Geum.ru

Стандарт

Вид материалаДокументы

Содержание


Комбинаторные алгоритмы
Методы оптимизации
Лингвистические основы информатики
Подобный материал:
1   2   3   4   5   6

Комбинаторные алгоритмы


Алгоритмы и их сложности. Машина Тьюринга, недерминированная машина Тьюринга, классы Р и NР. Поиск и сортировка, сложность задачи сортировки, поиск с возвратом. Графы и сети. Машинное представление графов и сетей, поиск в ширину и поиск в глубину в графе. Оптимизационные задачи на графах: задача о минимальном остове, алгоритмы Краскала и Прима; задачи о кратчайших путях в сетях, алгоритмы Форда – Фалкерсона, Дейкстры, Фловда, сетевые графики; потоки в сетях, теорема Форда – Фалкерсона, алгоритм Форда – Фалкерсона построения максимального потока, задача о потоке минимальной стоимости, прямой и двойственный алгоритмы ее решения, транспортная задача; паросочетания в двудольных графах, теорема Бержа, алгоритм Хопкрофта – Карпа построения наибольшего паросочетания, теорема Холла,

алгоритм построения совершенного паросочетания, венгерский алгоритм построения оптимального паросочетания, задача разбиения на минимальное число паросочетаний, теорема Мендельсона – Далмеджа. Задача коммивояжера, алгоритмы с гарантированной оценкой точности для задачи коммивояжера, метод ветвей и границ. Стохастические алгоритмы, моделирование отжига. Комбинаторика: генерирование перестановок, генерирование подмножеств, генерирование разбиений множеств.


220

ОПД.Ф.07

Распознавание образов

Модели описания состояний объек-тов: модели дискриминантного анализа, таксономии, оценки признаков. Методы распознавания образов: дискриминации на основе сведения к линейным неравенствам, линейной коррекции, свертывания, метод комитетов, метод потенциалов, статистической теории решений. Задача таксономии: метод сфер. Метод плеяд. Реляционные модели таксономии, метод максимальных совместных подсистем. Задачи выбора информативных признаков, сводимые к двойственным моделям оптимизации. Тупиковые тесты в выборе информативных признаков. Метод линейных многообразий в оценке признаков. Структурно-лингвистические методы. Диагностика состояний сложных систем и ситуаций принятия решении, классификация объектов и явлений, моделирование неформализованных закономерностей и зависимостей между факторами, генерирование понятий, описание классов объектов и ситуаций. Применение методов распознавания образов в интеллектуальных пакетах прикладных программ, в алгоритмах для неформализованных задач оптимального выбора решений.


110

ОПД.Ф.08

Методы оптимизации


Линейное программирование: поста-новка задачи линейного программиро-вания, ее геометрическая и экономи-ческая интерпретации, принцип двой-ственности, условия оптимальности, транспортная задача, симплекс-метод. Элементы выпуклого анализа. Основы теории математического программиро-вания, принцип Лагранжа, двойственность в выпуклом программировании. Нелинейное программирование: постановка задачи, экономическая интерпретация, двойственность, теорема Куна – Таккера, условия оптимальности, методы штрафных функций, возможных направлений, линейных отсечений, негладкая оптимизация. Численные методы оптимизации, методы безусловной и условной оптимизации. Вариационное исчисление, уравнение Эйлера, изопериметрическая задача. Метод динамического программиро-вания Беллмана.


110

ОПД.Ф.09

Вычислительный эксперимент и методы вычислений

Погрешности вычислений. Интерпо-лирование и приближение функций. Интерполяционный многочлен Лагранжа, многочлены Чебышева, тригонометрическая интерполяция; дискретное преобразование Фурье; наилучшее приближение в нормированном пространстве; существование элемента наилучшего приближения; Чебышевский альтернанс, ортогональные многочлены; процесс ортогонализации Шмидта; запись многочлена в виде разложения по ортогональным многочленам. Сплайны; экстремальные свойства сплайнов; построение кубического интерполяционного сплайна. Простейшие квадра-турные формулы прямоугольников, трапеций; квадратурные формулы Кьютона – Котеса; оценки погрешности этих квадратурных формул; квадратурные формулы Гаусса. Численное дифференцирование, правило Рунге оценки погрешности. Основные задачи линейной алгебры, метод Гаусса; метод простой итерации, метод простой итерации для симметричных положительно определенных матриц, оптимизация параметра процесса; процесс ускорения сходимости итераций, метод наискорейшего градиентного спуска; метод Зейделя. Методы решения нелинейных уравнений Метод разложения в ряд Тейлора решения задачи Коши для ОДУ, метод Эйлера и его модификации, методы Рунге – Кутта. Конечно-разностные методы, понятие об аппроксимации, исследование свойств конечно-разностных схем на модельных примерах; основные понятия теории разностных схем: аппроксимация, устойчивость, сходимость; аппроксимация, устойчивость и сходи-мость для простейшей краевой задачи для ОДУ второго порядка; методы решения системы ЛАУ с трехдиагональной матрицей (метод стрельбы и метод прогонки); метод конечных элементов; простейшие разностные схемы для уравнения переноса, явная и неявная схемы, разностная схема для уравнения Пуассона в прямоугольнике, ее корректность; методы решения сеточной задачи Дирихле для уравнения Пуассона.


220

ОПД.Ф.10

Лингвистические основы информатики


Языковые средства программных систем, лингвистическое обеспечение взаимодействия пользователя с системой, виды языков. Формальные языки, способы задания. Порождающие грамматики и автоматы. Контекстно-свободные языки, алгоритмы синтаксического анализа. Описание контекстных условий формальных языков. Модели естественных языков, деревья подчинения, системы составляющих. Основные этапы перевода с естественного языка на формализованный, словари. Направления развития языковых средств программных систем.


110

ОПД.Ф.11