Материалы

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

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

Часть 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. Принципы блочного шифрования; криптографическая функция сжатия

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

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

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

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

18. Метрика Хэмминга; принцип Locality Sensitive Hashing и его применения для поиска данных

19. Вдумчивые и конструктивные замечания по содержанию курса

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

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

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

• Конспект.

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

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

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

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

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

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

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