|
Вступительный экзамен по специальности 05.13.17 |
Программа вступительного экзамена в аспирантуру по специальности 05.13.17 «Теоретические основы информатики»
Скачать документ
Технические и физико-математические науки
А. ОБЩАЯ ЧАСТЬ.
I.Теория информации и случайные события.
- Энтропия и информация. Условная и предельная энтропии.
- Средняя длина кодового слова и избыточность.
- Теорема Шеннона-Фано и Хаффмана.
- Кодирование непрерывных сообщений.
- Разложение сигналов, порождаемых источником, в обобщенный ряд Фурье по ортогональным функциям.
- Теорема Шеннона о передаче сообщений по дискретному каналу без памяти.
- Зависимость и независимость случайных событий и случайных величин.
- Марковские цепи и их задание.
- Марковские процессы.
- Уравнение Колмогорова для переходных вероятностей марковских процессов.
Литература:
- Галлагер Р. Теория информации и надежная связь. — М.: Сов. радио, 1974.
- И.И.Гихман, А.В.Скороход. Теория случайных процессов. Т.2 — М.: Наука, 1971.
II. Основы теории множеств и математической логики.
- Счетные множества.
- Кардинальные числа.
- Теорема эквивалентности.
- Операции над множествами.
- Отношения на множествах.
- Упорядоченные множества.
- Исчисление высказываний.
- Исчисление предикатов первого порядка.
- Модальные исчисления.
- Теорема Геделя о неполноте арифметики.
Литература:
- С.К.Клини. Введение в метаматематику. — Книжный дом "Либроком", 2008.
III. Основы теории алгоритмов.
- Машины Тьюринга.
- Нормальные алгорифмы Маркова.
- Анализ сложности алгоритма сортировки Шелла.
- Алгоритмы глобального анализа графов.
- Эквивалентность некоторых комбинаторных задач. Классы Р и NP. NP-трудные и NP-полные задачи.
Литература:
- Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — М.: МЦНМО, 1999.
- Косовский Н.К. Основы теории элементарных алгоритмов. — Л.: Изд. Ленингр. ун-та, 1987.
- Успенский В.А., Семенов А.Л. Теория алгоритмов: основные открытия и приложения. — М.: Наука, 1987.
- Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. — М.: Мир, 1998.
- Кнут Дональд. Искусство программирования, том 1. Основные алгоритмы (3-е изд.). — Издательский дом "Вильямс", 2000.
IV.Теория графов.
- Общие сведения о графах и их характеристиках.
- Эйлеровы и гамильтоновы графы.
- Паросочетания и алгоритм построения наибольшего паросочетания в двудольном графе.
- Алгоритм разбиения частично упорядоченного множества на минимальное число цепей.
- Взвешенные графы и задачи о кратчайших маршрутах и остовах минимального веса.
- Плоские графы и их основные свойства,
Литература:
- Харари Ф.,Палмер Д. Перечисление графов. — М.: Мир, 1982.
V. Теория формальных языков и грамматик.
- Формальные грамматики, их основные классы. КС-грамматики и деревья выводов в них. Приведенные и неукорачивающие КС-грамматики. Нормальные формы неукорачивающих КС-грамматик.
- Однозначность и существенная неоднозначность КС-языков. Примеры не КС-языков.
- Автоматные грамматики и конечные автоматы. Регулярные выражения.
- МП-автоматы различных типов, их эквивалентность КС-грамматикам. Детерминированные автоматы и языки, их основные свойства.
- LR(k)-грамматики и языки, их основные свойства.
Литераура:
- Гладкий А. В. Формальные грамматики и языки. — М.: Наука, 1973.
- Рейуорд-Смит В. Дж. Теория формальных языков. Вводный курс. — М.: Радио и связь, 1988.
- Саломаа А. Жемчужины теории формальных языков. — М.: Мир, 1986.
VI. Теория автоматов.
- Детерминированные конечные автоматы (ДКА).
- Диаграммы Мура (системы переходов). Язык ДКА.
- Недетерминированные конечные автоматы (НКА). Язык НКА.
- Конечные автоматы с пустыми переходами.
- Теорема об устранении пустых переходов.
- Операции над конечными автоматами.
- Эквивалентность и минимизация конечных автоматов.
- Проверка эквивалентности состояний.
- Алгоритм минимизации ДКА.
Литература:
- Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений. — Издательский дом "Вильямс", 2002.
- Дудкин В.С., Исмаилов Р.Ш., Крайников А.В. Синтез конечных автоматов: Учебное пособие ; Под ред. В.Б. Смолова. — Л.: ЛЭТИ, 1987.
VII. Трансляция.
- Определение трансляции как формального объекта. Некоторые способы задания трансляций: явное перечисление элементов, гомоморфизм, схема синтаксически-управляемой трансляции, конечный и магазинный преобразователь, магазинный процессор.
- Простые синтаксически-управляемые трансляции. Эквивалентность простых схем синтаксически-управляемых трансляций и недетерминированных магазинных преобразователей.
- Эквивалентность магазинных преобразователей, реализующих трансляции при конечном состоянии и при пустом магазине.
- Простые семантически однозначные схемы синтаксически-управляемых трансляций и детерминированные магазинные преобразователи. Генерация выхода простой семантически однозначной трансляции по левостороннему анализу входа посредством детерминированного магазинного преобразователя.
- Определение класса LL(k)-грамматик. Необходимые и достаточные признаки LL(k)-грамматик.
Литература:
- Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. В 2-х т. — М.: Мир, 1978.
- Мартыненко Б. К. Синтаксически управляемая обработка данных. — СПб.: Изд-во СПбГУ, 1997.
- Фитиалов С. Я. Формальные грамматики. — Л.: Изд-во ЛГУ, 1984.
VIII. Языки программирования.
- Языки программирования. Основные понятия и определения. История и эволюция. Классификация языков. Проблемы и перспективы развития.
- Языковые абстракции: абстракция данных, абстракция управления, абстракция модульности.
- Языки моделирования. Моделирование на основе структурной методологии.
- Моделирование на основе объектно-ориентированной методологии.
- Языки программирования высокого уровня: обзор языков, ориентированных на предметную область.
- Языки программирования для задач искусственного интеллекта (LISP, Рефал).
- Естественные языки. Особенности естественных языков и культурных сред.
- Семантический анализ естественных языков. Интернационализация и локализация программных продуктов.
Литература:
- Пратт Т., Зелковиц М. Языки программирования: разработка и реализация. 4-е издание. — СПб.: Питер, 2002.
- Себеста Р. У. Основные концепции языков программирования, 5-е изд. — Издательский дом "Вильямс", 2001.
- Бабаев И.О., Герасимов М.А., Косовский Н.К. Интеллектуальное программирование. Турбо Пролог и Рефал-5 на персональных компьютерах. — СПб.: Издательство СПбУ, 1992.
Б. СПЕЦИАЛЬНАЯ ЧАСТЬ.
X. Представление знаний и базы знаний.
- Семантические сети.
- Системы фреймов.Системы правил (продукционные системы).Онтологии.
- Представление событий и ситуаций в базах знаний.
- Представление действий в базах знаний.
- Инструментальные средства представления знаний.
XI. Приобретение знаний.
- Методы обучения по примерам.
- Индуктивные методы обучения по примерам.
- Вероятностные методы распознавания образов.
- Непараметрические методы распознавания образов.
- Алгебраический подход к распознаванию образов.
- Извлечение знаний из текстов.
- Интерактивные (прямые) методы приобретения знаний.
XII. Рассуждения.
- Дедуктивные рассуждения и методы их автоматизации.
- Индуктивные рассуждения и методы их автоматизации.
- Абдуктивные рассуждения и аргументация.
- Рассуждения по аналогии и по прецедентам.
- Рассуждения о пространстве и времени.
- Индуктивный синтез программ.
XIII. Динамика в интеллектуальных системах.
- Планирование в пространстве состояний.
- Поиск в пространстве планов.
- Планирование на основе удовлетворения ограничений.
- Планирование на основе прецедентов.
- Моделирование поведения. Интеллектуальные динамические системы.
Литература:
- Н. Нильсон. Искусственный интеллект. Методы поиска решений. — М: Мир, 1973.
- Ю.И.Журавлев. Избранные научные труды. М.: Магистр, 1998.
- Г.С.Осипов. Лекции по искусственному интеллекту. М.:URSS, 2009.
- Г.С. Осипов Приобретение знаний интеллектуальными системами. — М.: Наука Физматлит, 1997.
- Г.С.Осипов. Методы искусственного интеллекта. М.: Физматлит, 2011.
- Гаврилова Т. А. Хорошевский В.Ф. Базы данных интеллектуальных систем. Учебное пособие. — СПб.: Питер, 2001.
- Рассел С. Норвиг П. Искусственный интеллект. — Издательский дом "Вильямс", 2007.
|
|
