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

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

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

Первое собеседование состоится в пятницу, 22 декабря, в 17-00, в 9-304. Вопросы разделены на обязательную группу (из неё предполагается знание всего) и дополнительную (из неё предполагается знание хотя бы половины вопросов, если в вопросе явно не указан иной критерий).

Второе собеседование состоится в четверг 1 февраля, в 13-30, в 9-304.

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

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

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

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

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

  • ИИ для логических игр (все эти темы имеют высокую сложность, особенно для игры в шашки)
    • Реверси
    • Волк и овцы
    • Мельница
    • Шашки русские
    • Шашки американские
  • Решатели (тоже темы высокой сложности)
    • Автоматический решатель игры в 15
    • Автоматический решатель кубика или пирамидки Рубика
    • Автоматический решатель сапёра
    • Автоматический решатель тетриса (по выбору: считать, что известна вся последовательность приходящих фигур, или считать, что известно только несколько следующих фигур, например две)
    • Решатель для игры terra incognita
    • SAT-солвер (использовать входные файлы в формате DIMACS)
  • Реализация в виде класса на Java одного из видов бинарного дерева поиска с авторегулировкой, например приведённые ниже (темы имеют среднюю сложность). Класс дерева должен реализовывать соответствующий интерфейс Java в обобщённом виде (Set или Map, в более сложном варианте SortedSet или SortedMap). Для усложнения задачи в неё можно добавить визуализацию.
    • АВЛ-дерево
    • Scapegoat tree
    • Splay tree
  • Реализация в виде класса на Java одного из видов хэш-таблицы, например приведённые ниже (темы имеют среднюю сложность). Класс таблицы должен реализовывать соответствующий интерфейс Java в обобщённом виде (Set или Map). Класс должен обеспечивать возможность неограниченного роста размера таблицы (в пределах памяти компьютера, естественно). Класс может обеспечивать или нет предсказуемый порядок перебора элементов (предсказуемый порядок, естественно, сложнее). Для усложнения задачи в неё можно добавить визуализацию.
    • Хэш-таблица с открытой адресацией
    • Хэш-таблица с двойным хэшированием
    • Хэш-таблица с разрешением коллизий с помощью бинарного дерева поиска

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

Важные даты:

  • 26.10 начало работы сервера
  • 19.11 -- последний срок регистрации команд (необходимо сообщить список членов команды и репозиторий с кодом решения)
  • 22.11 -- 24.11 первая итерация (спринт) официального соревнования
  • 13.12 23:59 дедлайн второй итерации
  • 14-18.12 вторая итерация (спринт) официального соревнования и выставление оценок

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

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

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

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

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

Теоретическая часть

Задания:

  • найти в массиве целых чисел подмассив с максимальной суммой (срок сдачи истёк 27.09)
  • дополнить классы из обучающего проекта BinaryTree, KtBinaryTree или Trie реализацией двух функцией -- подробности см. два последних слайда (срок сдачи 12.11, срок доделок 19.11)
  • решить с помощью эвристического алгоритма задачу о ранце или задачу коммивояжёра -- подробности см. предпоследний слайд (срок сдачи 10.12, без доделок)

Проверочные работы:

  • сортировки (27.09)
  • графы (15.11)
  • финальная работа (13.12) -- полтора часа по всему материалу

Методика выставления оценки по теории:

  • всего по теории можно получить шесть оценок (три задания, три работы)
  • оценка выставляется как средняя из четырёх оценок
  • две последние оценки (за последнее задание и финальную работу), если они есть, заменяют худшие из первых четырёх; пример -- имеются оценки 5, 4, 3, 3, 5, 2, вычёркиваются две тройки и оценка выводится из 5, 4, 5, 2, средняя 4
  • при наличии только трёх оценок, средняя выводится из них и добавляется штраф в 0.5 балла
  • двойки участвуют в выведении средней оценки на общих основаниях, но с учётом следующих моментов:
    • при наличии у студента ровно двух положительных оценок (более "2") ситуация решается индивидуально; в случае по умолчанию студенту даётся дополнительное задание и оценка по теории ставится после его выполнения
    • при наличии лишь одной положительной оценки или их отсутствии оценка по теории не выставляется

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

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