Булах Дмитрий Александрович
к.т.н., доцент кафедры ПКИМС

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

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

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

План курса:

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

Лекция Рассматриваемые вопросы Презентация PDF Задания для СРС

Лекция 1

Общие сведения об алгоритмах

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


PDF

PDF

PDF

Лекция 2

Основные способы организации данных

Дискретные, линейные, нелинейные структуры данных. Списочные структуры данных. Матрицы и обработка матриц. Хеши. Деревья.


PDF
PDF

PDF

Лекция 3

Обработка линейных структур данных

Алгоритмы сортировки линейных структур данных. Алгоритмы сортировки вставками, выбором, обменом, слиянием, быстрая (Хоара), блочная сортировка, сортировка подсчётом. Поиск грубой силой, КМП-поиск, поиск по бору.


PDF
PDF

PDF

Лекция 4

Графы. Общие сведения.

Общие сведения о графах, способы представления графов, простейшие алгоритмы на графах: Дейкстра, Флойд, Краскал.


PDF
PDF

PDF

Лекция 5

Основы алгоритмов компрессии данных

Потоковые и блочные алгоритмы сжатия, однопроходные и многопроходные алгоритмы сжатия. 7-битное кодирование. RLE, Huffman, LZW, BWT.


PDF
PDF

PDF

Лекция 6

Подходы к защите данных

Классификация и основы построения алгоритмов шифрования данных.


PDF
PDF

PDF

Лекция 7

Кодирование информации

Алгоритмы кодирования. Корректирующие коды.
PDF
PDF

PDF

Лекция 8

Вероятностные и эвристические алгоритмы

Алгоритмы, построенные на основе эвристик и вероятностных методов: генетический алгоритм, алгоритм работы нейронных сетей, муравьиные алгоритмы, алгоритм моделирования отжига.


PDF
PDF

PDF

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

Лабораторная работа Рассматриваемые вопросы Материалы

Лабораторная работа №1

Основы работы в MS Visual Studio.

Создание проекта, редактирование программного кода, компиляция и сборка проекта, работа с отладчиком. Измерение времени работы программного кода. Работа с консолью, циклами, одномерными массивами.

PDFЗадания для ЭН-24
PDFЗадания для ЭН-25

Лабораторная работа №2

Основы работы с контейнерами STL

Оценка производительности контейнеров std::vector, основные операции с контейнером. Реализация и оценка производительности алгоритмов сортировки.

PDFЗадания для ЭН-24,25

Лабораторная работа №3

Обработка одномерных массивов

Обработка одномерных массивов на примере написания интерпретаторов подмножества языка Brainfuck. Чтение текстовых файлов.

PDFЗадания для ЭН-24
PDFЗадания для ЭН-25

Лабораторная работа №4

Обработка матричных структур данных

Обработка матричных структур данных на примере реализации простого клеточного автомата.

PDFЗадания для ЭН-24
PDFЗадания для ЭН-25

Ваши преподаватели

Лектор

Дмитрий Булах
Булах Дмитрий Александрович

к.т.н., доцент кафедры ПКИМС


Рекомендуемая литература

Клик по обложке - переход к файлообменнику

...
Роберт Седжвик
Фундаментальные алгоритмы на C++. Части 1-4. Анализ. Структуры данных. Сортировка. Поиск.

...
Роберт Седжвик
Фундаментальные алгоритмы на C++. Часть 5. Алгоритмы на графах.

...
А. Ахо,
Дж. Хопкрофт,
Дж. Ульман
Структуры данных и алгоритмы.