Вопросык экзаменам. Вопросы по теории алгоритмов.
Машина Тьюринга, теорема Кука. NP-полные задачи. КлассNPи классP.
Задача коммивояжёра. Приложение метода ветвей и границ.
Динамическое программирование и метод сетевого планирования. Ранние и поздние времена, запасы времени на работу.
Алгоритм Карацубы. Сложность алгоритма Карацубы. Масштабное соотношение. (Можно блок алгоритмов Тома).
Алгоритм сортировки слиянием и быстрое преобразование Фурье.
Схема Горнера, быстрое преобразование Фурье, битовое преобразование Фурье, обратные матрицы преобразований Фурье для этих случаев. Арифметика комплексных чисел, их умножение и деление, матричное представление.
Модулярная арифметика, Быстрое возведение в степень. Алгоритм Масси-Омуры, алгоритм RSA.
Алгоритм Квадратичного решета для факторизации чисел и взлома RSA.
Алгоритм Цермело-Куна.
Алгоритм Евклида обращения чисел по заданному модулю.
Алгоритм Дейкстры.
Алгоритм Форда-Фалкерсона поиска максимального потока в сети..
Алгоритм быстрого перемножения матриц Штрассена.
Основные идеи перемножения полиномов с помощью преобразования Фурье.
Жадные алгоритмы построения минимального остовного дерева.
Алгоритм транзитивного замыкания графа (алгоритм Уоршалла).
Нечёткая логика. Формулы для нечёткой коньюнкции (и), дизьюнкции (или) и отрицания. Анализ иерархий элементы теории нейронных сетей. Сеть Кохонена, сеть Хопфилда, Персептрон (выразимость).
Логические функции не более чем двух переменных, существенность переменных, упрощение релейно-контактных схем,
Дизьюнктивная, коньюнктивная и полиномиальная формы, Теорема Поста, классы Поста, число функций (мощность) классов Поста, (часто встречающиеся) полные системы функций, Шефферовы функции.
Задача о раскрасках. Вычисление хроматического полинома.
Математическое и имитационное моделирование.
Простейшие бифуркации одномерных систем. Модель Изинга, фазовые переходы 1-го и второго рода, точка Кюри, спиновое стекло, жесткие, мягкие бифуркации, их связь с фазовыми переходами 1-го и 2-го рода.
(не обязательно) Формула Больцмана, её вывод из принципа максимума энтропии.
Персептрон, персептронная выразимость. Градиентный метод обучения. Метод отжига.
Нейросеть Кохонена. Связь скорости обучения и потребного числа шагов. Возможный критерий слияния классов.
Фазовые портреты линейных двумерных систем, собственные вектора, собственные значения и инварианты матриц, SD- диаграмма. Бифуркационные переходы общего и необщеего положения.
Логистическое отображение. Сколько параметров модели Ферхльюста остаются неустранимыми при (линейной) замене координат. Упорядочить в порядке Шарковского числа abcd,abcd-1,abcd+1,abcd+2,abcd+3,abcd+4,abcd+5. Теорема Ли-Йорке. Универсальность порядка Шарковского. Сечение Пуанкаре. Причины воспроизведения каскада бифуркаций при переход к хаосу в системе Рёсслера и нарушения этого же порядка в системе Лоренца.
Критерии устойчивости для цикла. Гиперустойчивость. Порядок Шарковского.
Уравнение Ферхльюста. Максимально обезразмерьте модель и проведите качественной исследование. Решите модель аналитически методом разделения переменных. Вопрос в сторону: какие полезные свойства этой функции могут использоваться в нейросетях обучаемых градиентным методом (Back-Propagation).
Модели популяционной динамики, в т.ч. модель хищник жертва.
Динамический хаос. Примеры систем. Понятие странного аттрактора. Консервативные и неконсервативные системы. Системы, заданные непрерывным-дифференциальным уравнением и дискретным отображением.
Метод Галёркина. Система Лоренца. (Можно система Тьюринга-модель реакция диффузия).
Модель Д.С.Чернавского борьбы стандартов. Пространственная форма модели (Модель Малкова-Чернавского).
Модель Пер-Бака и другие модели самоорганизованной критичности.
Методы исследования дискретных отображений. Критерий устойчивости неподвижных точек для одномерного и для многомерного отображения. Критерий сохранения фазового объёма в дискретном отображении.
Методы исследования непрерывных дифференциальных уравнений и систем. Критерий устойчивости неподвижных точек для одномерного уравнения и для многомерной системы. Критерий сохранения фазового объёма в непрерывном случае.
Методы исследования жестких систем. Нетривиальная взаимо-зависимость амплитуды и частоты в жёстком цикле. Системы типа Фитсхью-Нагума, связь одномерных бифуркационных диаграмм и некоторых главных изоклин жестких систем. Замена некоторых – быстрых - дифференциальных уравнений на аналитические. Модель деятельности нейрона.
Методы исследования дискретных отображений. Критерий устойчивости неподвижных точек для одномерного и для многомерного отображения. Критерий сохранения фазового объёма в дискретном отображении.
Характеристические уравнения и собственные вектора. SD-диаграмма.
Кондратьевские циклы и модель бистабильности на рынке труда.
Модели циклических колебаний в экономике.
Уравнение Фоккера-Планка и другие уравнение в частных производных. Уравнение переноса и теплопроводности. Уравнение Лапласа. Решение 1-мерного уравнения Фоккера-Планка. Температура, потенциал и равновесная плотность распределения. Разносные схемы (для уравнения переноса, спектральнуй признак).
Метод динамического программирования.
Моделирование систем массового обслуживания (+задача в задачнике).
Модель обучения Капустина. Методы исследования дискретных отображений. Сведение околодиагональных систем к непрерывным дифференциальным уравнениям.
Подкова Смейла, теорема Шильникова, гомоклиническая и гетеролиническая точка и структуры.
Разложение в ряды Тейлора, круги сходимости, приближённые формулы расчёта корней, синусов, экспонент и т.д.
Фрактальная размерность, кривые типа пеано, голоморфная динамика (множество Мандельброта), связь с логистическим отображением.
Сечение Пуанкаре, сигнатура и условия на суммы собственных значений трехмерных диссипативных и недиссипативных непрерывных хаотических систем, и сведение трехмерных систем к одномерным дискретным отображениям. Связь с логистическим отображением - условие возникновение порядка Шарковского при переходе к хаосу в трехмерных непрерывных диссипативных динамических системах.
Задача о реконструкции аттрактора.
Энтропии Реньи.
Феррари
Газель
КамАЗ
Исходная иерархия
Груз
Скорость
ЛПР
1минималистский вариант неудобен: чтобы избежать коллизий вариантов, с каждым студентом пришлось бы встречаться, чтобы в условиях нехватки уникальных вариантов последовательно раздать номера персонально и записывая их, (при большом количестве больших потоков это очень обременительно). Варианты бы повторялись между потоками. Это привело бы к появлению решений. (Кстати распечатка и транспортировка документа размером более 1000 страниц представили бы собой отдельный подвиг).