Construction and Analysis of Algorithms

Краткое содержание учебной дисциплины, модуля / Brief summary

Раздел 1. Структуры данных и сложность алгоритмов (Структуры данных. Стеки, очереди, связанные списки, бинарные деревья. Алгоритмы поиска подстроки в строке: прямой, Рабина-Карпа, конечный автомат, Кнута-Морриса-Пратта. Алгоритмы поиска и выборки. Бинарный поиск. Интерполяционный поиск. Деревья бинарного поиска. Сбалансированные деревья. Операции над деревьями. Хеширование. Открытая и закрытая адресация. Первичные и вторичные хеш-функции. Детерминированные и недетерминированные машины Тьюринга. Клеточные автоматы)

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

Раздел 3. Основные алгоритмические стратегии (Эвристики и метаэвристики. Алгоритмы локального поиска, поиска с запретами. Генетические алгоритмы, алгоритмы имитации отжига. Алгоритмы полного перебора, метод ветвей и границ. Динамическое программирование и метод «разделяй и властвуй». Понятие о методах динамического программирования и «разделяй и властвуй»)

Section 1. Data structures and complexity of algorithms (Data structures. Stacks, queues, linked lists, binary trees. Algorithms for searching a substring in a string: direct, Rabin-Karp algorithm, finite automaton, Knuth-Morris-Pratt algorithm. Search and selection algorithms. Binary search Interpolation search, Balanced trees, Hashing, Primary and secondary hash functions.

Section 2. Algorithms on graphs (Searching for the minimum spanning tree and the shortest path in a graph. Algorithm for finding an Eulerian cycle. Matching in bipartite graphs, augmenting chain method)

Section 3. Basic algorithmic strategies (Heuristics and metaheuristics. Local search algorithms, tabu search. Genetic algorithms, simulated annealing algorithms. Brute force algorithms, branch and bound method. Dynamic programming and the divide and conquer method. The concept of dynamic programming methods and “divide and conquer”)

Формируемые компетенции / The formed competences

СК-5. Применять основные понятия, утверждения и методы для решения базовых задач дискретной математики

SC-5. Apply basic concepts, statements, and methods to solve basic problems in discrete mathematics

Результаты обучения (знать, уметь, владеть) / Learning outcomes (know, can, be able)

Знать: 

принципы оценки комбинаторных алгоритмов;

наиболее распространенные оценки алгоритмов;

структуры данных, используемые при оценке алгоритмов;

приемы исчерпывающего поиска;

приемы декомпозиции;

понятия полиномиальной разрешимой и NP-полной задач;

списки наиболее распространенных NP-полных задач;

Уметь: 

определять трудоемкость алгоритмов;

применять структуры данных для построения алгоритмов;

использовать поиск с возвращением для построения алгоритмов;

использовать принцип «разделяй и властвуй» для декомпозиции задач;

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

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

разрабатывать эффективные алгоритмы поиска в графах;

Владеть: 

методами создания и реализации структур данных;

методами оценки трудоемкости алгоритмов;

подходами к решению алгоритмических задач на основе известных алгоритмических стратегий.

Know: 

principles of evaluating combinatorial algorithms;

most common algorithm evaluations;

data structures used in evaluating algorithms;

exhaustive search techniques;

decomposition techniques;

concepts of polynomial solvable and NP-complete problems;

lists of the most common NP-complete problems;

Can: 

determine the complexity of algorithms;

apply data structures to build algorithms;

use backtracking to build algorithms;

use the divide and conquer principle to decompose tasks;

develop software implementations of basic algorithms and data structures;

apply basic algorithms and data structures for practical problems arising in the development of software and hardware information processing systems;

develop efficient graph search algorithms;

Be able to: 

use methods of creating and implementing data structures;

use methods for estimating the complexity of algorithms;

use approaches to solving algorithmic problems based on known algorithmic strategies.

Семестр изучения учебной дисциплины, модуля / Semester of study

5

5

Пререквизиты / Prerequisites

«Дискретная математика и теория графов», «Методы программирования», «Технологии программирования»

«Discrete mathematics and graph theory», «Programming methods», «Programming technologies»

Трудоемкость в зачетных единицах (кредитах) / Credit units

3 зачетные единицы.

3 credit units

Количество аудиторных часов и часов самостоятельной работы / Academic hour of students’ class work,

hours of self-directed learning

108 часов, из них: 72 часа аудиторной работы, управляемая самостоятельная работа – 4 часа.

108 hours of students’ class work including: 72 academic hours, 4 hours of self-directed learning.

Требования и формы текущей и промежуточной аттестации / Requirements and forms of current and interim certification

Устный опрос, отчет по аудиторным практическим упражнениям, учебная дискуссия, анализ кейсов, контрольная работа с устной защитой, зачет

Oral questioning, report on classroom practical exercises, educational discussion, case analysis, test with oral defense, end-of-term test