Структуры данных и алгоритмы, группы М3305 - М3308

Осенний семестр, 2015-2016

Таблица результатов

Вопросы к зачету

Преподаватели

• Понедельник, чет. неделя, 17-00, ауд. 320 — Практика М3305
• Понедельник, нечет. неделя, 17-00, ауд. 320 — Практика М3306

• Четверг, чет. неделя, 11-40, ауд. 99 — Практика М3307

• Четверг, нечет. неделя, 11-40, ауд. 99 — Практика М3308

• Четверг, чет. неделя, 13-30, ауд. 302 — Лекция

Лабораторные работы

• Как сдавать задачи
• Лабораторная 1, закончилась 22.09.16
• Лабораторная 2, закончилась 06.10.16
• Лабораторная 3, закончилась 20.10.16
• Лабораторная 4, закончилась 02.11.16
• Лабораторная 5, закончилась 16.11.16
• Лабораторная 6, закончилась 30.11.16
• Лабораторная 7
  • Сервер принимает задачи до 23:59 14.12.16

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

• В случаях, когда источник не указан, подразумевается Кормен, Лейзерсон и др. "Алгоритмы. Построение и анализ" (второе издание).
• Лекция 1. Введение, сортировка вставками
  • (По желанию) изучить доказательство корректности сортировки вставками с помощью инвариантов цикла по главе 2.1.
  • Получить выражения для времени работы сортировки вставками в лучшем и худшем случаях (см. главу 2.2).
  • Упражнения 2-1-3 (стр. 63), 2-2-2 (стр. 71), 2-2-3 (стр. 71).
• Лекция 2. Асимптотические оценки, сортировка слиянием
  • Доказать теорему 3.1 (стр. 92).
  • Доказать правило сумм, правило произведений, правила "отбрасывания" констант для верхней асимптотической оценки (см. Ахо, Хопкрофт, Ульман "Структуры данных и алгоритмы", стр. 32).
  • Упражнения 3.1-2, 3.1-3, 3.1-4 (стр. 97).
  • Упражнение 3-4 а-ж (стр. 106).
  • Упражнения 2.3-5, 2.3-6 (стр. 82).
• Лекция 3. Пирамидальная сортировка, цифровая сортировка
  • Доказать корректность алгоритма построения пирамиды с помощью инварианта цикла (стр. 186).
  • Оценить время работы алгоритма построения пирамиды (стр. 186-187).
  • Доказать нижнюю оценку на время работы сортировок, основанных на сравнении (стр. 221-223).
  • Изучить алгоритм карманной сортировки (стр. 230).
  • Определите
    • асимптотическое время работы;
    • асимптотическую оценку дополнительной памяти;
    • ограничения на элементы сортируемого массива;
    • является ли сортировка устойчивой;
    для перечисленных ниже сортировок:
    • сортировка вставками, выбором, пузырьковая;
    • слиянием;
    • пирамидальная;
    • быстрая (QuickSort);
    • цифровая;
    • подсчетом;
    • карманная.
  • Упражнения 6.3-3, 6.4-3, 8.2-2.
• Лекция 4. Элементарные структуры данных: стек, очередь, списки. Очередь с приоритетами.
  • Написать псевдокод и проанализировать время работы операций для односвязного списка.
  • Проанализировать время работы операций для отсортированного списка.
  • Упражнение 6.5-4.
  • Упражнение 6.5-5.
  • Упражнение 6.5-6.
• Лекция 5. Бинарные деревья поиска.
  • Доказать время работы центрированного обхода (Теорема 12.1, стр. 318).
  • Упражнение 12.2-6.
  • Упражнение 12.2-7.
  • Упражнение Б.5-3 (стр. 1223).
  • Упражнение Б.5-4.
  • Упражнение Б.5-7.
• Лекция 6. Хеш-таблицы.
  • Доказать что А в методе умножения хорошее (см. Кнут, Искусство программирования т.3 стр 553-554).
  • Упражнение 11.3.
  • Упражнение 11.4-1.
  • Упражнение 11.2-2.
• Задание для самостоятельного изучения (по желанию). Splay-деревья.
  • Изучить викиконспект по Splay-деревьям.
  • Рассказать, как работает вспомогательная операция Splay в Splay-деревьях (случаи zig, zig-zig, zig-zag).
  • Рассказать, как реализуются операции поиска, вставки и удаления в Splay-деревьях.