02.03.01, СВ.5001 Математика и компьютерные науки
Команда в Microsoft Teams → чат Microsoft Teams (или код команды 9zw6j8j)
Слайды: Кэширование
Слайды: Рандомизация
Слайды: Алгоритмы сжатия
Блокнот: Реляционные БД и ORM
Слайды: Производительность обработки данных, распределённые СУБД, NoSQL Movement
Слайды: Виды нереляционных СУБД
Слайды: Техники и паттерны распределённого хранения данных и программирования
Слайды: Консенсус, CAP, PACELC
Слайды: Вебграфы
Слайды: И снова хэш-функции
Слайды: И снова нечёткое хэширование
Опубликованы здесь
Немного о кэшировании и моделировании кэширования
Рандомизация:
точность и производительность метода Монте-Карло
случайные базисы в многомерных пространствах
повышение точности измерений
случайные деревья
вероятностная проверка на простоту
Примеры реализации алгоритмов сжатия
Berkeley DB: индексация и доступ к данным
Locality Sensitive Hashing
Собственные свойства и количественные показатели работы кэшей
Принцип Белади, тривиальные стратегии вытеснения; аномалия Белади; Cache-obvious алгоритмы
Вариации стратегии LRU; мемоизация
Splay-дерево, T-дерево
Что такое и зачем могут пригодиться субоптимальные решения; методы Монте-Карло и Лас-Вегаса
Тасование Фишера-Йетса: оригинальное описание; алгоритм Дюрштенфельда
Формулировка и смысл теоремы Котельникова
Принцип Compressive Sensing
Повышение точности при помощи рандомизации с примером
Способы рандомизированного поиска пути между препятствиями; Random Tree, Rapidly Exploring Random Tree
Муравьиные алгоритмы
Вероятностные тесты на простоту: где и зачем нужны; тесты Ферма и Соловея-Штрассена
Понятие информационной энтропии
Код Шеннона и алгоритм Хаффмана
Идея и алгоритм арифметического кодирования
Происхождение, принцип и области применения сжатия RLE
Алгоритмы сжатия LZW
Прямое и обратное преобразование Барроуза-Вилера
Закон Мура в 1960-е и сейчас, закон Амдала; топологии распределённых вычислителей и решаемых ими зада/
Предпосылки NoSQL и фактическое значение этого термина
Принципы ACID, BASE; сильная согласованность в конечном счёте
Графовые и дедуктивные СУБД; документоориентированные СУБД
СУБД типа ключ-значение; колоночные СУБД
Map-Reduce, Map-Reduce-Combine; пример на какой-нибудь документоориентированной СУБД
Устройства кластерных файловых систем, импорт данных
Page Rank, как пример задачи на Вебграфе; Google Matrix и Pregel
Понятие распределённого консенсуса; протоколы PAXOS и RAFT
Теоремы CAP и PACELC
Универсальные и совершенные хэш-функции, совершенные хэш-таблицы
Принципы блочного шифрования; криптографическая функция сжатия
Принципы и примеры хэш-функций класса Меркла-Дамгора; атака удлиннением сообщения
Принципы и примеры хэш-функций класса Keccak
Принципы и примеры хэш-функций класса SWIFFT
Мера Жаккара; принципы MinHash, SimHash и фильтра Блума; оценка их точности
Метрика Хэмминга; принцип Locality Sensitive Hashing и его применения для поиска данных
Количественный анализ вебграфов с использованием моделей Барабаши-Альберт и Боллобаша–Риордана
Количественный анализ вебграфов с использованием моделей Бакли-Остгуса и копирования
Вдумчивые и конструктивные замечания по содержанию курса
Количественные измерения работы кэшей разных размеров с разными стратегиями для известных алгоритмов — самостоятельно или с использованием Mimircache
При кэшировании результатов части реализованных функций
При кэшировании результатов доступа к массиву (имитация работы ОЗУ)
Деревья RRT*
Язык Julia
Compressive Sensing — испытание доработанных примеров: посоревнуйтесь в сжатии с JPEG (на последнем этапе можно дополнительно округлить числа с плавающей запятой и использовать архиваторы)
Соревнование в генерации и проверке простых чисел — практически любыми способами
Демо: иллюстрация работы муравьиных алгоритмов и решаемых задач
Доклад по истории алгоритмов сжатия и про один из алгоритмов, не описанных на лекции, можно основываясь на этом метариале
Доклад: организация эффективного хранения ключей и данных произвольной длины в Berkeley DB
Демо: корректный бенчмарк 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 с.
Кузнецов С. Д. Методы сортировки и поиска. ИСП РАН, Центр Информационных Технологий.
Материалы лектора: приложение к данной странице; кому-то может показаться, что это лучше, чем ничего.