Course: 3

Semester: 5

Subject: Analysis of algorithms

Done all labs

Лабораторная 1: расстояние Левенштейна и Дамерау-Левенштейна

Целью данной лабораторной работы является применение навыков динамического программирования в алгоритмах поиска расстояний Левенштейна и Дамерау-Левенштейн

В рамках выполнения работы необходимо решить следующие задачи:

1. изучить расстояния Левенштейна и Дамерау-Левенштейна;
2. разработать алгоритмы поиска этих расстояний;
3. реализовать разработанные алгоритмы;
4. провести сравнительный анализ процессорного времени выполнения реализаций этих алгоритмов;
5. провести сравнительный анализ затрачиваемой реализованными алгоритмами пиковой памяти

Лабораторная 2: Алгоритмы умножения матриц

Целью данной лабораторной работы является изучение способов оптимизации алгоритмов на примере алгоритмов умножения матриц

В рамках выполнения работы необходимо решить следующие задачи:

1. изучить алгоритмы умножения матриц;
2. разработать и реализовать 3 алгоритма умножения матриц: стандартный, Винограда и Винограда с оптимизациями;
3. оценить трудоемкость реализаций алгоритмов;
4. провести сравнительный анализ процессорного времени выполнения реализаций алгоритмов.

Лабораторная 3: Алгоритмы сортировки

Целью данной лабораторной работы является получение навыков оценки трудоемкости алгоритмов на примере трех алгоритмов сортировок

В рамках выполнения работы необходимо решить следующие задачи:

1. изучить три алгоритма сортировок: сортировку вставками, сортировку пузырьком и шейкерную сортировку;
2. разработать и реализовать изученные алгоритмы;
3. провести сравнительный анализ трудоёмкости реализаций алгоритмов на основе теоретических расчетов;
4. провести сравнительный анализ процессорного времени выполнения реализаций алгоритмов на основе экспериментальных данных.

Лабораторная 4: Параллельное программирование

Целью данной работы является изучение организации параллельных вычислений на базе алгоритма трассировки лучей.

В рамках выполнения работы необходимо решить следующие задачи:

1. изучить основы параллельных вычислений;
2. изучить алгоритм трассировки лучей;
3. разработать параллельную версию алгоритма трассировки лучей;
4. реализовать последовательную и параллельную трассировку лучей;
5. провести сравнительный анализ времени работы реализаций.

Лабораторная 5: Конвейерная обработка данных

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

В рамках выполнения работы необходимо решить следующие задачи:

1. изучить основы конвейеризации;
2. изучить алгоритм стандартизации;
3. разработать параллельную версию конвейера для стандартизации с 3 стадиями обработки;
4. реализовать линейный и параллельный конвейерный варианты стандартизации;
5. собрать статистику времени обработки заявок конвейром;
6. провести сравнительный анализ времени работы реализаций.

Лабораторная 6: Муравьиный алгоритм

Целью данной работы является реализация муравьиного алгоритма для решения задачи коммивояжера и приобретение навыков параметризации алгоритмов.

В рамках выполнения работы необходимо решить следующие задачи:

1. реализовать алгоритм полного перебора для решения задачи коммивояжера;
2. изучить и реализовать муравьиный алгоритм для решения задачи коммивояжера;
3. провести параметризацию муравьиного алгоритма на трех классах данных и подобрать оптимальные параметры;
4. провести сравнительный анализ времени выполнения и трудоемкостей реализаций.

Лабораторная 7: Алгоритмы поиска в словаре

Целью данной работы является разработка эффективного алгоритма поиска по словаре.

В рамках выполнения работы необходимо решить следующие задачи:

1. изучить три алгоритма поиска в словаре: алгоритм полного перебора, алгоритм бинарного поиска и алгоритм поиска в сегментированном словаре;
2. разработать и реализовать изученные алгоритмы;
3. провести сравнительный анализ трудоёмкости реализаций алгоритмов на основе теоретических расчетов (в среднем; в лучшем и худшем случаях);
4. провести сравнительный анализ процессорного времени выполнения реализаций алгоритмов на основе экспериментальных данных;
5. провести сравнительный анализ количества сравнений с заданным ключом, необходимых для поиска каждым алгоритмом значения по ключу и для определения отсутствия заданного ключа в словаре.

Домашнее задание

Построение графа и истории по данным и по операциям (сортировка)