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

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

Материалы

Мультимедиа

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  2. Деревья RRT*

  3. Язык Julia

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

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

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

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

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

Часть I

  1. ...

Часть II

  1. ...

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

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

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

  • Конспект.

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

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

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

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

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

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

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