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

02.03.01, СВ.5001 Математика и компьютерные науки

Материалы

Мультимедиа

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

  1. Слайды: Кэширование

  2. Слайды: Рандомизация

  3. Слайды: Алгоритмы сжатия

  4. Блокнот: Реляционные БД и ORM

  5. Слайды: Производительность обработки данных, распределённые СУБД, NoSQL Movement

  6. Слайды: Виды нереляционных СУБД

  7. Слайды: Техники и паттерны распределённого хранения данных и программирования

  8. Слайды: Консенсус, CAP, PACELC

  9. Слайды: Вебграфы

  10. Слайды: И снова хэш-функции

  11. Слайды: И снова нечёткое хэширование

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

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

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

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

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

    1. точность и производительность метода Монте-Карло

    2. случайные базисы в многомерных пространствах

    3. повышение точности измерений

    4. случайные деревья

    5. вероятностная проверка на простоту

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

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

  5. Locality Sensitive Hashing

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

Часть I

  1. Собственные свойства и количественные показатели работы кэшей

  2. Принцип Белади, тривиальные стратегии вытеснения

  3. Аномалия Белади; Cache-obvious алгоритмы

  4. Вариации стратегии LRU; мемоизация

  5. Splay-дерево, T-дерево

  6. Что такое и зачем могут пригодиться субоптимальные решения

  7. Тасование Фишера-Йетса: оригинальное описание; алгоритм Дюрштенфельда

  8. Принцип Compressive Sensing

  9. Формулировка и смысл теоремы Котельникова

  10. Повышение точности при помощи рандомизации с примером

  11. Способы рандомизированного поиска пути между препятствиями

  12. Random Tree, Rapidly Exploring Random Tree

  13. Муравьиные алгоритмы

  14. Вероятностные тесты на простоту: где и зачем нужны; тесты Ферма и Соловея-Штрассена

  15. Понятие информационной энтропии

  16. Код Шеннона и алгоритм Хаффмана

  17. Идея и алгоритм арифметического кодирования

  18. Происхождение, принцип и области применения сжатия RLE

  19. Алгоритмы сжатия LZW

  20. Прямое и обратное преобразование Барроуза-Вилера

Часть II

  1. Закон Мура в 1960-е и сейчас, закон Амдала; топологии распределённых вычислителей и решаемых ими задач

  2. Предпосылки NoSQL и фактическое значение этого термина

  3. Принципы ACID, BASE; сильная согласованность в конечном счёте

  4. Графовые и дедуктивные СУБД; документоориентированные СУБД

  5. СУБД типа ключ-значение; колоночные СУБД

  6. Map-Reduce, Map-Reduce-Combine; пример на какой-нибудь документоориентированной СУБД

  7. Устройства кластерных файловых систем, импорт данных

  8. Page Rank, как пример задачи на Вебграфе; Google Matrix и Pregel

  9. Понятие распределённого консенсуса; протоколы PAXOS и RAFT

  10. Теоремы CAP и PACELC

  11. Количественный анализ вебграфов с использованием моделей Барабаши-Альберт и Боллобаша–Риордана

  12. Количественный анализ вебграфов с использованием моделей Бакли-Остгуса и копирования

  13. Универсальные и совершенные хэш-функции, совершенные хэш-таблицы

  14. Принципы блочного шифрования; криптографическая функция сжатия

  15. Принципы и примеры хэш-функций класса Меркла-Дамгора; атака удлиннением сообщения

  16. Принципы и примеры хэш-функций класса Keccak

  17. Принципы и примеры хэш-функций класса SWIFFT

  18. Мера Жаккара и метрика Хэмминга

  19. Принципы MinHash, SimHash и фильтра Блума; оценка их точности

  20. Принцип Locality Sensitive Hashing и его применения для поиска данных

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

  1. Количественные измерения работы кэшей разных размеров с разными стратегиями для известных алгоритмов — самостоятельно или с использованием Mimircache

    1. При кэшировании результатов части реализованных функций

    2. При кэшировании результатов доступа к массиву (имитация работы ОЗУ)

  2. Деревья RRT*

  3. Язык Julia

  4. Compressive Sensing — испытание доработанных примеров: посоревнуйтесь в сжатии с JPEG (на последнем этапе можно дополнительно округлить числа с плавающей запятой и использовать архиваторы)

  5. Соревнование в генерации и проверке простых чисел — практически любыми способами

  6. Демо: иллюстрация работы муравьиных алгоритмов и решаемых задач

  7. Доклад по истории алгоритмов сжатия и про один из алгоритмов, не описанных на лекции, можно основываясь на этом метариале

  8. Доклад: организация эффективного хранения ключей и данных произвольной длины в Berkeley DB

  9. Демо: корректный бенчмарк Berkeley DB: HASH vs BTREE

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

  • На все семестры Data Structures and Algorithms University of California San Diego; National Research University Higher School of Economics

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

  • Конспект.

  • Дж. Д. Ульман А. В. Ахо, Дж. Э. Хопкрофт. Структуры данных и алгоритмы. Издательский дом «Вильямс», 2000.

  • Дональд Э. Кнут. Искусство Программирования. Издательский дом «Вильямс», 2000.

  • Томас Кормен, Чарльз Лейзерсон, Рональд Ривест. Алгоритмы: построение и анализ. М.: МЦНМО, 1999.

  • Кубенский А. А. Структуры и алгоритмы обработки данных. Объектно-ориентированный подход и реализация на C++. СПб.: БХВ-Петербург, 2004.

  • Тоби Сегаран. Программируем коллективный разум: [пер. с англ.] // М. — Символ-Плюс, 2008, 368 с.

  • Кузнецов С. Д. Методы сортировки и поиска. ИСП РАН, Центр Информационных Технологий.

  • Материалы лектора: приложение к данной странице; кому-то может показаться, что это лучше, чем ничего.