18.05.2020. № 11. Отладка

Развернуть

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

27.04.2020. № 10. Упаковка данных

Развернуть

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

Слайды:

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

20.04.2020. № 9. Проекты

Развернуть

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

06.04.2020. № 8. Хеш-таблицы

Развернуть

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

23.03.2020. № 7. АВЛ-деревья, красно-черные деревья, префиксные деревья

Развернуть

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

Слайды:

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

16.03.2020. № 6. Деревья, бинарные деревья поиска, splay-деревья

Развернуть

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

04.03.2020. № 5. Составные типы данных, стек, очередь, списки, очередь с приоритетом

Развернуть

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

02.03.2020. № 4. Алгоритмы поиска подстроки в строке, модули

Развернуть

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

17.02.2020. № 3. Сортировки: квази-линейные, линейные

Развернуть

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

10.02.2020. № 2. Сложность алгоритмов, алгоритмы сортировки, рекурсивные алгоритмы

Развернуть

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

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

Действия