1. Основные принципы отладки программ.

1. Зачем сжимать информацию?
2. Сжатие с потерями и без потерь.
3. Алгоритм RLE.
4. Алгоритм Хаффмана: построение кодового дерева, упаковка и распаковка.
5. Алгоритм LZ77 (скользящее окно).
6. Алгоритм LZW.
7. Исключительный случай при распаковке LZW.
8. Сжатие с потерями и функциональный анализ.

Слайды:

Видеозапись:

1. Что такое хорошая программа (хороший проект)?
2. Хорошие и плохие интерфейсы (модулей и программ).
3. Тестирование и документирование.

1. Общий принцип работы хеш-таблицы.
2. Требования к хеш-функции.
3. Интерфейс хеш-таблицы.
4. Размещение в массиве: метод деления, метод умножения.
5. Тривиальные хеш-функции.
6. Хеш-функция Дженкинса.
7. Хеш-функция для набора элементов.
8. Конфликты и способы их разрешения.
9. Списки коллизий.
10. Открытая адресация: линейное, квадратичное исследование, двойное хеширование.
11. Кукушиное хеширование (cuckoo hash).
12. Хеш vs. дерево.
13. Криптографические хеш-функции.
14. Контрольные суммы.
15. Принцип адресации по содержимому.
16. Фильтр Блума.
17. Генерация хеш-функций для фильтра Блума.

1. АВЛ-деревья.
2. 2-3-4 деревья.
3. Красно-черные деревья (red-black trees).
4. Префиксные деревья (trie).
5. Слоеные списки (skip list).

Слайды:

Видеозапись:

1. Структура данных дерево.
2. Представление деревьев в Python.
3. Двоичные деревья.
4. Обходы двоичных деревьев, связь обходов с древовидным представлением арифметических выражений.
5. Преобразование произвольного дерева в двоичное.
6. Интерфейс и применение деревьев поиска.
7. Высота дерева поиска.
8. Удаление элемента.
9. Оптимальные деревья поиска.
10. Выворачивание (splay trees).

1. Записи.
2. Массивы.
3. Стеки, очереди и их применение в различных задачах.
4. Реализация стека с помощью динамического массива.
5. Связные списки: структура и свойства.
6. Операции над списками.
7. Двусвязные списки, кольцевые списки, двусвязные кольцевые списки.
8. Данные как «белый ящик» и как «черный ящик».
9. Отличия абстрактных типов данных от структур данных.
10. Очередь с приоритетом.

1. Поиск подстроки в строке — метод грубой силы и идеи его ускорения.
2. Алгоритм Боуэра-Мура.
3. Алгоритм Рабина-Карпа.
4. Программирование как борьба со сложностью.
5. Программа как один большой черный ящик.
6. Декомпозиция на модули.
7. Пример модульной структуры: скачивалка изображений.
8. На что указывает граф связей между модулями?
9. Модуль = Интерфейс + Реализация.
10. Устройство модулей в Python.
11. Стандартная библиотека Python как набор модулей.
12. Почему интерфейс важнее реализации?
13. Операционная система как интерфейс.
14. Признаки хорошего интерфейса.

1. Cортировка Шелла.
2. Быстрая сортировка. Процедура разделения массива.
3. Алгоритм выбора k-го элемента.
4. Стабильность сортировок.
5. Сортировка слиянием.
6. Пирамидальная сортировка.
7. Нижняя оценка скорости сортировок, основанных на сравнениях.
8. Линейные сортировки: подсчетом, поразрядная, карманная.

1. Сложность алгоритмов. Нотация O, Ω, Θ.
2. Задача сортировки.
3. Bogosort и bozosort.
4. Сортировка выбором.
5. «Пузырьковая» сортировка.
6. Сортировка вставками.
7. Принцип «Разделяй и властвуй». Примеры: задача о ханойских башнях, получение перестановок, алгоритм Карацубы (умножение длинных чисел).
8. Основная теорема о рекуррентных соотношениях.
9. Поиск в массиве, двоичный поиск.
10. Рекурсия. Удачные и неудачные примеры использования рекурсии.

Сайт с визуализацией сортировок