• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Бакалавриат 2019/2020

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

Лучший по критерию «Полезность курса для Вашей будущей карьеры»
Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»
Статус: Курс обязательный (Прикладная математика и информатика)
Направление: 01.03.02. Прикладная математика и информатика
Когда читается: 1-й курс, 1, 3 модуль
Формат изучения: без онлайн-курса
Язык: русский
Кредиты: 9

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

Аннотация

Курс состоит из двух частей. Первая часть посвящена основам языка 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 * Экзамен (Алгоритмы)
Список литературы

Список литературы

Рекомендуемая основная литература

  • Дейл Н., Уимз Ч., Хедингтон М. - Программирование на С++ - Издательство "ДМК Пресс" - 2007 - 672с. - ISBN: 5-93700-008-0 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/1219

Рекомендуемая дополнительная литература

  • Липпман С., Лажойе Ж. - Язык программирования С++. Полное руководство - Издательство "ДМК Пресс" - 2006 - 1105с. - ISBN: 5-94074-040-5 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/1216