Название работы	Кол-во страниц	Размер
Рабочей программы дисциплины параллельные вычисления Место дисциплины...	1	13.77kb.
Рабочей программы дисциплины Интеллектуальные системы Место дисциплины...	1	16.2kb.
Место дисциплины в структуре ооп принципы построения курса: Курс...	1	27.11kb.
Место дисциплины в структуре ооп принципы построения курса: Курс...	1	17.16kb.
Аннотация рабочей программы дисциплины	1	23.67kb.
Аннотация рабочей программы дисциплины	1	10.84kb.
Рабочей программы дисциплины Архитектура информационных систем Место...	1	22.64kb.
Рабочей программы дисциплины ЭВМ и периферийные устройства Место...	1	18.03kb.
Практикум Место дисциплины в структуре ооп принципы построения курса	1	17.65kb.
Рабочей программы дисциплины Математические основы информатики Место...	1	11.56kb.
Рабочей программы дисциплины Кратные интегралы и ряды Место дисциплины...	1	28.18kb.
Исследование модели децентрализованной структурированной p2p сети...	1	114.29kb.
Викторина для любознательных: «Занимательная биология»	1	9.92kb.

Аннотация рабочей программы дисциплины

Алгоритмы и анализ сложности

Место дисциплины в структуре ООП

Принципы построения курса:

Курс входит в профессиональный цикл ООП 010300 «Фундаментальная информатика и информационные технологии»

В курсе выделено несколько разделов / тем:

Основы анализа алгоритмов: асимптотический анализ верхней и средней оценок сложности алгоритмов; сравнение наилучших, средних и наихудших оценок; O-, o-, ?- и ?-нотации; стандартные классы сложности; эмпирические измерения эффективности алгоритмов; накладные расходы алгоритмов по времени и памяти; рекуррентные соотношения и анализ рекурсивных алгоритмов. Стратегии алгоритмов: полный перебор; метод «разделяй и властвуй»; «жадные» алгоритмы; бэктрекинг (перебор с возвратами); метод ветвей и границ; эвристический поиск; поиск по образцу, алгоритмы обработки строк; алгоритмы аппроксимации числовых функций. Основные алгоритмы обработки информации: основные алгоритмы над числами; алгоритмы последовательного и бинарного поиска; алгоритмы сортировки сложности O(N*N) и O(N*logN); хеш-функции и методы исключения коллизий; деревья бинарного поиска; представление графов (списки и матрицы смежности); поиск в глубину и поиск в ширину; алгоритмы поиска кратчайших путей (алгоритмы Дейкстры и Флойда); транзитивное замыкание (алгоритм Флойда); алгоритмы построения минимального покрывающего дерева (алгоритмы Прима и Крускала); топологическая сортировка. Распределенные алгоритмы: модель параллельного выполнения программы с общей памятью и модель передачи сообщений: организация параллельных вычислений на принципе консенсуса и на основе выбора; методы определения завершения параллельных вычислений. Основы теории вычислимости: конечные автоматы; контекстно-свободные грамматики; разрешимые и неразрешимые проблемы; невычислимые функции; проблема останова; применение невычислимости.
Компетенция обучающегося,

формируемая в результате освоения дисциплины (модуля)
- детальное знание методов и базовых алгоритмов обработки информационных структур, методов анализа сложности алгоритмов (ПК-17).