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

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

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

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

План курса:

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

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

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


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

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

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

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

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

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

Лекция 1

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

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

Лекция 2

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

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

Лекция 3

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

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

Лекция 4

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

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

Для тех, кто хочет попробовать себя в приближенном к настоящему программировании, выкладываю более-менее боевой пример
PDF
PDF

Лекция 5

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

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

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

Лабораторная работа Рассматриваемые вопросы Задания
ЭН-24		 Задания
ЭН-25

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

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

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

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

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

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

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

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

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

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

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

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

Лектор

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

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

Помогают на лабораторных работах


УспеваемостьОбновлено
20 октября 2025
PDF
Журнал группы ЭН-24
PDF
Журнал группы ЭН-25
PDF
Правила распределения
баллов
PDF
Как читать журнал успеваемости

Итоговая аттестация

Вопросы появятся ближе к зачёту

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

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

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