ТАВРИЧЕСКИЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ имени В.И.ВЕРНАДСКОГО

"Утверждаю"

Председатель Приемной комиссии

(подпись)

"_" 2014 года

ПРОГРАММА

вступительного испытания в аспирантуру по специальной дисциплине по направлению подготовки 02.06.01 – Компьютерные и информационные науки профиль 05.13.17 – Теоретические основы информатики Утверждено на заседании приёмной комиссии Таврического национального университета имени В.И. Вернадского (протокол № 4 от 22 мая 2014 года) Симферополь, Программа вступительного экзамена в аспирантуру по направлению 02.06.01 – Компьютерные и информационные науки профиль 05.13.17 – Теоретические основы информатики Разработана: д.ф-м.н. проф. Донской В.И., д.ф-м.н. проф. Щербина О.А.

Рассмотрено и утверждено на заседании кафедры информатики:

Протокол № 9 от 4 апреля 2014 г.

Заведующий кафедрой информатики_ д.ф-м.н. проф. Донской В.И.

Утверждено на заседании Ученого совета факультета математики и информатики Протокол № 8 от 15 апреля 2014 г.

Председатель Ученого Совета доц. Рудницкий О.И.

ДИФФЕРЕНЦИАЛЬНОЕ И ИНТЕГРАЛЬНОЕ ИСЧИСЛЕНИЕ

ФУНКЦИЙ ОДНОЙ ПЕРЕМЕННОЙ

Производная и дифференциал. Основные теоремы дифференциального исчисления и их приложения. Теоремы Ролля, Лагранжа, Коши. Правило Лопиталя. Формула Тейлора. Признаки постоянства, возрастание и убывание функции в точке и на промежутке. Максимум и минимум. Необходимое условие экстремума. Достаточное условие максимума и минимума. Нахождение наибольших и наименьших значений.

Неопределенный интеграл. Задача восстановления функции по ее производной.

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

Определенный интеграл. Необходимое и достаточное условия интегрируемости.

Интегрируемость монотонной и непрерывной функции. Интегрируемость ограниченной функции с конечным числом точек разрыва. Основные свойства определенного интеграла. Теорема о среднем значении. Определенный интеграл с переменным верхним пределом. Существование первообразной функции. Формула Ньютона-Лейбница. Интегрирование по частям и замена переменной.

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

РЯДЫ Числовые ряды. Признаки Даламбера и Коши. Интегральный признак сходимости.

Знакочередующиеся ряды, теорема Лейбница. Абсолютно сходящиеся ряды.

Перестановка членов абсолютно сходящегося ряда. Условно сходящиеся ряды.

Теорема Римана. Задача разложения функции в степенной ряд. Ряд Тейлора.

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

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

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

Ряды Фурье.

Степенные ряды. Понятие, интервал и радиус сходимости. Теорема Абеля.

Равномерная сходимость степенного ряда. Интегрирование и дифференцирование степенных рядов.

ДИФФЕРЕНЦИАЛЬНЫЕ УРАВНЕНИЕ

Элементы общей теории обыкновенных дифференциальных уравнений. Теорема о существовании и единственности решения нормальной системы уравнений.

Сведение уравнения n-го порядка к нормальной системе уравнений.

Линейные уравнения. Теорема о существовании и единственности решения нормальной системы линейных уравнений. Пространство решений однородного линейного уравнения n-го порядка. Фундаментальные системы решений, общее решение. Вронскиан. Формула Остроградского. Неоднородное линейное уравнение и вид его общего решения. Метод вариаций постоянных. Линейное уравнение второго порядка с постоянными коэффициентами. Свободные и вынужденные колебания. Резонанс.

ДИСКРЕТНАЯ МАТЕМАТИКА И МАТЕМАТИЧЕСКАЯ КИБЕРНЕТИКА

Класс P2. Элементарные булевы функции. Полиномы Жегалкина. Замкнутые классы и полнота. Критерий Поста.

Класс Pk. Элементарные функции k-значной логики. Разложения функций. Критерии полноты в Pk. Дизъюнктивные нормальные формы. Задачи минимизации ДНФ.

Локальные алгоритмы Ю.И. Журавлева, основанные на понятии окрестности конъюнкции. Оценивание числа дискретных объектов. Асимптотическое оценивание числа функций, ДНФ, комбинаторных формул.

Понятие конечного автомата. Основные способы задания конечных автоматов.

Ограниченно-детерминированные функции. Анализ поведения конечного автомата.

Синтез конечных автоматов.

Коды с исправлением ошибок. Линейные коды. Алфавитное кодирование.

Критерий однозначности декодирования. Алгоритм распознавания однозначности декодирования. Свойства взаимно однозначных кодов. Коды с минимальной избыточностью. Циклические коды. Коды Хэмминга.

МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ

Исчисления. Язык L исчисления высказывания. Язык Pr исчисления предикатов 1-го порядка. Язык Ar формальной арифметики. Теорема Гёделя о неполноте формальной арифметики.

Формальное определение алгоритма: алгоритмические модели Тьюринга, Маркова и рекурсивные функции. Операции примитивной рекурсии и минимизации.

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

ТЕОРИЯ СЛОЖНОСТИ ВЫЧИСЛЕНИЙ

Классы P, NP, NPC, NPH. Полиномиальная сводимость. Жадные алгоритмы.

Матроиды. Теорема Радо-Эдмондса. Графовый матроид. Матроиды и линейная независимость.

МЕТОДЫ ОПТИМИЗАЦИИ, ИССЛЕДОВАНИЕ ОПЕРАЦИЙ

И ТЕОРИЯ ИГР

Основные понятия оптимизации. Математическое и квадратичное программирование. Линейное и дискретное программирование. Некорректные и несобственные задачи.

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

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

Управление стохастическими процессами.

Марковские процессы с дискретным и с непрерывным временем. Управляемые марковские процессы. Системы массового обслуживания. Метод имитационного моделирования.

Принятие решений в условиях многокритериальности, неопределенности и конфликта. Многокритериальное программирование и основные понятия теории игр. Матричные игры. Бескоалиционные игры n лиц. Коалиционные игры.

Динамические задачи управления в условиях конфликта. Позиционные игры. Игры с повторениями. Иерархические игры.

ТЕОРИЯ РАСПОЗНАВАНИЯ ОБРАЗОВ

И ИСКУССТВЕННОГО ИНТЕЛЛЕКТА

Постановка задачи обучения распознаванию. Алгоритмы (методы) обучения и решающие правила: виды и классы. Нейронные сети, потенциальные функции, решающие деревья. Детерминированные задачи распознавания.

Детерминированная постановка задачи построения разделяющих границ.

Стохастические задачи распознавания образов. Задачи распознавания образов в условии неопределенности. Задачи распознавания в условиях неопределенности и конфликта.

Алгебраический подход к синтезу алгоритмов распознавания Ю.И. Журавлева.

Элементы теории Вапника-Червоненкиса: ёмкость семейств решающих правил, оценка равномерной сходимости частот ошибок на обучающей выборке к вероятностям ошибок.

Понятие обучаемости. Устойчивость алгоритмов обучения и обучаемость.

Логические продукционные системы. Базы знаний. Фреймы для представления знаний. Извлечение знаний из эмпирических данных. Экспертные системы.

ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА

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

Среднеквадратические приближения: существование элемента наилучшего приближения, способы его нахождения. Алгебраический интерполяционный многочлен, оценка погрешности интерполяции. Численное вычисление производной. Формулы численного интегрирования, оценка погрешности.

СИСТЕМНОЕ ПРОГРАММИРОВАНИЕ

КС-грамматики. Деревья вывода. Нормальные формы Хомского. Свойства КСязыков.

Определение синтаксически-ориентированного перевода. Нисходящий и восходящий разборы.

Основные принципы объектно-ориентированного программирования:

инкапсуляция, наследование, полиморфизм. Их характеристики и способы реализации.

Классы как пользовательские типы данных. Члены классов (данные, методы).

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

Понятие абстрактных типов данных (АТД). Линейный список, Стек, Очередь.

Способы их реализации (последовательный, связанный).

Бинарные деревья поиска. Сложностные оценки операций поиска, добавления и удаления узлов в двоичном дереве поиска.

Способы записи арифметических выражений (инфиксная, префиксная, постфиксная). Алгоритмы вычисления арифметических выражений.

Планирование и диспетчеризация процессов и задач. Стратегии планирования.

Дисциплины диспетчеризации.

Виртуальное адресное пространство. Сегментный, страничный и сегментностраничный способы организации виртуальной памяти.

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

Формальные основы проектирования реляционных баз данных: функциональные зависимости, декомпозиция схем отношений, нормальные формы схем отношений.

Структуры индексов: плотные и разреженные индексы, деревья и хеш-таблицы.

Алгоритмы обработки данных, основанные на сортировке и хешировании.

Компьютерные сети. Протоколы, интерфейс.

На подготовку к экзамену (3 вопроса) отводится до 2 часов времени.

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

Ответ на каждый вопрос оценивается от 0 до 20 баллов. Максимальная сумма баллов – 60. Минимальная необходимая для поступления сумма – 25 баллов.

Критерии оценивания ответа на каждый вопрос.

Дан полный ответ, продемонстрировано знание предмета и навыки устного изложения – 20 баллов.

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

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

Ответ схематичен, но отражает существо вопроса и не содержит грубых ошибок – 6-9 баллов.

Ответ не раскрывает существа вопроса или допущены грубые ошибки – 0- баллов.

Пересчет оценок в другие шкалы:

Литература 1. Кудрявцев Л.Д. Курс математического анализа. т. 1,2,3. – М.:, 1988.

2. Яблонский С.В. Дискретная математика. – М.: Наука, 1984.

3. Понтрягин Л.С. Обыкновенные дифференциальные уравнения. -М.:, 1978.

4. Самарский А.А., Гулин А.В. Численные методы. – М., 1989.

5. Турчак Л.И. Основы численных методов. – М., 1987.

6. Глушков В.М. Синтез цифровых автоматов. – М.: Физматгиз, 1962.

7. Дискретная математика и математическая кибернетика. –Т.1. – М.: Наука, 8. В.Л. Матросов, В.А. Горелик, С.А. Жданов, О.В. Муравьева, Б.З. Угольникова.

Теоретические основы информатики. Учебное пособие. –М.: МПГУ, 2005.

9. В.А.Горелик, Т.П.Фомина Основы исследования операций: Учебное пособие.

МПГУ, Липецкий ГУ. –М.:, 2004.

10. Вапник В.Н., Червоненкис А.Я. Теория распознавания образов. – М.: Наука, 11. Донской В.И. Алгоритмические модели обучения классификации:

обоснование, сравнение, выбор. – Симферополь: ДИАЙПИ, 2014.

12. Стюарт Рассел, Питер Норвиг. Искусственный интеллект: современный подход. – Киев: Издательский дом “Вильямс”. – 2006.

13. Ахо А., Сети Р., Ульман Д. Компиляторы: принципы, технологии, инструменты. – М.:. Издательский дом "Вильяме", 2001.

14. Таненбаум Э.С.Современные операционные системы.2-ое изд. – Спб.:Питер, 15. Гормеев А.В., Молчанов. Системное программное обеспечение. – СПб.:

Питер, 2001.

16. Ахо А., Хопкрофт Дж., Ульман Д. Структуры данных и алгоритмы. – М.: Издво "Вильямс,2000.

17. Олифер В. Г., Олифер Н. А. Компьютерные сети. Принципы, технологии, протоколы: Учебник для вузов. 4-е изд. — СПб.: Питер, 2010.

18. Льюис Ф., Розенкранц Д., Стирнз Р. Теоретические основы проектирования компиляторов. –М.:Мир, 1979.