Построение и анализ алгоритмов

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

Понятие о классах сложности задач. Задача о геометрическом центре пространства строк как пример задачи 3-Выполнимость. Гипотеза экспоненциального времени. Гипотеза P=NP, ее значимость, связь классов P, NP с ДКА и НДКА. Задачи Раздела 1 как примеры P-класса. Примеры распространенных NP-задач, 3-Выполнимость как задача класса NP. Пример переформулировки задачи из P-класса в NP-задачу. Определение NP-полной задачи. Сводимость, теорема Кука-Карпа-Левина. Шесть основных NP-полных задач, 3-Выполнимость как NP-полная задача. Прикладная значимость сводимости NP-полных задач. Класс FPT. Определение NP-трудных задач.

Исследование множеств на отделимость. Двудольность и 3-сочетания. Задача о разделении множества строк на непересекающиеся подмножества подстрок. Представление графов в виде строк матриц смежности. Приложения отделимости. Разбиение как NP-полная задача. Проверка двудольности, поиск паросочетаний. Дополняющий путь, максимальное паросочетание. Алгоритм Эдмондса-Карпа. Задача о стабильных паросочетаниях как пример P-задачи. Алгоритм Гейла-Шепли. Стабильные 3-сочетания как NP-полная задача. Жадный алгоритм для 3-сочетаний.

Исследование множеств на отделимость. Раскраска графов. Раскраска графа. Понятие о задачах распознавания и задачах оптимизации, N-Выполнимость. Критерий Эйлера планарности графа, контрпример. Алгоритм Хопкрофта-Тарьяна проверки планарности. Топологическая сортировка для проверки графа на ацикличную ориентированность, поиск пути максимальной длины. Хроматическое число. Алгоритмы раскрасок. Числа Грунди и Брукса.

Исследование множеств на отделимость. Клики. Поиск клики как NP-полная задача. Свойства клики, ребра-мосты. Поиск максимальной клики. Поиск клики как NP-трудная и FTP-задачи. Поиск жадным алгоритмом. Поиск всех клик в графе. Поиск клик максимального веса, точный алгоритм Rozman-Konc, основанный на методе ветвей и границ.

Задачи целочисленного программирования. Задача об упаковке контейнера как NP-полная, ее приложения и разновидности. Решение методом ветвей и границ, границы его применимости. Метод Гомори. Приближенные методы решения. Поточная формулировка задачи. Задача о рюкзаке как общий случай задачи об упаковке контейнера, ее разновидности, приложения. Решение 0\1-задачи о рюкзаке методом ветвей и границ.

Остовные деревья и эйлеровы графы. Задача Штейнера, ее варианты. Задача Штейнера в графах, минимальное остовное дерево и алгоритмы его построения (Прима, Краскала, Борувки). Эйлеров путь, теорема о его существовании. Эйлеров цикл, алгоритм Герхольцера. СД «Дека». Полиномиальный подсчет количества эйлеровых циклов, «Теорема B.E.S.T.», некоторые свойства матриц, представляющих эйлеровы графы. Задача о вершинном покрытии как представитель класса NP-полных.

Гамильтоновы графы. Гамильтонов путь (ГП) как NP-трудная задача. Теорема Дирака о существовании ГП. Полиномиальный алгоритм поиска ГП в случае орграфа. Теорема Рахмана-Кайкобада, потребность в поиске кратчайшего пути. Алгоритмы Дейкстры, Беллмана-Форда, A*. Гамильтонов цикл (ГЦ) как NP-полная задача. Поиск ГЦ в произвольном графе алгоритмом Беллмана-Хелда-Карпа. Поиск всех кратчайших путей в графе, алгоритмы Флойда-Уоршелла, Джонсона.

Задача коммивояжера. Задача коммивояжера (TSP) как представитель класса NP-полных, ее прикладная ценность. Решение симметричного и асимметричного варианта TSP. Метрический вариант TSP, метод остовного дерева, алгоритм Кристофидеса.

Стратегии оптимизации. Решение TSP для минимального остовного дерева с существенным (n>100) числом вершин как частный случай задачи. Определение метаэвристики. Локальная оптимизация, метод сопряженных градиентов, оптимизация имитацией отжига, поиск с запретами. Влияние дифференцируемости, аналитичности функций на выбор метода оптимизации и ограничение параметров.

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

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

Введение в вероятностные структуры данных. Определение, значимость в современных информационных технологиях. СД «Фильтр Блума», проверка принадлежности элемента множеству. СД «HyperLogLog», оценка количества уникальных элементов множества. СД «Count-Min Sketch», подсчет частоты элементов в потоке данных.

The concept of problem complexity classes. The problem of the geometric center of the row space as an example of the 3-Satisfiability problem. The exponential time conjecture. The P=NP conjecture, its significance, the relationship of the classes P, NP with DFA and NDFA. Problems of Section 1 as examples of the P-class. Examples of common NP-problems, 3-Satisfiability as a problem of the NP class. An example of reformulating a problem from the P-class to an NP-problem. Definition of an NP-complete problem. Reducibility, the Cook-Karp-Levin theorem. Six main NP-complete problems, 3-Satisfiability as an NP-complete problem. Applied significance of the reducibility of NP-complete problems. The FPT class. Definition of NP-hard problems.

Set separability. Bipartition and 3-matchings. The problem of partitioning a set of strings into disjoint subsets of substrings. Representation of graphs as rows of adjacency matrices. Applications of separability. Partitioning as an NP-complete problem. Testing bipartition, finding matchings. Augmenting path, maximum matching. Edmonds-Karp algorithm. The problem of stable matchings as an example of the P-problem. Gale-Shapley algorithm. Stable 3-matchings as an NP-complete problem. Greedy algorithm for 3-matchings.

Set separability. Graph coloring. Graph coloring. Concept of recognition problems and optimization problems, N-satisfiability. Euler’s criterion for graph planarity, counterexample. Hopcroft-Tarjan algorithm for checking planarity. Topological sorting for checking graph acyclic orientation, finding the maximum path length. Chromatic number. Coloring algorithms. Grundy and Brooks numbers.

Integer programming problems. The bin packing problem as NP-complete, its applications, and variants. Branch-and-bound solution and its applicability limits. Cutting-plane method. Approximate solution methods. On-line formulation of the problem. The knapsack problem as a general case of the bin packing problem, its variants, and applications. Branch-and-bound solution of the 0\1 knapsack problem.

Spanning trees and Eulerian graphs. The Steiner problem and its variants. The Steiner problem in graphs, the minimum spanning tree, and algorithms for constructing it (Prim’s, Kruskal, Boruvka). The Eulerian path and its existence theorem. The Eulerian cycle, Gerholzer’s algorithm. The Deque data structure. Polynomial counting of Eulerian cycles, the B.E.S.T. Theorem, and some properties of matrices representing Eulerian graphs. The vertex cover problem as a representative of the class of NP-complete matrices.

Hamiltonian graphs. Hamiltonian path (HP) as an NP-hard problem. Dirac’s theorem on the existence of a HP. Polynomial-time algorithm for finding a HP in the case of a directed graph. Rahman-Kaikobad theorem, the need to find the shortest path. Dijkstra, Bellman-Ford, and A* algorithms. Hamiltonian cycle (HC) as an NP-complete problem. Finding a HP in an arbitrary graph using the Bellman-Held-Karp algorithm. Finding all shortest paths in a graph; Floyd-Warshall and Johnson algorithms.

The Traveling Salesman Problem. The Traveling Salesman Problem (TSP) as an NP-complete problem and its practical value. Solutions to the symmetric and asymmetric versions of the TSP. The metric version of the TSP, the spanning tree method, and Christofides’ algorithm.

Optimization strategies. Solving the minimum spanning tree problem for a significant (n>100) number of nodes as a special case. Definition of metaheuristics. Local optimization, conjugate gradient method, simulated annealing optimization, tabu search. The influence of differentiability and analyticity of functions on the choice of optimization method and parameter constraints.

Genetic algorithms. Genetic algorithms (GA) as a probabilistic case of the simple iteration method. Information encoding features. Selection, crossover, mutation, and substitution strategies. Extinction. Probabilistic factors influencing convergence rate.

Swarm algorithms. Advantages of cooperative strategies over competitive ones. Definition of swarm algorithms (SA) and their differences from genetic algorithms. Concepts of agents, their rationality, and selfishness. Definitions of games, games with perfect and imperfect information, and zero-sum games. Classification of problems by the feasibility of solving them using GA or SA. Particle swarm and ant colony algorithms. Specifics of configuring parameters responsible for agent trust and doubt.

Introduction to probabilistic data structures. Definition and importance in modern information technology. The Bloom Filter SD: checking whether an element belongs to a set. The HyperLogLog SD: estimating the number of unique elements in a set. The Count-Min Sketch SD: counting the frequency of elements in a data stream.

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

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

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

Universal competencies: master the fundamentals of research, search, analyze, and synthesize information; solve standard professional problems using information and communication technologies. 

Basic professional competencies: Apply modern technologies and basic programming language constructs to implement algorithmic applications and develop web projects.

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

В результате изучения данной дисциплины студент должен

знать:

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

уметь:

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

иметь навык:

• проектирования и реализации структур данных;
• оценки трудоемкости алгоритмов;
• решения алгоритмических задач на основе известных алгоритмических стратегий.

Upon completion of this course, the student should

know:

− the most common algorithm evaluations;

− principles of evaluating combinatorial algorithms;

− data structures used in algorithm evaluation;

− exhaustive search techniques;

− decomposition techniques;

− the concepts of polynomial-time solvable and NP-complete problems;

− lists of the most common NP-complete problems;

can:

− determine the complexity of algorithms;

− apply data structures to construct algorithms;

− use backtracking to construct algorithms;

− use the divide-and-conquer principle to decompose problems;

− develop software implementations of basic algorithms and data structures;

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

− develop efficient graph search algorithms;

Be able to:

− design and implement data structures;

− evaluate the complexity of algorithms;

− solve algorithmic problems based on known algorithmic strategies.

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

6

6

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

— Математический анализ,

— Алгебра и теория чисел,

— Дискретная математика и математическая логика

— Mathematical analysis,

— Algebra and Number Theory,

— Discrete Mathematics and Mathematical Logic

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

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

3 credit units.

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

hours of self-directed learning

Всего 120 часов, в том числе 68 аудиторных часов и 52 часа самостоятельной работы

A total of 120 hours, of which 68 academic hours of students’ class work and 52 hours of self-directed learning.

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

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

Экзамен.

Survey, lab report with oral defense, report on classroom practical exercises, test.

Exam.