Олимпиадное программирование

2020/2021

Статус: Факультатив

Кто читает: Кафедра информационных технологий в бизнесе (Пермь)

Когда читается: 2-4 модуль

Преподаватели: Морозенко Владимир Викторович

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

Кредиты: 3

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

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

Аннотация

Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов, изучающих дисциплину «Олимпиадное программирование» образовательным стандартом федерального государственного автономного образовательного учреждения высшего профессионального образования национального исследовательского университета «Высшая школа экономики»

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

Развитие профессионального кругозора и алгоритмического мышления студентов
Выработка навыков командного решения задач, требующих распределения ролей в процессе разработки, реализации алгоритмов в виде программного продукта и его отладки

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

Разрабатывает алгоритм для решения поставленной задачи.
Реализует алгоритм в виде программного кода, готовит тесты, тестирует программный продукт.

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

Раздел 1.Алгоритмы и алгоритмические языки
Тема 1. Классы алгоритмов (точные, приближенные, эффективные, переборные, рекурсивные). Понятие алгоритма, требования к алгоритму, классы алгоритмов (точные, приближенные, эффективные, переборные, рекурсивные), примеры алгоритмов из разных классов для решения задач оптимизации, анализ их сложности и корректности. Тема 2. Структуры данных. Основные абстрактные типы данных, структуры данных (массив, список, стек, очередь, дерево), их реализация в различных языках программирования, примеры использования в стандартных алгоритмах.
Раздел 2.Разработка программ
Тема 3. Разработка алгоритмов и программ для решения задач по теме «Геометрия». Основные формулы аналитической геометрии для описания фигур (прямая на плоскости и в пространстве, плоскость, многоугольники), основные операции (скалярное, векторной и смешанное произведение) и формулы векторной алгебры, их применение для решения геометрических задач. Тема 4. Разработка алгоритмов и программ для решения задач по теме «Массивы». Одномерные и многомерные массивы, их применение для решения задач. Тема 5. Разработка алгоритмов и программ для решения задач по теме «Графы». Основные алгоритмы для работы с графами (Прима, Краскала, Дейкстры, Флойда, венгерский, «жадные»), оптимизационные задачи на графы (минимальное остовное дерево, максимальное паросочетание, максимальные поток минимальной стоимости, задача о назначениях). Тема 6. Разработка алгоритмов и программ для решения задач по теме «Рекурсия и динамическое программирование». Рекуррентные соотношения, их аналитическое решение и программная реализация, динамическое программирование и его связь с рекуррентными соотношениями, решение задач на составление рекуррентных соотношений, решение оптимизационных задач методом динамического программирования. Тема 7. Разработка алгоритмов и программ для решения задач по теме «Сортировка и поиск». Алгоритмы сортировки (сортировка вставками, быстрая сортировка, сортировка слиянием, цифровая сортировка), алгоритмы поиска порядковых статистик, поиск медианы, решение задач на сортировку и поиск. Тема 8. Разработка алгоритмов и программ для решения задач по теме «Строки». Основные алгоритмы работы со строками, лексикографическая сортировка строк, алгоритмы шифрования, решение задач с использованием строк. Тема 9. Разработка алгоритмов и программ для решения задач по теме «Комбинаторика». Комбинаторные операции (перестановки, сочетания, размещения) и принципы (сложения, умножения, дополнения, включения-исключения, кодирования), алгоритмы генерации комбинаторных объектов и быстрого вычисления числа сочетаний, решение задач на комбинаторику. Тема 10. Разработка алгоритмов и программ для решения задач по теме «Длинная арифметика». Операции модулярной арифметики, теорема Ферма, китайская теорема об остатках, системы исчисления с произвольным основанием, моделирование сложения, умножения и деления «длинных» чисел с помощью массивов, решение задач на «длинную арифметику».

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

Самостоятельная работа 1
Самостоятельная работа 2
Экзамен

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

Промежуточная аттестация (4 модуль)
0.2 * Самостоятельная работа 1 + 0.2 * Самостоятельная работа 2 + 0.6 * Экзамен

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