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

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

Принципы оценки алгоритмов. Объект и предмет дисциплины. Определение алгоритма. Прикладное значение эффективности алгоритмов – временная и пространственная сложность алгоритма, О-нотация. Основная теорема о рекуррентных соотношениях. Оценка сложности алгоритма умножения в столбик. Алгоритм Карацубы.

Хранение информации. Понятие абстракции. Абстрактные типы данных (АТД), их реализация структурами данных (СД): связный список, стек, очередь, очередь с приоритетом. Бинарное дерево. Построение приоритетной очереди с помощью бинарного дерева (СД «Двоичная куча»). Преобразование массива в двоичную кучу. Стратегии выбора оптимальных структур данных.

Упорядочивание информации. Сортировки. Классификация сортировок по их основной операции (обменные, вставочные, выборочные, сливающие, сравнивающие). Оценка сложности. Теорема о невозможности существования алгоритма сортировки сравнениями в «худшем» и «в среднем» с трудоемкостью меньшей, чем О(n log(n)). Определение эвристики. Эвристика выбора опорного элемента в быстрой сортировке. Устойчивость, адаптивность, поточность сортировок. Предпосылки для использования отличных от массивов СД в сортировках. Пирамидальная сортировка, плавная сортировка Дейкстры (SmoothSort). Гибридные сортировки.

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

Упорядочивание поступающих данных. Самобалансирующиеся (АВЛ) деревья, операция вращения. Красно-черные деревья, 2-3-деревья, Б- и М-деревья. Декартово дерево.

Поиск без упорядочивания, эффективная индексация. Декартово и красно-черное деревья как реализации АТД «Ассоциативный массив», другие реализации. Проблема больших данных, ее преодоление с помощью хэш-таблиц. Основные понятия и определения (хэш-функции, их качество, коллизии). Семейства хэш-функций. Примеры эффективных хэш-функций. Способы разрешения коллизий. Задача о поиске N наибольших (наименьших) элементов без сортировки. Передовые и перспективные направления в индексации (Cuckoo Hashing, Tiny pointers, SwissTable).

Эффективный поиск последовательностей. Регулярные выражения, операции над ними, метасимволы, шаблоны. Машины Тьюринга. Детерминированные и недетерминированные конечные автоматы (ДКА и НДКА). Поиск подстроки в строке. Понятие об амортизационном анализе алгоритмов. Задача о поиске геометрического центра в пространстве строк. Функция Левенштейна. Алгоритм Хиршберга.

Principles of algorithm estimation. Object and subject of the discipline. Definition of an algorithm. Practical significance of algorithm efficiency – time and space complexity of an algorithm, O-notation. Fundamental theorem of recurrence relations. Complexity estimation of the long multiplication algorithm. Karatsuba algorithm.

Information storage. The concept of abstraction. Abstract data types (ADTs) and their implementation using data structures (DS): linked list, stack, queue, priority queue. Binary tree. Building a priority queue using a binary tree (BD «Binary Heap»). Converting an array to a binary heap. Strategies for choosing optimal data structures.

Information ordering. Sorting. Classification of sortings by their main operation (exchange, insertion, selection, merging, comparison). Complexity estimation. A theorem on the impossibility of existence of a comparison sorting algorithm in the «worst» and «on average» cases with complexity less than O(n log(n)). Definition of heuristics. Heuristic for choosing a pivot element in quicksort. Robustness, adaptability, and flowability of sorting. Prerequisites for using non-array SDs in sorting. Heapsort, Dijkstra’s smooth sort (SmoothSort). Hybrid sorts.

Searching in ordered information. Binary and interpolating search. Exponentially growing data, hybrid search. Traversals and search in binary trees. Checking graphs for cycles. Binary search trees. Finding the lowest common ancestor of two nodes.

Sorting incoming data. Self-balancing (ABL) trees, rotation operation. Red-black trees, 2-3-trees, B- and M-trees. Cartesian tree.

Unordered search, efficient indexing. Cartesian and red-black trees as implementations of the Associative Array ADT, and other implementations. The problem of big data and how to overcome it using hash tables. Key concepts and definitions (hash functions, their quality, collisions). Families of hash functions. Examples of efficient hash functions. Collision resolution methods. The problem of finding the N largest (smallest) elements without sorting. Advanced and promising trends in indexing (Cuckoo Hashing, Tiny pointers, SwissTable).

Efficient sequence search. Regular expressions, operations on them, metacharacters, patterns. Turing machines. Deterministic and nondeterministic finite automata (DFA and NDFA). Substring search. Amortized analysis of algorithms. The problem of finding the geometric center in string space. The Levenshtein function. Hirschberg’s algorithm.

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

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

знать:

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

уметь:

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

иметь навык:

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

Upon completion of this course, the student should

know: 

− understand the most common algorithm evaluations; 

− use data structures in algorithm evaluation; 

can: 

− determine the complexity of algorithms; 

− apply data structures to construct algorithms;

− use backtracking to construct algorithms; 

− 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 systems for information processing; 

be able to: 

− design and implement data structures; 

− estimate the complexity of algorithms; 

− solve algorithmic problems based on known algorithmic strategies.

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

5

5

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

Всего 90 часов, в том числе 54 аудиторных часа и 36 часов самостоятельной работы.

A total of 90 hours, of which 54 academic hours of students’ class work and 36 hours of self-directed learning.

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

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

Зачет.

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

End-of-term tests.