Алгоритмы и структуры данныхSyllabus

Subject code

İFS-2226yn-RU

Credits

6

Student workload

2

Semester

Autumn semester

Academic year

2

Subject type

Elective

Form of education

Full-time

Language of instruction

Russian

In-class hours

a) 15 часов — лекция b) 15 часов – Семинар c) 15 часов —лаборатор. занятия

Out-of-class hours

a) 1 час – самостоятельная работа b) 1 час – консультационный час

Дисциплина «алгоритмы и структуры данных» изучает основные методы организации, хранения и эффективной обработки данных, а также принципы разработки алгоритмов для решения вычислительных задач. в рамках курса рассматриваются массивы, списки, стеки, очереди, деревья, графы, хеш-таблицы и другие структуры данных, а также алгоритмы поиска, сортировки, рекурсии и обработки графов. особое внимание уделяется анализу временной и пространственной сложности алгоритмов с использованием нотации big o, сравнению различных подходов и выбору эффективных алгоритмов для решения практических задач. дисциплина способствует развитию алгоритмического мышления, логики программирования и навыков эффективного решения сложных вычислительных задач.

• lecture
• seminar
• laboratory work

1. 1

   CLO 1: Объясняет и применяет основные понятия алгоритмов и структур данных, их свойства, классификацию и способы представления.

2. 2

   CLO 2: Разрабатывает и анализирует алгоритмы для решения поставленных задач, определяет их временную и пространственную сложность

3. 3

   CLO 3: Применяет и анализирует основные структуры данных, включая массивы, связанные списки, стеки, очереди, деревья, графы и хеш-таблицы

4. 4

   CLO 4:  разрабатывает и применяет основные алгоритмы поиска, сортировки, рекурсии, обработки деревьев и графов, сравнивает их эффективность.

5. 5

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

6. 6

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

1. 1.
   Введение в алгоритмы и структуры данных. алгоритмически неразрешимые задачиLecture

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

2. 2.
   Структуры данныхLecture

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

3. 3.
   Оптимизация и параллелизация алгоритмовLecture

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

4. 4.
   Подходы к построению алгоритмовLecture

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

5. 5.
   Алгоритмы сортировки и поискаLecture

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

6. 6.
   Жадные алгоритмы. динамическое программированиеLecture

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

7. 7.
   Алгоритмы на графах. алгоритмы поиска кратчайшего путиLecture

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

8. 8.
   Пошаговая демонстрация DFS и BFSLecture

   В рамках данной темы подробно изучаются алгоритмы обхода графов в глубину (dfs — depth-first search) и в ширину (bfs — breadth-first search). рассматривается пошаговый процесс выполнения каждого алгоритма, порядок посещения вершин, использование стеков и очередей, а также формирование дерева обхода. проводится практическая демонстрация работы DFS и BFS на различных графах и сравниваются области применения, преимущества и временная сложность данных алгоритмов.

1. Steven s. skiena – the algorithm design manual (springer, 3rd edition, 2020).
2. Robert sedgewick, kevin wayne – algorithms (addison-wesley, 4th edition, 2011)
3. Geeksforgeeks (https://www.geeksforgeeks.org/)