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

2020/2021

Учебный год

RUS

Обучение ведется на русском языке

3

Кредиты

Кто читает:

Кафедра информационных технологий в бизнесе (Пермь) (Факультет социально-экономических и компьютерных наук)

Статус:

Факультатив

Когда читается:

2-4 модуль

Преподаватель

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

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

Аннотация

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

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

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

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

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

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

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

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

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

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

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

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

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

• Алгоритмы и структуры данных : учебник / В.В. Белов, В.И. Чистякова. — М. :КУРС : НИЦ ИНФРА-М, 2017. — 240 с. — (Бакалавриат). - Режим доступа: http://znanium.com/catalog/product/766771

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

• Мейер Б. - Инструменты, алгоритмы и структуры данных - Национальный Открытый Университет "ИНТУИТ" - 2016 - 542с. - ISBN: - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/100603