Основы и методология программирования (углубленный курс)

Бакалавриат 2019/2020

Лучший по критерию «Полезность курса для Вашей будущей карьеры»

Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»

Статус: Курс обязательный (Прикладная математика и информатика)

Направление: 01.03.02. Прикладная математика и информатика

Кто читает: Базовая кафедра Яндекс

Где читается: Факультет компьютерных наук

Когда читается: 1-й курс, 1, 3 модуль

Формат изучения: без онлайн-курса

Преподаватели: Аверченко Алексей Валерьевич, Артюхин Станислав Геннадьевич, Евстропов Глеб Олегович, Зобнин Алексей Игоревич, Матросов Михаил Александрович, Полднев Антон Вячеславович, Смирнов Иван Федорович, Фельдшеров Святослав Викторович

Язык: русский

Кредиты: 9

Контактные часы: 144

Полная версия программы учебной дисциплины

Аннотация

Курс состоит из двух частей. Первая часть посвящена основам языка C++. Курс опирается на последний стандарт C++17. Вначале изучаются контейнеры, итераторы и алгоритмы стандартной библиотеки, и лишь затем - работа с памятью и указатели. Значительная время уделяется философии работы с ресурсами в C++. Вторая часть посвящена изучению методов построения и анализа алгоритмов, оценки их сложности в различных вычислительных моделях. Большой упор делается на эффективные структуры данных и анализ вероятностных структур. Студентам предлагается большой объём практических заданий, проверяемых автоматически и рецензируемых вручную.

Цель освоения дисциплины

Знание и практическое применение конструкций языка С++ в объёме достаточном для реализации любого алгоритма из курса.
Владение понятием теоретической сложности алгоритма и методами её оценки.
Понимание практической эффективности рассказанных алгоритмов.
Умение адаптировать и дорабатывать рассказанные алгоритмы под непосредственные практические приложения.

Планируемые результаты обучения

Знать основные контейнеры стандартной библиотеки C++.
Знать основные алгоритмы стандартной библиотеки C++.
Уметь работать с классами и объектами в C++
Знать модель работы с ресурсами в C++.
Умение правильно выбрать структуру работы с данными и реализовать её на практике.
Понимание концепции динамического программирования как метода оптимизации перебора комбинаторных объектов.
Базовое понимание математического аппарата современного шифрования и его практической значимости.
Уверенное владение терминологией теории графов, алгоритмами обхода и поиска кратчайших путей.
Понимание возможностей строковых алгоритмов, умение выбрать суффиксную структуру под конкретную задачу.

Содержание учебной дисциплины

Язык программирования C++
1. Переменные, ввод и вывод, условный оператор, циклы, оператор switch. 2. Векторы и строки. Алгоритм sort. 3. Структуры. Классы pair и tuple. 4. Константность. Ссылки. Указатели. 5. Функции и лямбда-функции. Способы передачи и возврата параметров. 6. Ассоциативные контейнеры map и unordered_map. 7. Контейнеры list и deque. Адаптеры stack, queue и priority_queue. Класс string_view. 8. Шаблонные функции. Алгоритмы стандартной библиотеки. 9. Классы: публичный интерфейс и приватные детали реализации. Функции-члены. 10. Жизненный цикл объекта. Конструкторы, деструктор. Семантика перемещения. 11. Динамическая память. Динамические массивы. Null-terminated strings. 12. Исключения. Идиома RAII. Умные указатели unique_ptr и shared_ptr. 13. Реализация шаблонного класса vector.
Алгоритмы
1. Задачи LCA и LA. 2. Персистентность и персистентные структуры данных. 3. Простой перебор комбинаторных объектов. Динамическое программирование. Основные идеи и примеры. Приёмы параметризации. Генерация комбинаторных объектов. 4. Динамическое программирование на ацикличных графах, подотрезках, поддеревьях и подмножествах. 5. Различные приёмы экономии памяти и восстановления ответа в задачах динамического программирования. 6. Введение в теоретико-числовые алгоритмы. Быстрое возведение в степень, расширенный алгоритм Евклида, решето Эратосфена и линейное решето, факторизация за O(n). 7. Тест на простоту Миллера-Рабина и шифрование RSA. 8. Алгоритм Карацубы. Метод деревьев рекурсии и основная теорема. 9. Основные термины теории графов. Некоторые интересные множества на графах. Обход в глубину и обход в ширину. Топологическая сортировка и компоненты сильной связности. 10. Мосты и точки сочленения. Компоненты рёберной и вершинной двусвязности. 11. Задача о кратчайших путях. Алгоритмы Форда-Беллмана, Флойда-Уоршелла и Дейкстры. 12. Задача о минимальном остове. Лемма о безопасном ребре. Алгоритмы Прима, Борувки и Краскалла. 13. Система непересекающихся множеств. Критерии оптимальности остовного дерева. Простейшие алгоритмы кластеризации на основе остовных деревьев. 14. Задача поиска шаблона в тексте. Префикс-функция и z-функция. Автомат префикс-функции. 15. Бор-дерево и сжатое бор-дерево. Алгоритм Ахо-Корасик. 16. Суффиксный массив и lcp 17. Алгоритм Укконена. 18. Паросочетания в двудольном графе. Алгоритм Куна. Теорема Кёнига-Эгервари. 19. Задача о максимальном потоке. Теорема Форда-Фалкерсона. 20. Полиномиальные алгоритмы решения задачи о максимальном потоке. Алгоритм Эдмондса-Карпа, техника масштабирования, алгоритм Диница. 21. Стоимостной поток. Определения и жадный алгоритм. Алгоритм Дейкстры с потенциалами Джонсона.

Элементы контроля

Контрольные работы
Домашнее задание
Экзамен
Экзамен в форме контеста
Контрольная работа (Алгоритмы)
Домашнее задание теоретическое (Алгоритмы)
Компьютерное тестирование (Алгоритмы)
Домашнее задание практическое (Алгоритмы)
Работа на семинаре (Алгоритмы)
Экзамен (Алгоритмы)

Промежуточная аттестация

Промежуточная аттестация (1 модуль)
0.35 * Домашнее задание + 0.25 * Контрольные работы + 0.4 * Экзамен
Промежуточная аттестация (3 модуль)
0.15 * Домашнее задание практическое (Алгоритмы) + 0.25 * Домашнее задание теоретическое (Алгоритмы) + 0.15 * Компьютерное тестирование (Алгоритмы) + 0.15 * Контрольная работа (Алгоритмы) + 0.3 * Экзамен (Алгоритмы)

Программа дисциплины