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

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

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

План курса:

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

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

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

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

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

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

УДАЛЁННОЕ ВЫПОЛНЕНИЕ И СДАЧА ЛАБОРАТОРНОЙ РАБОТЫ

Важная информация для тех, кто сидит на карантине!

Для виртуального присутствия на лабораторной работе воспользуйтесь Zoom.

Ссылка: https://us02web.zoom.us/j/4079826884?pwd=TTJ4ZjVaNi9GaGxjSkpGNzYxMFVDUT09

Идентификатор конференции: 407 982 6884
Код доступа: 035630

Эту же сылку нужно использовать, если вы хотите сдавать лабораторные работы через Zoom. Кто хочет через TeamViewer - сдаёт через TeamViewer.

Контакты для связи со мной:

ВКонтакте: https://vk.com/id11730524 (предпочтительный вариант)
Почта: dima@pkims.ru (в обычном режиме проверяю пару раз в день)

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

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

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

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