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

Для программы «Математика и компьютерные науки»

Материалы

Материалы лекций

  1. Слайды: Кэширование
  2. Слайды: Рандомизация
  3. Слайды: Алгоритмы сжатия
  4. Блокнот: Реляционные БД и ORM
  5. Слайды: Производительность обработки данных, распределённые СУБД, NoSQL Movement
  6. Слайды: Виды нереляционных СУБД
  7. Слайды: Техники и паттерны распределённого хранения данных и программирования
  8. Слайды: Консенсус, CAP, PACELC
  9. Слайды: Вебграфы
  10. Слайды: И снова хэш-функции
  11. Слайды: И снова нечёткое хэширование

Задания и примеры

Опубликованы здесь

Темы практических занятий

  1. Немного о кэшировании и моделировании кэширования

  2. Рандомизация:

    • точность и производительность метода Монте-Карло
    • случайные базисы в многомерных пространствах
    • повышение точности измерений
    • случайные деревья
    • вероятностная проверка на простоту

  3. Примеры реализации алгоритмов сжатия

  4. Berkeley DB: индексация и доступ к данным

  5. Locality Sensitive Hashing

Вопросы к экзамену, осень 2024

Часть I

  1. Собственные свойства и количественные показатели работы кэшей
  2. Принцип Белади, тривиальные стратегии вытеснения; аномалия Белади; Cache-obvious алгоритмы
  3. Вариации стратегии LRU; мемоизация
  4. Splay-дерево, T-дерево
  5. Что такое и зачем могут пригодиться субоптимальные решения; методы Монте-Карло и Лас-Вегаса
  6. Тасование Фишера-Йетса: оригинальное описание; алгоритм Дюрштенфельда
  7. Формулировка и смысл теоремы Котельникова
  8. Принцип Compressive Sensing
  9. Повышение точности при помощи рандомизации с примером
  10. Способы рандомизированного поиска пути между препятствиями; Random Tree, Rapidly Exploring Random Tree
  11. Муравьиные алгоритмы
  12. Вероятностные тесты на простоту: где и зачем нужны; тесты Ферма и Соловея-Штрассена
  13. Понятие информационной энтропии
  14. Код Шеннона и алгоритм Хаффмана
  15. Идея и алгоритм арифметического кодирования
  16. Происхождение, принцип и области применения сжатия RLE
  17. Алгоритмы сжатия LZW
  18. Прямое и обратное преобразование Барроуза-Вилера
  19. Закон Мура в 1960-е и сейчас, закон Амдала; топологии распределённых вычислителей и решаемых ими задач

Часть II

  1. Предпосылки NoSQL и фактическое значение этого термина
  2. Принципы ACID, BASE; сильная согласованность в конечном счёте
  3. Графовые и дедуктивные СУБД; документоориентированные СУБД
  4. СУБД типа ключ-значение; колоночные СУБД
  5. Map-Reduce, Map-Reduce-Combine; пример на какой-нибудь документоориентированной СУБД
  6. Устройства кластерных файловых систем, импорт данных
  7. Page Rank, как пример задачи на Вебграфе; Google Matrix и Pregel
  8. Понятие распределённого консенсуса; протоколы PAXOS и RAFT
  9. Теоремы CAP и PACELC
  10. Универсальные и совершенные хэш-функции, совершенные хэш-таблицы
  11. Принципы блочного шифрования; криптографическая функция сжатия
  12. Принципы и примеры хэш-функций класса Меркла-Дамгора; атака удлиннением сообщения
  13. Принципы и примеры хэш-функций класса Keccak
  14. Принципы и примеры хэш-функций класса SWIFFT
  15. Мера Жаккара; принципы MinHash, SimHash и фильтра Блума; оценка их точности
  16. Метрика Хэмминга; принцип Locality Sensitive Hashing и его применения для поиска данных
  17. Количественный анализ вебграфов с использованием моделей Барабаши-Альберт и Боллобаша-Риордана
  18. Количественный анализ вебграфов с использованием моделей Бакли-Остгуса и копирования
  19. Вдумчивые и конструктивные замечания по содержанию курса

Темы для докладов и мастер-классов

  1. Количественные измерения работы кэшей разных размеров с разными стратегиями для известных алгоритмов — самостоятельно или с использованием Mimircache
    • При кэшировании результатов части реализованных функций
    • При кэшировании результатов доступа к массиву (имитация работы ОЗУ)
  2. Деревья RRT*
  3. Язык Julia
  4. Compressive Sensing — испытание доработанных примеров: посоревнуйтесь в сжатии с JPEG (на последнем этапе можно дополнительно округлить числа с плавающей запятой и использовать архиваторы)
  5. Соревнование в генерации и проверке простых чисел — практически любыми способами
  6. Демо: иллюстрация работы муравьиных алгоритмов и решаемых задач
  7. Доклад по истории алгоритмов сжатия и про один из алгоритмов, не описанных на лекции, можно основываясь на этом метариале
  8. Доклад: организация эффективного хранения ключей и данных произвольной длины в Berkeley DB
  9. Демо: корректный бенчмарк Berkeley DB: HASH vs BTREE

Информационные источники

Рекомендованные онлайн-курсы

Список литературы и не литературы

Note

Эта страница доступна на старом сайте