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

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

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

Даты:

  • 17 декабря, 16:00, 9-325 -- экспресс-тестирование по теории "не для всех"
  • 28 декабря, 16:00, 9-304 -- первое собеседование по теории
  • 4 февраля, ориентировочно 16:00 -- второе собеседование по теории

Обязательная группа вопросов:

  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 = “Неудовлетворительно” за курсовой проект (необходимо улучшать оценку), “Незачёт” по теории (необходимо улучшать оценку)

Страницы:

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

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

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

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

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

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

Важные даты:

  • до 29 октября -- регистрация команд
  • до 6 ноября -- регистрация рабочих репозиториев команд
  • 6-20 ноября -- тренировочные раунды
  • 21-23 ноября -- первый боевой раунд, публикация результатов и оценок
  • 24 ноября - 18 декабря -- период доработки
  • 19-21 декабря -- финальный раунд, публикация окончательных результатов и оценок

В качестве соревновательного проекта предлагается (в упрощённом виде) задача с конкурса ICFPC 2017.

Формулировка: реализовать программу-бот, обеспечивающую формирование ходов для следующей игры. Дан неориентированный граф с вершинами и дугами, часть вершин помечено как важные. Каждая из дуг может принадлежать какому-то игроку или не принадлежать никому. Ход игрока заключается в том, что определённая (одна) никому не принадлежащая дуга объявляется своей. Игроки ходят по очереди, очерёдность ходов определяется порядком подключения ботов к серверу. Игра прекращается, когда не принадлежащих никому дуг не остаётся. В конце игры игроки получают очки по следующим правилам: за каждый законченный путь между важной вершиной A и другой вершиной B даётся число очков, равное квадрату длины самого короткого пути между этими вершинами. Если вершина B -- тоже важная, очки за данный путь даются дважды. Игрок, набравший больше всех очков, выигрывает.

Технические требования:

  • участники предоставляют решение в виде программы (по умолчанию разрешаются языки Java и Kotlin; если вы хотите писать на другом языке, предупредите нас об этом)
  • процесс игры реализован на сервере, который общается с программами-игроками по определённому протоколу (обмен JSON-данными по протоколу TCP/IP). Подробности см. раздел "4. The lambda punter protocol" в спецификации задачи по ссылке ниже, в нашем варианте используется ТОЛЬКО online-режим, описанный в разделе 4.2 по той же ссылке
  • пример бота, общающегося с сервером, можно взять отсюда

Результаты:

Полезные ссылки:

Упражнения

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

Шесть уроков (1-3, 5-7):

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

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

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

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

Дедлайны:

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

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

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

Известные баги:

  • Тесты sortTemperatures из первого урока падают по тайм-ауту или по out of memory.
    • Чинится заменой вызова testGeneratedTemperatures(5000) в AbstractTaskTests.kt урока 1 на, например, testGeneratedTemperatures(100) -- значение аргумента вызова может зависеть от конкретной реализации вашего решения

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

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