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

Организация зачёта

  • К 26 мая необходимо выполнить индивидуальные задания (кроме освобождённых от них)
  • 29 мая в 10-00 (9-304) состоится семестровая проверочная работа (обязательная для всех, кроме уже получивших зачёт)
  • 2 июня в 17-00 (9-304) состоится собеседование по теории (студенты приглашаются индивидуально, списки будут разосланы старостам)

Вопросы:

  1. Оценка трудоёмкости и ресурсоёмкости алгоритмов.
  2. Создание алгоритмов: рекуррентные алгоритмы
  3. Создание алгоритмов: композиция
  4. Создание алгоритмов: динамическое программирование и мемоизация
  5. Создание алгоритмов: жадные алгоритмы
  6. Сортировка вставками
  7. Сортировка слияниями
  8. Пирамидальная сортировка
  9. Быстрая сортировка
  10. Сортировка за линейное время
  11. Структуры данных: графы, варианты представления, применение
  12. Графовые алгоритмы: поиск в ширину
  13. Графовые алгоритмы: поиск в глубину
  14. Графовые алгоритмы: алгоритм Дейкстры
  15. Структуры данных Java: List / ArrayList / LinkedList
  16. Структуры данных Java: Stack / Queue / Deque / ArrayDeque / LinkedList
  17. Хэш-таблицы: варианты реализации, характеристики
  18. Структуры данных Java: Set / Map / HashSet / HashMap / LinkedHashSet / LinkedHashMap
  19. Бинарные деревья поиска: основные операции
  20. Бинарные деревья поиска: балансировка, повороты
  21. Бинарные деревья поиска: красно-чёрное дерево
  22. Структуры данных Java: SortedSet / SortedMap / TreeSet / TreeMap
  23. Задача о поиске подмассива с максимальной суммой
  24. Задача о разрезании стержня
  25. Задача о ранце
  26. Задача коммивояжёра

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

Читается параллельно с курсом программирование под Android

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

Литература

  • Т. Кормен и др. Алгоритмы. Построение и анализ
  • Д. Кнут. Искусство программирования
  • Н. Вирт. Алгоритмы + Структуры данных = Программы
  • Е. В. Пышкин. Структуры данных и алгоритмы: реализация на 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)

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

Отчетность:

  • курсовой проект
  • домашние задания (см. ниже)
  • теоретический зачёт (см. ниже)

Страницы:

Домашние задания

Общие требования: домашнее задание выполняется в виде метода или методов класса, для которых написаны автоматические тесты (с использованием JUnit или аналогичной библиотеки). Сдаются задания по электронной почте, код предпочтительнее выкладывать на GitHub.

  1. (факультативное, срок 15.05) Дана позиция игры в 15. Найти цепочку ходов, возвращающую эту позицию в исходное положение.
  2. (обязательное, срок 20.03) Решить задачу о поиске максимального подмассива одним из двух методов (разделяй и властвуй, рекуррентный). Подробности в 1-й лекции.
  3. (методическое, срок 20.03) Прочитать про алгоритмы поиска в ширину (BFS) и в глубину (DFS) на графе.
  4. (срок 27.03, для пропустивших или проваливших тестирование 20.03) Написать функцию для поиска кратчайшего пути на графе в ширину (фамилии, начинающиеся с А..К) или в глубину (фамилии, начинающиеся с Л..Я). Для представления графа и вершины использовать интерфейс Graph из презентации третьей лекции.
  5. (срок 2.05, для пропустивших тестирование 17.04) В обучающем проекте доработать (на выбор) метод iterator или метод delete в классе lesson3.BinaryTree. Написать также тесты, подтверждающие работоспособность разработанного метода. Задание представить в виде проекта на GitHub или Pull Request к обучающему проекту.
  6. Индивидуальное задание (срок 26.05). Список тем см. ниже. Возможны (по договорённости с преподавателем) другие темы (предполагается реализация сложного алгоритма или/и структуры данных). Может быть сделано как часть курсового проекта. Выполняется обязательно или по желанию студента в зависимости от итогов аттестации 27.03.

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

Внимание: списки задач ориентировочные. В любом случае проконсультируйтесь с руководителем курсового проекта.

  • Реализация в виде класса на Java одного из видов бинарного дерева поиска с авторегулировкой, например
    • АВЛ-дерево
    • Scapegoat tree
    • Splay tree
  • Реализация в виде класса на Java одного из видов multi map (ассоциативный массив, в котором каждому ключу может соответствовать более одного значения), например
    • SetMultimap -- значения, соответствующие одному ключу, не могут повторяться и неупорядочены
    • ListMultimap -- значения, соответствующие одному ключу, могут повторяться и упорядочены
  • Реализация в виде класса на Java одного из видов хэш-таблицы, например:
    • Хэш-таблица с открытой адресацией
  • Решатели
    • Автоматический решатель игры в 15
    • Автоматический решатель кубика или пирамидки Рубика
    • Автоматический решатель сапёра
    • Автоматический решатель тетриса (считать, что известна вся последовательность приходящих фигур)
    • Решатель для игры terra incognita
    • SAT-солвер (использовать входные файлы в формате DIMACS)
  • Шифраторы
    • RSA
    • AES
  • Архиваторы
    • ...
  • ИИ для логических игр
    • реверси
    • волк и овцы
    • мельница
    • шашки
  • Задачи с ежегодного конкурса ICFPC

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

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