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

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

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

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

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

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

Кто читает: Департамент больших данных и информационного поиска

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

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

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

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

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

Кредиты: 9

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

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

Аннотация

Курс состоит из двух частей. Первая часть посвящена основам языка 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.25 * Домашнее задание + 0.45 * Контрольные работы + 0.3 * Экзамен
Промежуточная аттестация (3 модуль)
0.25 * Домашнее задание + 0.3 * Домашнее задание теоретическое (Алгоритмы) + 0.15 * Контрольная работа (Алгоритмы) + 0.15 * Контрольные работы + 0.15 * Экзамен

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