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

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

Раздел 4. Приближенные алгоритмы и аппроксимация с гарантированной точностью (Алгоритмы с гарантированной оценкой точности. Жадные алгоритмы для покрытия множеств. Приближенные алгоритмы для вершинного покрытия. Жадный алгоритм для задачи о рюкзаке. Алгоритм Кристофидеса)

Раздел 5. Вероятностный анализ детерминированных алгоритмов (Вероятностный анализ задачи об упаковке выполнимости КНФ. Точность алгоритма для почти всех входов. Полиномиальность в среднем)

Раздел 6. Вероятностные алгоритмы и их анализ (Вероятностное округление для задачи MAX-SAT. Максимальный разрез в графе. Методы дерандомизации. Метод условных вероятностей. Метод малых вероятностных пространств. Полиномиальная проверка простоты)

Section 4. Approximate algorithms and approximation with guaranteed accuracy (Algorithms with guaranteed accuracy estimates. Greedy algorithms for set covering. Approximate algorithms for vertex covering. Greedy algorithm for the knapsack problem. Christofides algorithm)

Section 5. Probabilistic analysis of deterministic algorithms (Probabilistic analysis of the CNF satisfiability packing problem. Algorithm accuracy for almost all inputs. Polynomiality in average)

Section 6. Probabilistic algorithms and their analysis (Probabilistic rounding for the MAX-SAT problem. Maximum cut in a graph. Derandomization methods. Method of conditional probabilities. Method of small probability spaces. Polynomial primality check)

Формируемые компетенции / 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

6

6

Пререквизиты / 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

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

90 hours of students’ class work including 50 academic hours, 4 hours of self-directed learning.

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

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

Report on classroom practical exercises, test with oral defense, colloquium, end-of-term test and exam