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

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

Оценка трудоемкости алгоритмов.  Асимптотики Ο, Ω, Θ. Оценка трудоемкости алгоритмов с использованием рекуррентных уравнений. Рекуррентные уравнения и методы их решения. 

 Способы организации базовых структур данных. Абстрактные типы данных (АТД), их реализация структурами данных (СД): связный список, стек, очередь, очередь с приоритетом. Способы организации базовых структур данных: массив, мультисписок, стек, очередь. Реализация базовых операций и их трудоемкость. 

Специальная древовидная структура данных: куча. Бинарная куча. D-куча. Биномиальная куча. Куча Фибоначчи. Реализация базовых операций и их трудоемкость. Реализация расширенного набора операций и их трудоемкость. Технологии использования корневых деревьев для реализации базового и расширенного набора операций структуры данных куча и оценка их трудоемкости. Стратегии выбора оптимальных структур данных. 

Специальная структура данных: система непересекающихся множеств (СНМ). 

Способы представления системы непересекающихся множеств (СНМ) с помощью массива и связного списка с указателем на представителя. Представление СНМ с помощью корневых деревьев с эвристиками объединения по размеру и сжатия пути. Реализация базовых операций и оценка их трудоемкости.

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

Операции с деревьями. Технологии реализации базовых операций с использованием корневых деревьев. Технологии преобразования деревьев в задачах сетевой оптимизации с использованием корневых структур. Фундаментальная система циклов и разрезов.

Алгоритмы на графах и мультиграфах. Методы хранения графов в памяти компьютера. Матрица смежности. Матрица инцидентности. Представление ориентированных графов списками дуг. Списки наследников узлов. Списки предшественников узлов. Списки наследников и предшественников узлов. Алгоритм поиска наследников и его трудоемкость. Алгоритм поиска предшественников и его трудоемкость. Алгоритм поиска наследников и предшественников и его трудоемкость. Реализация базовых операций и их трудоемкость. Мультисписки. Стратегии выбора оптимальных структур данных. Стратегии и алгоритмы обхода узлов графа

Задача оценки потоков на ненаблюдаемой части сети. Математическая модель задачи идентификации местоположения специальных программируемых устройств (датчиков) (англ. Sensor Location Problem, SLP) в узлах двунаправленного графа. NP — полная проблема минимизации размера множества контролируемых узлов. Стратегии идентификации узлов для локализации датчиков. Сбор, обработка, анализ информации о функции потока. Оценка потоков в той части сети, которая не наблюдается. Примеры оптимальных и субоптимальных решений задачи SLP. 

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

Разреженный матричный анализ и технологии декомпозиции. Декомпозиция переменных по наборам узлов и дуг базисной матрицы для разреженных недоопределенных  систем линейных алгебраических уравнений (СЛАУ). Эффективные алгоритмы построения базисных графов, базиса пространства решений и частных решений разреженных систем с использованием корнев СЛАУ. Методы, алгоритмы и технологии построения общего решения разреженной СЛАУ с учетом типа разреженности. Применение методов, алгоритмов и технологий декомпозиция для решения прикладных задач разреженного матричного анализа.

Оптимальные пути. Математические модели задач о кратчайших путях. Базисные методы построения оптимальных путей с использованием корневых деревьев. Технологии преобразования деревьев. в задачах о кратчайших путях. Применение принципов динамического программирования для решения задач о кратчайших путях. Уравнение Беллмана.   Двухкритериальные задачи потокового программирования.

Задачи линейной оптимизации с неточными данными. Математические модели линейных задач оптимизации в конечномерных пространствах. Допустимое решение. Математические модели обратных задач в соответствии с выбранной нормой для моделирования параметров целевой функции. Моделирование оптимальных значений параметров целевой функции. Математические модели обратных задач линейной оптимизации для моделирования параметров нижних и верхних границ в соответствии с выбранной нормой. Частично допустимое решение. Математические модели обратных задач в соответствии с выбранной нормой для моделирования параметров нижних и верхних границ. Формирование параметров нижних и верхних границ. 

Evaluation of algorithms complexity. 

Asymptotics of Ο, Ω, Θ. Estimating the complexity of algorithms using recurrence equations. Recurrence equations and methods for their solution.

Methods for organizing basic data structures. Abstract data types (ADT) and their implementation by data structures (DS): linked list, stack, queue, priority queue. Methods for organizing basic data structures: array, multilist, stack, queue. Implementation of basic operations and their complexity.

A special tree data structure: the heap.

Binary heap. D-heap. Binomial heap. Fibonacci heap. Implementation of basic operations and their complexity. Implementation of an extended set of operations and their complexity. Technologies for using rooted trees to implement the basic and extended set of operations of the heap data structure and their complexity estimation. Strategies for choosing optimal data structures.

Special data structure: disjoint set system (DSS).   Methods for representing a disjoint set system (DSS) using an array and a linked list with a pointer to a representative. Representing DSS using rooted trees with the join-by-size and path compression heuristics. Implementation of basic operations and estimation of their complexity.

Sorting. Classification of sorts: exchange, insertion, and merge. Binary inclusion sorting. Selection sorting. Sorting algorithms using exchanges: bubble sort, merge sort. Partition sorting: Hoare quicksort. Evaluation of basic internal sorting algorithms.

Operations using trees. Technologies for implementing basic operations using rooted trees. Technologies and algorithms for transforming trees in network optimization problems using rooted structures. A fundamental system of cycles and cuts.

Algorithms on graphs and multigraphs.

Methods for storing graphs in computer memory. Adjacency matrix. Incidence matrix. Representation of directed graphs by lists of arcs. Lists of successors of nodes. Lists of predecessors of nodes. Lists of successors and predecessors of nodes. The algorithm for finding successors and its complexity. The algorithm for finding predecessors and its complexity. The algorithm for finding successors and predecessors and its complexity. Implementation of basic operations and their complexity. Multilists. Strategies for choosing optimal data structures. Strategies and algorithms for traversing graph nodes

The problem of estimating flows on an unobservable part of the network.

A mathematical model of the Sensor Location Problem (SLP) for identifying the locations of special programmable devices (sensors) in nodes of a bidirectional graph. NP-complete problem of minimizing the size of a set of monitored nodes. Strategies for identifying nodes for sensor localization. Collection, processing, and analysis of flow function information. Estimation of flows in the unobserved portion of the network. Examples of optimal and suboptimal solutions to the SLP problem. 

Decomposition of basic graphs. Flow decomposition. Methods, algorithms, and technologies for constructing optimal and suboptimal solutions to the SLP problem.

Sparse matrix analysis and decomposition technologies. Decomposition of variables by sets of nodes and arcs of the basis matrix for sparse underdetermined systems of linear algebraic equations (SLAEs). Efficient algorithms for constructing basis graphs, solution space basis, and particular solutions of sparse systems using SLAE roots. Methods, algorithms, and technologies for constructing a general solution to a sparse SLAE, taking into account the type of sparsity. Application of decomposition methods, algorithms, and technologies to solving applied problems of sparse matrix analysis.

Optimal paths. Mathematical models of shortest-path problems. Basic methods for constructing optimal paths using rooted trees. Tree transformation technologies in shortest-path problems. Application of dynamic programming principles to solving shortest-path problems. Bellman equation.  Network optimization problems of two-criteria.

Linear optimization problems with uncertain data. Mathematical models of linear optimization problems in finite-dimensional spaces. Feasible solution. Mathematical models of inverse problems in accordance with the chosen norm for modeling the parameters of the objective function. Modeling optimal values ​​of the objective function parameters. Mathematical models of inverse linear optimization problems for modeling the parameters of the lower and upper bounds in accordance with the chosen norm. Partially feasible solution. Mathematical models of inverse problems in accordance with the chosen norm for modeling the parameters of the lower and upper bounds. Formation of the parameters of the lower and upper bounds.

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

Специализированная компетенция:

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

Specialized competence: make a well-founded choice of a rational numerical method for solving applied mathematical problems, implement it using modern computer software, evaluate the correctness of the results obtained and analyze the possibilities of alternative approaches.

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

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

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

• • определять трудоемкость алгоритмов;
  • применять структуры данных для построения алгоритмов;
  • использовать принципы динамического программирования для решения задач об оптимальных путях;
  • использовать принципы декомпозиции для задач разреженного матричного анализа;
  • разрабатывать программные реализации основных алгоритмов и структур данных;
  • применять основные алгоритмы и структуры данных для практических задач;
  • разрабатывать эффективные алгоритмы поиска на графах и мультиграфах;
  • анализировать достоверность и трактовать численные результаты;
• владеть:

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

As a result of mastering the academic discipline, the student must

know:

– the concept of problem dimension and algorithm complexity;

– basic methods for solving recurrence equations;

– data structures used in algorithm evaluation;

– decomposition techniques;

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

– methods for organizing data structures and technologies for their use;

– basic algorithms on graphs and multigraphs;

can:

– determine the complexity of algorithms;

– apply data structures to construct algorithms;

– use dynamic programming principles to solve optimal path problems;

– apply decomposition principles to sparse matrix analysis problems;

– develop software implementations of basic algorithms and data structures;

– apply basic algorithms and data structures to practical problems;

– develop efficient graph and multigraph search algorithms;

– analyze the reliability and interpret numerical results;

be able to:

– skills in working with modern software for numerically solving mathematical and applied problems;

– assess the correctness of the problem statement;

– select a method for numerically solving the problem;

– skills in designing and implementing data structures;

– assessing the complexity of algorithms;

– solving algorithmic problems using modern technologies of sparse matrix analysis and theoretical computer science;

– analyze the reliability and interpret numerical results.

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

5

5

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

–Компьютерная математика,

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

– Дискретная математика и теория графов,

– Численные методы,

– Оптимизация

.

– Computer Mathematica,

– Algebra and Number Theory,

– Discrete Mathematics and Graph Theory,

– Numerical Methods,

– Optimization.

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

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

3 credits 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

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

Итоговые контрольные работы.

5 семестр –зачет.

Survey, written report with oral defense on laboratory work, written report with oral defense on homework, written report with oral defense on solving problems and exercises, verification work.

End-of-term tests.

5th semester – credit.