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

Пересдача теоретического зачёта состоится 9 июня в 13:00, ориентировочно в аудитории 9-309, в формате коллективной или индивидуальной беседы.

Вопросы для теоретического зачёта

  1. Оценка трудоёмкости и ресурсоёмкости алгоритмов.
  2. Создание алгоритмов: рекуррентные алгоритмы
  3. Создание алгоритмов: композиция
  4. Создание алгоритмов: динамическое программирование, мемоизация
  5. Алгоритмы случайной перестановки
  6. Сортировка вставками
  7. Сортировка слияниями
  8. Быстрая сортировка
  9. Сортировка за линейное время
  10. Структуры данных: контейнеры
  11. Алгоритмы выделения / освобождения памяти
  12. Хэш-таблицы: варианты реализации, характеристики
  13. Бинарные деревья: варианты реализации, характеристики
  14. Класс P и класс NP
  15. NP-полные задачи
  16. Задача о поиске подмассива с максимальной суммой
  17. Задача о найме работника
  18. Задача о разрезании стержня
  19. Задача о ранце
  20. Задача о сумме подмножеств.

1. Программирование под Android

Ранее эта часть курса существовала в рамках курса Java-технологии (см. ссылки внизу страницы).

Презентации / примеры:

# Дата Название Тематика
1 2016-02-11 Введение Платформа Android, Средства разработки. Подготовка к работе. Архитектура приложения. Жизненный цикл приложения.
2 2016-02-25 Ресурсы Ресурсы. Управление ресурсами.
3 2016-03-03 Альтернативные ресурсы, Activity
4 2016-03-17 Activity API, процессы и потоки Жизненный цикл Activity, обработка событий, типы процессов, UI Thread, Worker Threads, Async Tasks
5 2016-03-31 Intents, Broadcast receivers
6 2016-04-21 Tasks, Back stacks, Services
7 2016-05-05 Content providers
8 2016-05-19 Доп. лекция (не в доступе)

2. Алгоритмы и структуры данных

Основной раздел курса читается впервые.

Литература:

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

Презентации / примеры:

# Дата Название Примеры Тематика
1 2016-02-18 Введение в алгоритмы См. Алгоритм: определение, свойства, рекуррентность, принцип композиции, примеры
2 2016-03-10 Вероятностные алгоритмы --- Вероятностный анализ, индикаторные случайные величины, алгоритмы перестановки
2016-03-24 Алгоритмы сортировки(2-й сем) --- Сортировка: вставками (включениями), выбором, пузырьком (обменом), двоичной кучей, слияниями, Хоара
3 2016-03-24 Алгоритмы сортировки --- Сортировка: устойчивость, корректность, производительность, ресурсоёмкость, сортировки за линейное время
4 2016-04-07 Структуры данных, управление памятью См. Простые структуры данных. Выделение и освобождение памяти
5 2016-04-14 Язык Kotlin, библиотека Anko См. Ознакомительная лекция: использование Kotlin в Java-проектах и Android-проектах
6 2016-04-28 Таблицы и деревья См. Таблицы, хэш-таблицы, бинарные деревья поиска, повороты, реализации
7 2016-05-12 Динамическое программирование См. Мемоизация, разрезание стержня, задача о ранце, жадные алгоритмы, генетические алгоритмы
8 2016-05-26 NP-полнота --- Класс P, класс NP, NP-полные задачи, примеры

Примеры курсовых проектов на весенний семестр 2015/16 уч. год

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

Android

  • Балда
  • Японский кроссворд (2х или 3х цветный)
  • Морской бой
  • English peg solitaire
  • European peg solitair
  • Точки / Го
  • Крестики-нолики
  • Шахматы
  • Шашки
  • Волк и овцы
  • Сапер (http://anowl-ig.narod.ru/):
  • Быки и коровы
  • Выбирание камней
  • Простая мельница
  • Ним
  • Пазлы
  • Числовые ребусы
  • Сим
  • Ханойская башня
  • Домино (вариант на выбор)
  • Пасьянс (на выбор)
  • Судоку
  • Ход конем (http://4pda.ru/forum/index.php?showtopic=309260)
  • Монополия
  • Маджонг
  • 21 очко
  • Гонки на бумаге (Paper Racing) (http://4pda.ru/forum/index.php?showtopic=391655)

Алгоритмы и структуры данных

  • Реализация в виде класса на Java одного из видов бинарного дерева поиска с авторегулировкой, например
    • АВЛ дерево
    • Расширяющееся дерево
    • Scapegoat tree
  • Реализация в виде класса на Java одного из видов multi map (ассоциативный массив, в котором каждому ключу может соответствовать более одного значения), например
    • SetMultimap -- значения, соответствующие одному ключу, не могут повторяться и неупорядочены
    • ListMultimap -- значения, соответствующие одному ключу, могут повторяться и упорядочены
  • ...

Комбинированные задачи

  • Игра в 15 с GUI и автоматическим решателем.
  • Кубик или Пирамидка Рубика с GUI и автоматическим решателем.
  • Логическая игра с GUI и искусственным интеллектом
    • реверси
    • волк и овцы
    • мельница
    • четыре в ряд
    • быки и коровы
    • ... (игра должна быть средней сложности, иначе написание искусственного интеллекта будет слишком трудным)
  • Лабиринтовая игра с GUI и искусственным интеллектом, см. здесь
  • Японский кроссворд с автоматическим решателем
  • Задачи с ежегодного конкурса ICFPC с GUI для их демонстрации

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

  • лекции за год 2014-15 (автор Кузнецов А.Н.) можно посмотреть здесь
  • лекции за год 2012-13 (автор Кузнецов А.Н.) можно посмотреть здесь