Курс "Теория алгоритмов"

Теория алгоритмов

Курс "Теория алгоритмов" читается студентам 2 курса института ИнЭл, обучающиимся по профилю "Автоматизация проектирования изделий наноэлектроники" (группы ЭН-24, ЭН-25), в третьем (осеннем) семестре.

План курса:

8 лекций;
4 лабораторные работы.

К лекциям предусмотрена самостоятельная работа.

Изучение дисцины "Теория алгоритмов" заканчивается зачётом с оценкой.

КРАТКАЯ АННТОАЦИЯ

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

В рамках лабораторных работ я ставлю своей целью поддержание знаний основ программирования, полученных студентами в процессе обучения преподавателями кафедры ИПОВС, а также их развитие и углубление в сторону, специфичную для нашей кафедры, что, несомненно, пригодится в дальнейшем.

Материалы к лекциям

Лекция	Рассматриваемые вопросы	Презентация PDF	Задания для СРС
Лекция 1 Общие сведения об алгоритмах	Определение термина "алгоритм". Основные свойства алгоритмов и формы их записи. Классфификация алгоритмов с точки зрения последовательности исполнения и принципа работы, парадигмы разработки алгоритмов. Понятие сложности алгоритма.
Лекция 2 Основные способы организации данных	Дискретные, линейные, нелинейные структуры данных. Списочные структуры данных. Матрицы и обработка матриц. Хеши. Деревья.
Лекция 3 Обработка линейных структур данных	Алгоритмы обработки линейных структур данных. Алгоритмы сортировки вставками, выбором, обменом, слиянием, быстрая (Хоара), блочная сортировка, сортировка подсчётом. Поиск грубой силой, КМП-поиск, поиск по бору.
Лекция 4 Графы. Общие сведения.	Общие сведения о графах, способы представления графов, простейшие алгоритмы на графах: Дейкстра, Флойд, Краскал.
Лекция 5 Основы алгоритмов компрессии данных	Потоковые и блочные алгоритмы сжатия, однопроходные и многопроходные алгоритмы сжатия. 7-битное кодирование. RLE, Huffman, LZW, BWT.
Лекция 6 Подходы к защите данных	Классификация и основы построения алгоритмов шифрования данных.
Лекция 7 Кодирование информации	Алгоритмы кодирования. URL-кодирование. Base64. Контрольные коды: CRC8. Корректирующие коды. Коды Хэмминга.
Лекция 8 Вероятностные и эвристические алгоритмы	Алгоритмы, построенные на основе эвристик и вероятностных методов: генетический алгоритм, алгоритм работы нейронных сетей, муравьиные алгоритмы, алгоритм моделирования отжига.

Тематика лабораторных работ

Лабораторная работа	Рассматриваемые вопросы	Задания ЭН-24	Задания ЭН-25
Лабораторная работа №1 Основы работы в MS Visual Studio.	Создание проекта, редактирование программного кода, компиляция и сборка проекта, работа с отладчиком. Измерение времени работы программного кода. Требования: ввод/вывод, переменные, условия, циклы, массивы.	Задания для ЭН-24	Задания для ЭН-25
Лабораторная работа №2 Основы работы с контейнерами STL	Оценка производительности контейнеров std::vector, основные операции с контейнером. Реализация и оценка производительности алгоритмов сортировки. Требования: динамические масивы, ввод/вывод ANSI C и C++, циклы.	Задания для ЭН-24	Задания для ЭН-25
Лабораторная работа №3 Обработка одномерных массивов	Обработка одномерных массивов на примере написания интерпретаторов подмножества языка Brainfuck. Чтение текстовых файлов. Требования: чтение текстовых файлов, ввод/вывод, циклы, оператор switch, массивы.	Задания для ЭН-24	Задания для ЭН-25
Лабораторная работа №4 Обработка матричных структур данных	Обработка матричных структур данных на примере реализации простого клеточного автомата. Требования: матрицы, ввод/вывод, циклы, оператор switch.	Задания для ЭН-24	Задания для ЭН-25