Федеральное государственное бюджетное учреждение науки



жүктеу 65.67 Kb.
Дата02.04.2018
өлшемі65.67 Kb.
түріПрограмма

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ НАУКИ

ИНСТИТУТ ПРИКЛАДНЫХ МАТЕМАТИЧЕСКИХ ИССЛЕДОВАНИЙ

КАРЕЛЬСКОГО НАУЧНОГО ЦЕНТРА

РОССИЙСКОЙ АКАДЕМИИ НАУК

(ИПМИ КарНЦ РАН)


УТВЕРЖДАЮ:

Директор ИПМИ КарНЦ РАН

д.ф.-м.н., профессор

В.В. Мазалов


«____» ____________ 20 г.

ПРОГРАММА

ВСТУПИТЕЛЬНОГО ЭКЗАМЕНА

в аспирантуру по направлению подготовки



01.06.01 – Математика и механика

(профиль: Дискретная математика и математическая кибернетика )

Принята Ученым советом ИПМИ КарНЦ РАН «22» мая 2014 г., протокол № 6

Петрозаводск 2014 г.



  1. Основы статистического моделирования

1.1. Статистические оценки и их основные свойства (состоятельность, несмещенность, эффективность). Неравенство Рао-Крамера.

1.2. Методы нахождения статистических оценок (методы моментов и максимального правдоподобия).

1.3. Общая логическая схема статистического критерия. Критерии согласия.

1.4. Имитационное моделирование. Метод Монте-Карло. Примеры.

1.5. Корреляционный анализ. Линейная регрессия. Метод наименьших квадратов.

1.6. Дисперсионный анализ.

1.7. Множественная регрессия. Нахождение наиболее информативного множества признаков линейной регрессии.

1.8. Нелинейная регрессия.



2. Прикладная теория вероятностей

2.1. Основные классы случайных процессов: марковские, процессы восстановления, гауссовские (винеровский и дробный броуновский процесс).

2.2. Интервальное оценивание на основе центральной предельной теоремы.

2.3. Простейшая система М/М/1, стационарное распределение (вывод).

2.4. Марковские и регенерирующие процессы (определения и основные свойства).

2.5. Формула Поллачека –Хинчина (вывод, применение).

2.6. Формула Литтла (вывод, применение).

2.7. Теорема Джексона о декомпозиции стационарной марковской сети (формулировка и применение).


  1. Теория графов

3.1. Модели в форме графов.

3.2. Алгоритмы поиска на графах: Беллмана — Форда, Дейкстры, Форда — Фалкерсона, Крускала, Прима, поиск в глубину, поиск в ширину.

3.3. Модель случайных графов Эрдёша — Реньи, модель Барабаши-Альберт, модель Уоттса — Строгатца.


4. Математическая теория игр

4.1. Задача выпуклого программирования. Теорема Куна-Таккера.

4.2. Принцип равновесия.

4.3. Потенциальные игры.

4.4. Выпуклые игры.

4.5. Кооперативные игры.


  1. Дифференциальные уравнения

5.1. Основные понятия и определения, геометрическая интерпретация. Теорема Пикара о существовании и единственности решения задачи Коши.

5.2. Простейшие методы интегрирования уравнений 1-го порядка.

5.3. Решение линейных уравнений и систем с постоянными коэффициентами.

5.4. Устойчивость по Ляпунову, метод функций Ляпунова.

5.5. Динамические системы: основные понятия и определения. Инвариантные множества, предельные множества, грубость (структурная устойчивость).


  1. Численные методы

6.1. Решение систем линейных алгебраических уравнений: прямые и итерационные методы (общая характеристика, примеры).

6.2. Методы вычисления собственных чисел матрицы (на выбор).

6.3. Интерполирование (интерполяционные полиномы Лагранжа и Ньютона), численное дифференцирование и интегрирование (общая методология, примеры).

6.4. Минимизация функций нескольких переменных: градиентные методы, методы сопряженных направлений.

6.5. Численное решение задачи Коши: методы Рунге-Кутты, Адамса.

6.6. Разностные методы решения краевых задач математической физики (основные понятия, примеры).

6.7. Метод конечных элементов.


  1. Информатика и вычислительная техника

7.1. Алгоритм (машина Тьюринга, нормальные алгоритмы Маркова, конечные автоматы. Понятие сложности алгоритмов).

7.2. Алгебра логики: булевы функции. На выбор: критерий Поста (критерий полноты класса булевых функций, с доказательством), законы де Моргана (доказательство), закон Пирса (доказательство), задача выполнимости булевых формул (сложность и частные случаи задачи SAT, без доказательства).

7.3.Формальные языки и грамматики (классификация по Хомскому). Операции над строками: подстановка, гомоморфизм, проекция, синтаксическое отношение, префикс (рассказать об одной из операций).

7.4. Архитектуры вычислительных систем (рассказать об одной из архитектур): архитектура фон Неймана (принципы фон Неймана), Гарвардская архитектура (модификации архитектуры).

7.5. Организация КЭШ-памяти. Стековые компьютеры, RISC – процессоры.

7.6. Абстрактный тип данных: список, стек, очередь, ассоциативный массив, очередь с приоритетом. Структуры данных: массив, запись, связный список (линейный однонаправленный, двунаправленный, XOR-связный, кольцевой, с пропусками), дерево (двоичное, АВЛ-дерево, красно-чёрное, префиксное, суффиксное, куча (Фибоначчиева, двоичная)), хеш-таблица. Выбрать любые две структуры, рассказать о них, сравнить скорость доступа, время вставки и удаления элемента. В-дерево, алгоритмы сортировки.



7.7. Уровни сетевой модели OSI. Рассказать об одном из уровней подробнее.

7.8. Сложные сети и анализ гиперссылок. Свойства сетей: плотность, коэффициент кластеризации, меры центральности. Алгоритмы: HITS, PageRank. Рассказать об одном из алгоритмов и об одном из свойств.

7.9. Алгоритмы маршрутизации. Стек протоколов TCP/IP.


8. Операционные системы и системы программирования

8.1 Операционная система. На выбор: структура (компоненты) ОС, типы ОС, процессы (управление процессами, состояния процессов), потоки (типы многопоточности, взаимодействие потоков).

8.2. Управление памятью в операционных системах. На выбор: динамическое распределение памяти, виртуальная память, сборка мусора (проблемы, механизмы).



8.3. Парадигмы программирования. Процедурное программирование, объектно-ориентированное программирование.

8.4. Функциональное программирование, логическое программирование.



8.5. Параллельные вычисления. На выбор: закон Амдала, закон Густавсона-Барсиса, метрика Карпа-Флэта, типы параллелизма, анализ параллельных алгоритмов (оценка времени выполнения от числа процессоров).

8.6. Технология параллельного программирования. На выбор: OpenMP, MPI/



8.7. Языки баз данных (на выбор): язык описания данных, язык управления и манипулирования данными, язык запросов.

8.8 Проектирование баз данных (на выбор): нормальная форма, ограничения целостности.



8.9. Базы знаний. Извлечение знаний из текста (на выбор): выделение именованных сущностей, разрешение кореференции, построение онтологий.

8.10 Способы представления знаний (на выбор): семантическая сеть, фрейм, тематическая карта.

8.11 На выбор: экспертная система, система вывода (reasoning system), машина вывода (архитектура), алгоритм Rete.


Литература

1. Альфред В. Ахо, Моника С. Лам, Рави Сети, Джеффри Д. Ульман. Компиляторы принципы, технологии, инструментарий. Вильямс. 2011.

2. Аксенова Е.А., Соколов А.В. Алгоритмы и структуры данных на С++. Петрозаводск, изд-во ПетрГУ, 2008 г.

3. Карманов В.Г. Математическое программирование. М.: Физматлит, 2008.

4. Кнут Д. Искусство программирования. MMIX RISC-компьютер для нового тысячелетия. Вильямс. 2007.

5. Кобзарь А.И. Прикладная математическая статистика. М.: Физматлит, 2006.

6. Лебедев В.И. Функциональный анализ и вычислительная математика. М.: Физматлит, 2005.

7. Мазалов В.В. Математическая теория игр и приложения, Санкт-Петербург, Лань, 1010.

8. Петров И.Б., Лобанов А.И. Лекции по вычислительной математике. М., 2006.

9. Реттиева А.Н. Оптимальность в динамических и вероятностных моделях. Учебное пособие. Петрозаводск: изд-во ПетрГУ, 2011.

10. Страуструп Б. Дизайн и эволюция C++. – М.: ДМК Пресс, СПБ.: Питер, 2007.

11. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. М.: Физматлит, 2005.

12. Турчак Л.И., Плотников П.В. Основы численных методов. М., 2005.

13. Формалев В.Д., Ревизников Д.Л. Численные методы. М., 2006.

14. Халафян А.А. STATISTICA 6. Статистический анализ данных. М.: Бином – Пресс, 2007.

15. Харари Ф. Теория графов. М: ЛИБРОКОМ, 2009.



16. Ермаков С.М. Метод Монте-Карло в вычислительной математике. СПБ.: Бином, 2009.


Достарыңызбен бөлісу:


©kzref.org 2019
әкімшілігінің қараңыз

    Басты бет