Алгоритмизация и программирование · МИИГАиК

Алгоритмизация и программирование

Лебедев Евгений Денисович, преподаватель кафедры информатики и геоинформационных технологий · lebedeved !собака! edu.miigaik.ru

1 О курсе

✉ Контакты

Преподаватель: Лебедев Евгений Денисович
Email: lebedeved !собака! edu.miigaik.ru

📚 Литература

Все учебные материалы и методические пособия: Открыть материалы ↗

📊 Презентации

Слайды к лекциям и практическим занятиям: Открыть презентации ↗

📈 Успеваемость

Таблица с оценками и результатами работ: Открыть таблицу ↗

2 Конспекты

Лекции

Лекция 1

Введение в асимптотический анализ

 Лекция 2

Асимптотический анализ. Рекурсивные функции

 Лекция 3

Арифметические основы вычислений

 Лекция 4

Введение в параллелизацию

 Лекция 5

Параллелизация на уровне данных

 Лекция 6

Оценка эффективности параллельных вычислений

 Лекция 7

Элементарные алгоритмы для работы с графами

 Лекция 8

Параллелизм графовых задач. Задача поиска кратчайшего маршрута

 Лекция 9

Модификации алгоритма Дейкстры. Дельта-шаг. Алгоритм A*

 Лекция 10

Задача коммивояжёра: подходы и решения

 Лекция 11

Эвристические алгоритмы

 Лекция 12

Обобщение алгоритмических стратегий

 Доп. глава

О различии техники

 Доп. глава

Введение в реверс-инжиниринг

 Доп. глава

Тренировка на покемонах (реверс-инжиниринг)

 Доп. глава

Задача коммивояжёра. Часть 1

 Доп. глава

Задача коммивояжёра. Часть 2. Эвристические алгоритмы. Метод отжига

Практики

Лабораторные работы и домашнее чтение указаны в карточке той практики, к которой они относятся, — это отдельные страницы.

Практика 1

Оценка скорости работы алгоритмов

ЛР 1 · Библиотечные реализации алгоритмов
Практика 2

Как люди придумывают алгоритмы?

ЛР 2 · Расчёт площади фигуры
Практика 3

Побитовые операторы и модулярная алгебра

Дом. чтение · Знакомство с PyGame
Практика 4

Алгоритмы численных приближений. Метод градиентного спуска

Практика 5

Методы оптимизации «Разделяй и властвуй»

Практика 6

Алгоритмы сортировки

ЛР 3 · Алгоритмы сортировки
Практика 7

Параллелизация. Быстрая сортировка

ЛР 4 · Знакомство с параллелизацией Дом. чтение · Numba: ускорение кода с JIT
Практика 8

Алгоритмы поиска с возвратом и обхода дерева

Практика 9

Деревья. Идея индексирования данных

Практика 10

Графы. Обход в ширину. Обход в глубину. Проверка связности

Практика 11

Задача о кратчайшем пути

ЛР 5 · Алгоритм поиска кратчайшего пути
Практика 12

Жадные алгоритмы. Алгоритм A*

ЛР 6 · Алгоритм A*
Практика 13

Эвристические алгоритмы. Метод отжига. Муравьиный алгоритм

ЛР 7 · Методы решения алгоритмических задач
Практика 14

Модель нейрона как эвристический алгоритм

Практика 15

Генетический алгоритм. Обучение с подкреплением

3 Индивидуальные темы

Список индивидуальных тем
  1. Программа-демонстратор алгоритмов сортировки массивов
  2. Маргаритковый мир
  3. Генератор лабиринтов алгоритмом Эйлера
  4. Генератор лабиринтов на основе алгоритма Краскала (или Прима)
  5. Генерация лабиринта на основе случайного поиска в глубину
  6. Генераторы простых чисел (решето Эратосфена)
  7. Программа-демонстратор алгоритма поиска A*
  8. Муравьиный алгоритм и его применение (предлагается для поиска оптимального маршрута)
  9. K-d-дерево (для индексации точек)
  10. Алгоритмы решения задачи о рюкзаке
  11. Генерация карты высот на основе шума Перлина
  12. Генерация высот алгоритмом Diamond-Square
  13. Решение задачи коммивояжёра методом отжига на реальных данных
  14. Алгоритм решения задачи заливки однородной области (обход в ширину)
  15. Алгоритм решения задачи сборки кубика Рубика
  16. Алгоритм решения пятнашек
  17. Алгоритм Минимакс (на примере игры крестики-нолики)
  18. Поиск минимального отсутствующего числа
  19. Гравитационная задача N тел
  20. Алгоритм трассировки лучей (2D-реализация)
  21. Псевдотонирование изображений (псевдотонирование Бёркеса)
  22. Построение минимальных выпуклых оболочек (алгоритм Грэхема)
  23. Алгоритм триангуляции Делоне методом заметающей прямой
  24. Программа-демонстратор папоротника Барнсли
  25. Программа-демонстратор множества Жюлиа
  26. Математические модели хаоса и их визуализация
  27. Модель сегрегации Шеллинга
  28. Решение задачи джерримендеринга для произвольного распределения
  29. Упрощение полилинии методом Дугласа-Пекера
  30. Алгоритмы моделирования транспортных потоков (энтропийный метод)
  31. Алгоритм сжатия JPEG2000
  32. Алгоритм Укконена
  33. Алгоритм шинглов
  34. Алгоритм решения задачи Иосифа Флавия в общем виде
  35. Алгоритм Тремо

Требования к проекту

  1. Презентация 10–20 слайдов
  2. Первый слайд — титульный лист: название проекта, группа, ФИО, предмет
  3. Второй слайд — постановка задачи: о чём ваша задача?
  4. Третий слайд — методы решения: перечисляете известные методы решения (названия методов / ссылки на конкретные алгоритмы / ссылки на иную литературу). Выбранный вами алгоритм / алгоритмы подчёркиваете жирным или цветным шрифтом
  5. Четвёртый слайд — средства реализации: язык программирования, версия языка программирования (для C++ — номер стандарта), версии использованных библиотек
  6. Пятый слайд — блок-схема алгоритма/алгоритмов, выбранных вами, или код наиболее важной функции. Блок-схема выполняется посредством ресурса programforyou
  7. Шестой слайд — описание интерфейса программы (даже если это консольное приложение): что на вход, как пользователю это ввести
  8. Седьмой слайд — демонстрация работы программы (предварительно записанное видео или гиф; рекомендуется гиф)
  9. Восьмой слайд — асимптотическая оценка предложенного алгоритма/алгоритмов, если это возможно
  10. Девятый слайд — замеры времени работы при разных данных. Оформляется таблицей
  11. Десятый слайд — заключительный комментарий. Выводы

Время выступления 10–20 минут. Обратите внимание, что некоторые пункты могут потребовать нескольких слайдов, поэтому разброс у каждого свой, но прошу придерживаться структуры! Вопросы по реализации проектов обсуждаются во время очных занятий. Поскольку мы с вами говорим о параллелизации, то, очевидно, такие работы выше ценятся независимо от выбранного языка программирования. Однако даже без неё вы можете получить максимальный балл. Начиная с апреля, я хотел бы начать слушать доклады.

4 Дифференцированный зачёт

⚠ Внимание

Кто будет пойман на генерации кода при помощи ИИ во время сдачи диф. зачёта, досрочно завершает попытку и отправляется на пересдачу в другой день. Если это последний день приёма, то студент уходит с долгом до осеннего семестра.

Даты приёма: 11, 12, 18, 19 июня. К этим датам у вас должны быть сданы лабораторные работы в нужном количестве. С собой зачётка.

При ответе на теоретические вопросы не разрешается пользоваться конспектами.

Билет состоит из 2 теоретических вопросов и 1 практического задания. Примеры практических заданий представлены в Лабораторной работе №7 «Методы решения алгоритмических задач». В случае предоставления неполного или некорректного решения задание может быть уточнено или заменено на дополнительное.

О чём был курс?

Считается, что из курса вы вынесете следующее:

  • Сможете рассказать в виде краткого обзора про алгоритмические стратегии: методы «грубой силы», жадные алгоритмы, численные алгоритмы, алгоритмы с возвратом, эвристические алгоритмы (отдельно муравьиные алгоритмы, генетические алгоритмы)
  • Сформировали навык оценки алгоритмов по скорости работы (асимптотический анализ)
  • Сформировали навык оценки ресурса параллелизма алгоритмов (видеть, какие участки кода можно потенциально распараллелить)
Вопросы к диф. зачёту
  1. Формализация понятия алгоритма. Опишите подходы к формализации понятия алгоритма: машину Тьюринга, нормальные алгоритмы Маркова, лямбда-исчисление Чёрча. Сформулируйте тезис Чёрча. Сформулируйте теорему о рекурсии.
  2. Асимптотический анализ. Опишите абстрактную модель вычислений. Перечислите вычислительные ресурсы. Раскройте идею асимптотического анализа алгоритмов. Что такое нотация big-O?
  3. Рекурсивные функции. Объясните, как вычисляется рекурсивная функция. Как выполняется асимптотический анализ рекурсивных алгоритмов? Опишите анализ рекуррентных соотношений. Сформулируйте мастер-теорему.
  4. Числа в памяти компьютера. Опишите представление чисел в памяти компьютера. Какие проблемы компьютерных вычислений вызваны использованием стандарта IEEE 754? Приведите примеры применения побитовых операторов.
  5. Параллелизация на уровне процессора. Раскройте основы параллелизации. Как устроена параллелизация на уровне процессора? Что такое векторные операции? Что такое интринсики?
  6. Параллелизация на уровне данных. Дайте определения процесса и потока. Опишите параллелизацию на уровне данных. В чём заключается проблема разделения ресурсов? Опишите задачу обедающих философов. Перечислите средства синхронизации.
  7. Численные приближения. Опишите алгоритмы численных приближений. Раскройте идею целочисленного интегрирования. Оцените ресурс параллелизации в алгоритмах численных приближений.
  8. «Разделяй и властвуй». Раскройте методы оптимизации «Разделяй и властвуй». Опишите бинарное возведение в степень. Опишите алгоритм Карацубы. Оцените ресурс параллелизации при реализации метода декомпозиции.
  9. Эффективность параллельных вычислений. Как оценивается эффективность параллельных вычислений? Опишите модель вычислений в виде графа «операции-операнды». Перечислите показатели эффективности параллельного алгоритма.
  10. Законы Амдала и Густавсона — Барсиса. Сформулируйте закон Амдала. Сформулируйте закон Густавсона — Барсиса. Приведите практические приложения закона Амдала.
  11. Параллельный Python. Как реализуются параллельные алгоритмы в Python? Что такое Global Interpreter Lock (GIL)? Перечислите готовые решения для многопоточных приложений в Python.
  12. Алгоритмы сортировки. Опишите алгоритмы сортировки. Выполните асимптотический анализ сортировки пузырьком, поразрядной сортировки и быстрой сортировки. Оцените ресурс параллелизации в алгоритме быстрой сортировки.
  13. Полный перебор. Раскройте метод полного перебора. Какие существуют методы оптимизации полного перебора? Опишите алгоритмы поиска с возвратом.
  14. Графовые задачи. Дайте определение графа. Перечислите виды графов. Как графы представляются в памяти? Приведите примеры графовых задач. Покажите, как граф используется в качестве инструмента научного анализа.
  15. Деревья. Дайте определение дерева. Опишите способы обхода деревьев. Что такое двоичная куча? Как выполняется поиск в двоичном дереве? Раскройте идею индексирования данных.
  16. Обходы графа. Дайте определение графа. Перечислите виды графов и способы представления графов в памяти. Опишите специализированные форматы хранения графов. Опишите поиск в глубину и поиск в ширину.
  17. Параллельный обход графа. Опишите специализированные форматы хранения графов. Как устроен параллельный поиск в ширину?
  18. Алгоритм Дейкстры: оптимизация. Раскройте идею динамического программирования. Сформулируйте задачу о кратчайшем пути. Опишите алгоритм Дейкстры. Оцените ресурс оптимизации алгоритма Дейкстры.
  19. Алгоритм Дейкстры: параллелизация. Раскройте идею динамического программирования. Сформулируйте задачу о кратчайшем пути. Опишите алгоритм Дейкстры. Оцените ресурс параллелизации алгоритма Дейкстры.
  20. Алгоритм Дельта-шага. Раскройте идею динамического программирования. Сформулируйте задачу о кратчайшем пути. Опишите алгоритм Дельта-шага. Оцените ресурс параллелизации алгоритма Дельта-шага.
  21. Жадные алгоритмы. Раскройте понятие жадного алгоритма. Сформулируйте задачу о рюкзаке. Приведите пример жадной оптимизации (алгоритм A*).
  22. Задача коммивояжёра. Сформулируйте задачу коммивояжёра. Разберите решения: метод грубой силы (полный перебор), динамическое программирование, жадный алгоритм.
  23. Метод ветвей и границ. Опишите поиск с возвратом и метод ветвей и границ. Сформулируйте задачу коммивояжёра. Как эвристики используются для оптимизации перебора (алгоритм Литтла)?
  24. Имитация отжига. Раскройте понятие эвристического алгоритма. Опишите алгоритм имитации отжига. Приведите примеры использования алгоритма имитации отжига.
  25. Генетический алгоритм. Раскройте понятие эвристического алгоритма. Опишите генетический алгоритм. Приведите примеры использования генетического алгоритма.
  26. Муравьиный алгоритм. Раскройте понятие эвристического алгоритма. Опишите муравьиный алгоритм. Приведите примеры использования муравьиного алгоритма.
  27. Алгоритмически неразрешимые задачи. Опишите подходы к формализации понятия алгоритма. Раскройте лямбда-исчисление Чёрча. Сформулируйте тезис Чёрча. Приведите примеры алгоритмически неразрешимых задач.
  28. Средства синхронизации. Раскройте основы параллелизации. Опишите средства синхронизации и их реализацию: атомарные переменные, мьютексы, семафоры.
Навигация
Лекции
Практики
Лабораторные работы
Содержание