Перейти к содержанию

Главная#

ALG#

Pied Piper

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

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

Ссылка на презентации

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

Объявления:#

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

Индивидуальные темы
  1. Программа-демонстратор алгоритмов сортировки массивов
  2. Маргаритковый мир
  3. Генератор лабиринтов алгоритмом Эйлера
  4. Генератор лабиринтов на основе алгоритма Краскала (или Прима)
  5. Генерация лабиринта на основе случайного поиска в глубину
  6. Генераторы простых чисел (решето Эратосфера)
  7. Программа-демонстратор алгоритма поиска А*
  8. Муравьиный алгоритм и его применение (предлагается для поиска оптимального маршрута)
  9. K-d-дерево (для индексации точек)
  10. Алгоритмы решения задачи о рюкзаке
  11. Генерация карты высот на основе шума Прима
  12. Генерация высот алгоритмом Diamond-Square
  13. Решение задачи коммиявояжера методом отжига на реальных данных
  14. Алгоритм решения задачи заливки однородной области (обход в ширину)
  15. Алгоритм решения задачи сборки кубика-рубика
  16. Алгоритм решения пятнашек
  17. Алгоритм Минимакс (на примере игры крестики-нолики)
  18. Поиск минимального отсуствующего числа
  19. Гравитационная задача N-тел
  20. Алгоритм трассировки лучей (2D-реализация)

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

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

Диф. зачет#

Warning

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

Даты приема 19, 26 мая. К этим датам у вас должны быть сданы Лабораторные работы в нужном количестве. С собой зачетку.

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

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

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

  • Сможете рассказать в виде краткого обзора про алгоритмические стратегии: Методы «грубой силы», Жадные алгоритмы, Численные алгоритмы, Алгоритмы с возвратом, Эвристические алгоритмы (отдельно Муравьиные алгоритмы, Генетические алгоритмы)

  • Сформировали навык оценки алгоритмов по скорости работы (асимптотический анализ)

  • Сформировали навык оценки ресурса параллелизма алгоритмов (видеть, какие участки кода можно потенциально распарареллить)

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

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