Содержание курса в осеннем семестре 2020/21 уч. года

Зачёт по теории

Обязателен для всех студентов, у кого на момент проведения зачёта (точная дата уточняется) средняя оценка за семестр с учётом дробной части (см. отчётность ниже) ниже 3.5. Для допуска к зачёту необходимо иметь положительную оценку по упражнениям или соревнованию (см. отчётность ниже). Может проводиться в формате собеседования или в формате тестирования.

Даты: 17 декабря (и далее будет дата в феврале для досдачи).

Обязательная группа вопросов (все вопросы прошлогодние, по итогам этого года возможны изменения в списке):

  1. Оценка трудоёмкости и ресурсоёмкости алгоритмов. O большое.
  2. Бинарный поиск
  3. Сортировка слияниями
  4. Хэш-таблицы: принцип работы, основные операции
  5. Бинарные деревья поиска: принцип работы, основные операции
  6. Структуры данных: графы, варианты представления, применение
  7. Графовые алгоритмы: поиск в ширину
  8. Графовые алгоритмы: поиск в глубину
  9. Графовые алгоритмы: алгоритм Дейкстры
  10. Структуры данных Java: List / ArrayList / LinkedList
  11. Структуры данных Java: Stack / Queue / Deque / ArrayDeque / LinkedList
  12. Структуры данных Java: Set / Map / HashSet / HashMap / LinkedHashSet / LinkedHashMap
  13. Структуры данных Java: SortedSet / SortedMap / TreeSet / TreeMap

Дополнительная группа вопросов:

  1. Создание алгоритмов (хотя бы два метода из перечисленных)
    1. Рекуррентные алгоритмы
    2. Композиция
    3. Динамическое программирование и мемоизация
    4. Жадные алгоритмы
  2. Сложные сортировки (хотя бы одна из перечисленных)
    1. Пирамидальная сортировка
    2. Быстрая сортировка
    3. Сортировки за линейное время (подсчётом, карманная, другие)
  3. Хэш-таблицы: варианты реализации, характеристики (хотя бы два из перечисленных)
    1. Таблицы с прямой адресацией
    2. Метод цепочек
    3. Открытая адресация
    4. Кукушкино хэширование
  4. Деревья поиска и прочие (хотя бы одно из перечисленного)
    1. Балансировка и повороты
    2. Красно-чёрное дерево
    3. Префиксные деревья
  5. Графовые алгоритмы (хотя бы два из перечисленных)
    1. A-Star
    2. Переборные алгоритмы
    3. Альфа-бета процедура
    4. Топологическая сортировка
    5. Поиск циклов
    6. Поиск мостов
    7. Поиск компонент связности
    8. Поиск минимального остовного дерева
  6. Эвристические алгоритмы (хотя бы один из перечисленных)
    1. Генетический алгоритм
    2. Алгоритм колонии муравьёв
    3. Алгоритм имитации отжига
  7. Вероятностные структуры данных (хотя бы одна из перечисленных)
    1. Bloom Filter
    2. HyperLogLog
    3. Count-min sketch
  8. Задачи (хотя бы две из перечисленных)
    1. Задача о поиске подмассива с максимальной суммой
    2. Задача о разрезании стержня
    3. Задача о ранце
    4. Задача коммивояжёра
    5. Задача о сумме подмножеств
  9. Дополнительные разделы (хотя бы один из перечисленного)
    1. Шифрование с открытым ключом: принцип работы
    2. Машина Тьюринга: принцип работы
    3. NP-полные задачи: основные понятия, примеры задач

Информация о курсе

Занятия в рамках цикла "Программирование" (3-й семестр).
Преподаватели:
Глухих М.И.
Петров М.А.
Гагарский К.А.
Ахин М.Х.
Беляев М.А.
Абдуллин А.М.
Егорова И.А.
Сидорина Т.Л.
Слушатели:
Студенты, обучающиеся по направлениям бакалавриата "Информатика и вычислительная техника" и "Автоматизация и управление"

Литература

  • Т. Кормен и др. Алгоритмы. Построение и анализ
  • Д. Кнут. Искусство программирования
  • Н. Вирт. Алгоритмы + Структуры данных = Программы
  • Е. В. Пышкин. Структуры данных и алгоритмы: реализация на C/C++ - книга есть в Интранете
  • McDowell, G. L. Cracking the Coding Interview: 150 Programming Questions and Solutions.
  • S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani. Algorithms.

Электронные ресурсы

JRE / JDK

Среды разработки (IDE)

Документация

Отчетность:

Два из трёх:

  • индивидуальный проект
  • соревновательный проект
  • упражнения

За каждую из трёх частей студенту ставится оценка от 2.5 до 5 (примерно соответствующая общепринятой пятибалльной системе), или 0 в случае отсутствия данной части или неудовлетворительного её состояния. Далее считается среднее арифметическое из двух лучших оценок, из него выводятся оценки за семестр по следующему принципу:

  • От 4.5 до 5 = “Отлично” за курсовой проект, “Зачёт” по теории автоматом (если оценка получена не позднее 28 декабря), или по итогам тестирования и/или собеседования
  • От 4 до 4.49 = “Хорошо” за курсовой проект, “Зачёт” по теории автоматом (если оценка получена не позднее 28 декабря), или по итогам тестирования и/или собеседования
  • От 3.5 до 3.99 = “Хорошо” за курсовой проект, “Зачёт” по теории по итогам тестирования и/или собеседования
  • От 3 до 3.49 = “Удовлетворительно” за курсовой проект, “Зачёт” по теории по итогам тестирования и/или собеседования
  • Менее 3, но положительная оценка за соревновательный проект или упражнения = “Неудовлетворительно” за курсовой проект (необходимо улучшать оценку), “Зачёт” по теории по итогам тестирования и/или собеседования
  • Менее 3, и отрицательная оценка за соревновательный проект и упражнения = “Неудовлетворительно” за курсовой проект (необходимо улучшать оценку), “Незачёт” по теории (необходимо улучшать оценку)

Допустимые языки для выполнения всех трёх частей практики: Java, Kotlin.

Страницы:

Презентации лекций

Внимание: презентации, помеченные (2019), прошлогодние.

Примеры индивидуальных проектов на осенний семестр 2019/20 уч. год

Внимание: в качестве темы не разрешается выбирать задачу, решение которой дублирует классы из стандартной библиотеки Java (например, хэш-таблица с разрешением коллизий методов цепочек или красно-чёрное дерево). Выбранную тему обязательно обсудить с преподавателем практики, уточнить формулировку темы и оценить вместе с ним, адекватную ли сложность она имеет. Преподаватели практики оставляют за собой право ограничить оценку за выполнение сравнительно лёгких проектов значениями 4.5 или 4.0.

Все задания по умолчанию сдаются в виде репозитория на GitHub с собирающимся проектом и проходящими тестами. Наличие тестов и соблюдение JavaCodeStyle обязательно.

  • ИИ для логических игр (все эти темы имеют высокую сложность, особенно для игры в шашки)
    • Реверси
    • Волк и овцы
    • Мельница
    • Шашки русские
    • Шашки американские
  • Решатели (тоже темы высокой сложности)
    • Автоматический решатель игры в 15
    • Автоматический решатель кубика или пирамидки Рубика
    • Автоматический решатель сапёра
    • Автоматический решатель тетриса (по выбору: считать, что известна вся последовательность приходящих фигур, или считать, что известно только несколько следующих фигур, например две)
    • Решатель для игры terra incognita
    • SAT-солвер (использовать входные файлы в формате DIMACS)
  • Реализация в виде класса на Java одного из видов бинарного дерева поиска с авторегулировкой, например приведённые ниже (темы имеют среднюю сложность). Класс дерева должен реализовывать соответствующий интерфейс Java в обобщённом виде (Set или Map, в более сложном варианте SortedSet или SortedMap). Для усложнения задачи в неё можно добавить визуализацию.
    • АВЛ-дерево
    • Scapegoat tree
    • Splay tree
    • Трип/дерамида (оно же Декартово дерево)
  • Реализация в виде класса на Java одного из видов хеш-таблицы, например приведённые ниже (темы имеют среднюю сложность). Класс таблицы должен реализовывать соответствующий интерфейс Java в обобщённом виде (Set или Map). Класс должен обеспечивать возможность неограниченного роста размера таблицы (в пределах памяти компьютера, естественно). Класс может обеспечивать или нет предсказуемый порядок перебора элементов (предсказуемый порядок, естественно, сложнее). Для усложнения задачи в неё можно добавить визуализацию.
    • Хеш-таблица с открытой адресацией
    • Хеш-таблица с двойным хешированием
  • Реализация в виде класса на Java одной из прочих структур данных. Точный вид задания согласовывается с преподавателем. Предполагается, как минимум, возможность неограниченного роста структуры данных и максимальная её универсальность. Возможно добавление визуализации
    • Скиплист (он же Список с пропусками, с реализацией List<>, Set<> или SortedSet<> в зависимости от желаемой сложности)
    • 32- или 64- арное дерево поиска для целых чисел (с реализацией Set<>(Map<>) или SortedSet<>(SortedMap<>) в зависимости от желаемой сложности)
    • суффиксное дерево (с алгоритмом Укконена или без него в зависимости от желаемой сложности)
    • бинарная куча
    • фильтр Блума (с произвольным количеством хеш-функций или с фиксированным их количеством в зависимости от желаемой сложности, с реализацией Set<>, частично на заглушках)
  • Варианты посложнее:
    • Хеш-дерево (например, hash array-mapped trie, с реализацией Set<> или Map<>)
    • Суффиксный массив с префиксным массивом (с реализацией основных операций для строк, набор можно варьировать, с построением за O(N) для особой сложности)

Соревновательный проект

В качестве соревновательного проекта использована задача с конкурса ICFPC 2019.

Основные правила:

  • можно участвовать в одиночку или командой из двух человек
  • требуется зарегистрироваться на страничке соревнования до конца октября
  • для решения задачи следует создать программу на Java, Kotlin или другом языке программирования; программа должна находиться в репозитории, по требованию преподавателей к нему предоставляется доступ для проверки решения
  • соревнование проходит в два этапа, ориентировочно первый в середине ноября, второй и последний в середине декабря
  • начиная с момента окончания первого этапа соревнования другие участники в него не принимаются
  • исходя из абсолютных и относительных успехов участников в конце каждого этапа им ставятся оценки

Упражнения

Пройдут в срок с 18 сентября по 10 декабря. Учебный проект с задачами здесь. Задания сдаются через систему Котоед.

Восемь уроков:

  1. Задачи на сортировку
  2. Общие задачи на построение алгоритмов
  3. Задачи на бинарные деревья
  4. Задачи на префиксные деревья
  5. Задачи на хэш-таблицы
  6. Задачи на графы
  7. Задачи на динамическое программирование
  8. Задачи на эвристические алгоритмы

Требуется решить по две задачи из четырёх или пяти имеющихся уроков. Итоговая оценка за упражнения получается делением числа баллов, набранных за задачи в Котоеде (пять лучших уроков, две лучшие в каждом уроке, с учётом штрафов преподавателей) на 12 (60 = отлично, 48 = хорошо и так далее). Решать можно как на Котлине, так и на Java. Допустимая версия Котлина: 1.4.*, допустимая версия JDK: 11 (при использовании других версий JDK могут возникать проблемы с совместимостью версий при проверке на Котоеде).

Требования к решению:

  • Код (в приличном стиле)
  • В комментарии (обязательно)
    • Оценка трудоёмкости
    • Оценка ресурсоёмкости – можно опустить, только если O(1)
  • Тесты каждой из следующих групп:
    • Обычные случаи
    • Краевые случаи (мало данных, нестандартный ответ и т.п.)
    • Длинные (на производительность)
    • В некоторых задачах могут уже быть тесты всех групп
    • Обязательно дописать к тестам задачи хотя бы одну проверку (даже если по вашему мнению тестов достаточно)
    • Тесты должны проходить (если вы считаете, что они не проходят из-за бага в тестах, стоит написать комментарий по этому поводу)

Дедлайны:

  • 1 ноября 23:59 -- дедлайн на задачи из первых трёх уроков
  • 10 декабря 23:59 -- дедлайн на все остальные задачи

От чего зависит оценка:

  • Количество и сложность задач
  • Из каждого урока оцениваются две самые сложные задачи
    • Качество кода + Качество алгоритма
    • Правильность оценки алгоритма
    • Полнота тестов

Архив за предыдущие годы

  • лекции за год 2019-20 (автор Глухих М.И.) можно посмотреть здесь
  • лекции за год 2018-19 (автор Глухих М.И.) можно посмотреть здесь
  • лекции за год 2017-18 (автор Глухих М.И.) можно посмотреть здесь
  • лекции за год 2016-17 (автор Глухих М.И.) можно посмотреть здесь
  • лекции за год 2015-16 (авторы Глухих М.И., Кузнецов А.Н.) можно посмотреть здесь