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

Собеседование по теории

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

Даты: TODO

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

  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. Хэш-таблицы: варианты реализации, характеристики
  4. Бинарные деревья поиска: балансировка, повороты
  5. Бинарные деревья поиска: красно-чёрное дерево
  6. Префиксные деревья
  7. Графовые алгоритмы (хотя бы два из перечисленных)
    1. A-Star
    2. Переборные алгоритмы
    3. Альфа-бета процедура
    4. Топологическая сортировка
    5. Поиск циклов
    6. Поиск мостов
    7. Поиск компонент связности
    8. Поиск минимального остовного дерева
  8. Эвристические алгоритмы (хотя бы один из перечисленных)
    1. Генетический алгоритм
    2. Алгоритм колонии муравьёв
    3. Алгоритм имитации отжига
  9. Вероятностные структуры данных
  10. NP-полные задачи: основные понятия, примеры задач
  11. Шифрование с открытым ключом: принцип работы
  12. Задачи (хотя бы две из перечисленных)
    1. Задача о поиске подмассива с максимальной суммой
    2. Задача о разрезании стержня
    3. Задача о ранце
    4. Задача коммивояжёра
    5. Задача о сумме подмножеств

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

Занятия в рамках цикла "Программирование" (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 = “Отлично” за курсовой проект, “Зачёт” по теории автоматом
  • От 4 до 4.49 = “Хорошо” за курсовой проект, “Зачёт” по теории автоматом
  • От 3.5 до 3.99 = “Хорошо” за курсовой проект, “Зачёт” по теории по итогам собеседования
  • От 3 до 3.49 = “Удовлетворительно” за курсовой проект, “Зачёт” по теории по итогам собеседования
  • От 2 до 2.99 = “Неудовлетворительно” за курсовой проект (необходимо улучшать оценку), “Зачёт” по теории по итогам собеседования
  • От 0 до 1.99 = “Неудовлетворительно” за курсовой проект (необходимо улучшать оценку), “Незачёт” по теории (необходимо улучшать оценку)

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

Страницы:

  • принятый JavaCodeStyle
  • официальный KotlinCodeStyle
  • учебный проект
    • NB: эта ссылка будет работать, начиная с 23 сентября. Прошлогодний проект смотреть можно, но просьба его не клонировать и пока не начинать решать задачи (разве что для собственного интереса)

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

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

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

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

  • ИИ для логических игр (все эти темы имеют высокую сложность, особенно для игры в шашки)
    • Реверси
    • Волк и овцы
    • Мельница
    • Шашки русские
    • Шашки американские
  • Решатели (тоже темы высокой сложности)
    • Автоматический решатель игры в 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 или другом языке программирования; программа должна находиться в репозитории, по требованию преподавателей к нему предоставляется доступ для проверки решения
  • соревнование проходит в два этапа, ориентировочно первый в середине ноября, второй и последний в середине декабря
  • начиная с момента окончания первого этапа соревнования другие участники в него не принимаются
  • исходя из абсолютных и относительных успехов участников в конце каждого этапа им ставятся оценки

Упражнения

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

Семь уроков:

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

Требуется решить по две задачи хотя бы из четырёх имеющихся уроков. Решать можно как на Котлине, так и на Java.

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

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

Дедлайны:

  • 20 октября 23:59 -- приём задач из уроков 1-2 заканчивается
  • TODO -- приём задач из урока 3 заканчивается
  • 8 декабря 23:59 -- приём задач из уроков 5-7 заканчивается

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

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

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

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