[ МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ
УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«КАЗАНСКИЙ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ТЕХНИЧЕСКИЙ
УНИВЕРСИТЕТ им. А.Н. Туполева-КАИ»
ПРОГРАММА ВСТУПИТЕЛЬНОГО ЭКЗАМЕНА В АСПИРАНТУРУ
ПО СПЕЦИАЛЬНОСТИ ВАК 05.13.17
«ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ИНФОРМАТИКИ»
Утверждена на заседании Ученого совета Института технической кибернетики и информатики КНИТУ-КАИ им А.Н. Туполева протокол № 6 от 30.06.2014 Казань 2014ПРОГРАММА
вступительного экзамена в аспирантуру по специальности ВАК 05.13.17 – «Теоретические основы информатики»Настоящая программа разработана в соответствии с паспортом специальности ВАК 05.13. «Теоретические основы информатики». При этом учитывалась специфика научных направлений КНИТУ-КАИ им. А.Н. Туполева. Предполагается, что поступающий в аспирантуру экзаменуется только по темам, отвечающим научному направлению его руководителя.
В основу программы положены следующие дисциплины: теория множеств, логика, автоматы, алгоритмы; методы программирования; теория вероятностей и математическая статистика; теория информации и кодирования; базы данных; схемотехника ЭВМ; вычислительные машины, комплексы, системы и сети; сетевые операционные системы; системы искусственного интеллекта; архитектурноалгоритмические основы параллельных вычислений; параллельное программирование; защита сетевых и пространственных данных.
I. Математические основы информатики Тема 1. Множества, математическая логика и алгоритмы Кардинальные числа.
1.
Операции над множествами. Упорядоченные множества.
2.
Элементы теории нечетких множеств.
3.
Исчисление высказываний и его свойства.
4.
Исчисление предикатов первого порядка и его свойства.
5.
Машины Тьюринга. Тезис Черча.
6.
Эквивалентность некоторых комбинаторных задач.
7.
Классы Р и NP. NP-трудные и NP-полные задачи.
8.
Тема 2. Статистические методы обработки данных Обработка экспериментальных данных.
1.
Закон больших чисел. Центральная предельная теорема.
2.
Cтатистическое оценивание и проверка статистических гипотез.
3.
Понятие о случайной выборке. Оценка параметров по независимым наблюдениям.
4.
Cлучайные процессы. Цепи Маркова.
5.
Многомерный статистический анализ. Компонентный анализ. Факторный анализ. Кластер-анализ.
6.
Классификация без обучения. Дискриминантный анализ. Классификация с обучением.
7.
Множественный ковариационный анализ.
8.
Метод наименьших квадратов.
9.
Множественный корреляционно-регрессионный анализ.
10.
Тема 3. Методы распознавания 1. Проблема распознавания объектов.
2. Обработка априорной информации.
3. Вероятностные системы распознавания.
4. Словарь признаков систем распознавания.
5. Логические системы распознавания.
6. Структурные методы распознавания.
7. Управление процессом распознавания.
8. Эффективность вероятностных и логических систем распознавания.
9. Распознавание в условиях противодействия.
Тема 4. Методы обработки изображений Точечные преобразования изображения. Эквализация.
1.
Преобразование Фурье. Обобщенные функции.
Линейные фильтры. Передаточная функция фильтра.
Теорема Котельникова-Шеннона.
Медианная фильтрация.
Фильтры Собеля и Канни для выделения границ образа.
Преобразование Хафа.
Особые точки изображения. Точки Харриса.
Способ обучения классификатора. Процедура Adaboost.
Трекинг объекта на изображениях.
10.
Тема 5. Модели и алгоритмы анализа данных Основные понятия и принципы анализа данных.
Этапы подготовки данных к анализу.
Понятие технологии KDD и Data Mining.
Методы отбора переменных для формирования обучающих выборок.
Понятие кластеризации. Алгоритм k-means.
Понятие деревьев решений. Алгоритмы построения деревьев решений.
Понятие нейрона и искусственной нейронной сети.
Принципы и алгоритмы обучения нейронных сетей.
Алгоритм обратного распространения ошибки.
Оценка эффективности и сравнение моделей.
10.
Рекомендуемая литература Клини С.К. Введение в метаматематику. – М: Либроком, 2008.
Успенский В.А., Семенов А.Л. Теория алгоритмов: основные открытия и приложения. – М.: Наука, 1987.
Кофман А. Введение в теорию нечетких множеств. – М.: Радио и связь, 1982.
Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979.
Феллер В. Введение в теорию вероятностей и её приложения. В 2-х т. – М.: Мир, Вентцель Е.С., Овчаров А.А. Теория вероятностей и ее инженерные приложения. – М.: Наука 1988.
Барковский С.С., Захаров В.М., Лукашов А.М., Нурутдинова А.Р., Шалагин С.В. Многомерный анализ данных методами прикладной статистики. Учеб. пособие. – Казань: Изд-во КГТУ, 2010.
Мерков А.Б. Распознавание образов. Введение в методы статистического обучения. – М.: Едиториал УРСС, Потапов А.С. Распознавание образов и машинное восприятие – М.: Политехника, 2007.
Горелик А.Л., Скрипкин В.А. Методы распознавания – М.: Высшая школа, 2004.
10.
Форсайт Д., Понс Ж. Компьютерное зрение. Современный подход. – М.: Вильямс, 2004.
11.
Паклин Н.Б., Орешков В.И. Бизнес-аналитика: от данных к знаниям: учебное пособие. 2-е изд. – СПб.:
12.
Барсегян А.А., Куприянов М.С., Холод И.И., Тесс М.Д. Анализ данных и процессов: учебное пособие. 3-е 13.
изд. – СПб.: БХВ-Петербург, 2009.
Кацко И.А., Паклин Н.Б. Практикум по анализу данных на компьютере: Учеб. пособие для вузов. – М.: Издательство "КолосС", 2009.
Ризаев И.С. Интеллектуальный анализ данных для поддержки принятия решений. – Казань: Изд-во МОиН 15.
Тема 1. Представление знаний Понятие искусственного интеллекта. Формы представления знаний.
Логика и формальные системы. Логическое представление знаний.
Семантические сети. Классификация семантических сетей.
Основные задачи, решаемые с использованием семантических сетей.
Понятие сущности. Семантические отношения и их виды. Семантические модели «сущность – связь».
6. Фреймы – системно-структурное описание предметной области. Принципы фрейм-представлений, слоты.
7. Продукционные системы представления знаний.
Тема 2. Эволюционное моделирование Эволюционная методология.
Синергетика.
Генетические алгоритмы.
Нейросети.
Модально-логические подходы.
Тема 3. Информационный поиск Основные понятия и виды поиска.
Информационно-поисковые языки.
Критерии выдачи.
Модели поиска. Стратегия поиска.
Функциональная эффективность поиска.
Поисковые массивы, способы их организации.
Тема 4. Семантическое моделирование 1. Онтология как вычислительная модель предметной области. Интеграции онтологического, когнитивного и событийного моделирования.
2. Семантические инструменты. Языки обработки семантических сетей. Семантические модели решателя интеллектуальных систем.
3. Онтологии и тезаурусы. Формальные онтологии. Построение тезаурусов средствами семантической технологии. Терминологические сети.
4. Исчисление позитивно-образованных формул и автоматическое доказательство теорем.
5. Семантика языков программирования. Онтологическая парадигма программирования.
6. Семантические технологии проектирования баз данных.
7. Семантические технологии проектирования баз знаний.
8. Семантические технологии в информационном поиске.
9. Логико-семантические модели прикладных интеллектуальных систем. Семантические технологии в проектировании. Семантические технологии в образовании.
Тема 5. Экспертные системы Формальные основы и методология построения..
Общая структура и схема функционирования.
Взаимодействие пользователей с ЭС.
Методы поиска решений в ЭС.
Управление функционированием ЭС.
Объяснительные способности ЭС.
Рекомендуемая литература Осипов Г.С. Методы искусственного интеллекта. – М.: Физматлит, 2011.
Рассел С., Норвиг П. Искусственный интеллект. – М.: Вильямс, 2007.
Лорьер Ж.-Л. Системы искусственного интеллекта. – М.: Мир, 1991.
Представление и использование знаний /Под. ред. Х. Уэно, М. Иси-дзука. – М.: Мир, 1989.
Тейз А., Грибомон П., Луи Ж. и др. Логический подход к искусственному интеллекту. От классической логики к логическому программированию. – М.: Мир. 1990.
6. Минский М. Фреймы для представления знаний. – М.: Энергия, 1979.
7. Райхлин В.А. Конструктивное моделирование систем. – Казань: Фн (Наука), 2005.
8. Николис Г., Пригожин И. Познание сложного. – М.: УРС, 2003.
9. Карлов Н.В., Кириченко Н.А. Колебания, волны, структуры. – М.: Физматлит, 2003.
10. Капица С.П., Курдюмов С.П., Малинецкий Г.Г. Синергетика и прогнозы будущего. – М.: Наука, 1997. – Интернет-адрес: http://www.iph.ras.ru/~mifs/kkm/GI1.htm 11. Анохин П.К. Принципиальные вопросы общей теории функциональных систем //Принципы системной организации функций. – М.: Наука, 1973. – Интернет-адрес: http://www.keldysh.ru/pages/BioCyber/RT/ Functional.pdf 12. Малышев Н.Г., Берштейн Л.С., Боженюк А.В. Нечеткие модели для экспертных систем в САПР. – М.:
Энергоатомиздат, 1991.
13. Аверкин А.Н., Батыршин И.З., Блишун А.Ф. Нечеткие множества в моделях управления и искусственного интеллекта /Под ред. Д.А. Поспелова. – М: Наука, 1986.
14. Маннинг К., Рагхаван П., Шютце Х. Введение в информационный поиск. – М.: Вильямс, 2011.
15. Открытые семантические технологии проектирования интеллектуальных систем = Open Semantic Technologies for Intelligent Systems (OSTIS-2012): материалы II Междунар. научн.-техн. конф. /редкол.: В.В.
Голенков (отв. ред.) [и др.]. – Минск : БГУИР, 2012.
16. Открытые семантические технологии проектирования интеллектуальных систем = Open Semantic Technologies for Intelligent Systems (OSTIS-2013): материалы III Междунар. научн.-техн. конф. /редкол.: В. В. Голенков (отв. ред.) [и др.]. – Минск : БГУИР, 2013.
17. Цаленко М.Ш. Моделирование семантики в базах данных. - М.: Наука. Главная редакция физикоматематической литературы, 1989.
18. Барков И.А. Теория конструкторской семантики. – Ижевск: Изд-во ИжГТУ, 2003.
19. Васильев С.Н., Жерлов А.К., Федосов Е.А., Федунов Б.Е. Интеллектное управление динамическими системами. – М.: Физматлит, 2000.
20. Попов Э.В. Экспертные системы: Решение неформализованных задач в диалоге с ЭВМ. – М.: Наука, 1987.
21. Джексон П. Введение в экспертные системы. – М.: Вильямс, 2001.
Тема 1. Автоматы и грамматики Детерминированные конечные автоматы. Диаграммы Мура (системы переходов).
Недетерминированные конечные автоматы.
Автоматные грамматики и конечные автоматы. Регулярные выражения.
Формальные грамматики, их основные классы.
КС-грамматики и деревья выводов в них.
Автоматы с магазинной памятью.
Тема 2. Автоматное программирование Области применения автоматного подхода.
Парадигма автоматного программирования.
Автоматные модели.
Процедурное программирование с явным выделением состояний.
Объектно-ориентированное программирование с явным выделением состояний.
Тема 3. ЯРВ-программирование 1. Основные операции с регулярными выражениями.
2. Строки, кодировки и режимы. Стандартные метасимволы и возможности.
3. Типы механизмов обработки регулярных выражений.
4. Основы поиска совпадений. Максимализм, возврат. Хронометраж. Исключение случайных совпадений.
5. Стандартные оптимизации. Приемы построения быстрых выражений. Раскрутка цикла.
Тема 4. Объектно-ориентированный подход Структура сложных систем.
Объектная модель.
Классы и объекты.
Диаграммы.
Процессы проектирования.
Рекомендуемая литература Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений. – М.: Вильямс, 2002.
Гладкий А. В. Формальные грамматики и языки. — М.: Наука, 1973.
Глушков В.М. Синтез цифровых автоматов. – М.: Физматгиз,1962.
Кобринский Н.Е., Трахтенброт Б.А. Введение в теорию конечных автоматов. – М.: Физматгиз, 1962.
Лавров С. С. Программирование. Математические основы, средства, теория. – СПб.: БХВ-Петербург, 2001.
Дейкстра Э. Взаимодействие последовательных процессов //Языки программирования. – М.: Мир, 1972.
Поликарпова Н. И., Шалыто А. А. Автоматное программирование. – СПб.: Питер, 2008.
Фридл Дж. Регулярные выражения, 3-е издание. – Пер. с англ. – СПб.: Символ-Плюс, 2008.
Ахо А., Сети Р., Ульман Д. Компиляторы. Принципы, технологии, инструменты. – М.: Вильямс, 2002.
Буч Г. Объектно-ориентированный анализ и проектирование с примерами на C++. Второе издание. – М.:
10.
Бином; СПб.: Невский диалект, 2000.
Тема 1. Автоматы и цифровые схемы Синтез автоматов по неформальному заданию.
Минимизация таблиц переходов.
Кодирование состояний автомата.
Состязания в комбинационных схемах.
Состязания в асинхронных последовательностных схемах.
Способы реализации синхронных схем.
Тема 2. Элементы теории модульных структур Многофункциональные логические модули.
Модульные реализации последовательностных схем.
Однородные сети.
Операционные среды.
Тема 3. Системы параллельной обработки данных Ретроспектива и предметные предпосылки параллелизма.
Классификации, тенденции развития и показатели производительности.
Ассоциативные параллельные процессоры.
ОКМД-системы. Банки памяти. Элементы теории коммутационных сетей.
SMP- и MPP-системы. Организация главной памяти. RAID-массивы.
6. Кластерные архитектуры.
7. Суперпроцессоры.
Тема 4. Параллельное программирование Базовое программное обеспечение вычислительного кластера.
Инструментальные средства создания параллельных программ.
Коллективные и парные операции приема и передачи сообщений MPI.
Основные директивы OpenMP.
Особенности технологии CUDA и границы ее применимости.
Иерархия памяти в GPU.
Преимущества подходов OpenCL и OpenACC перед CUDA.
Рекомендуемая литература Райхлин В.А. Основы цифровой схемотехники. Издание второе. – Казань: Изд. КГТУ, 2006.
Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб.: БХВ-Петербург, 2004.
Райхлин В.А. Системы параллельной обработки данных. – Казань: Фн (Наука), 2010.
Илья Федотов. Модели параллельного программирования. – М.: Салон-Пресс, 2012.
А. Линев, Д. Боголепов, С. Бастраков, Технологии параллельного программирования для процессоров новых архитектур. – М.: Изд-во МГУ, 2010.
А. Боресков, А. Харламов и др., Параллельные вычисления на GPU. Архитектура и программная модель CUDA. – М.: Изд-во МГУ, 2012.
Шпаковский Г.И., Серикова Н.В. Программирование для многопроцессорных систем в стандарте MPI – Минск: Изд-во БГУ, 2002.
Митчел, Марк, Оулдем и др. Программирование для Linux. Профессиональный подход – М.: Вильямс, 2003.
Таненбаум Э. Современные операционные системы. 2-е изд. – СПб.: Питер, 2002.
Тема 1. Организация баз данных Языки описания данных.
Концептуальная, внешняя схемы и схема хранения БД.
Модели данных. Целостность БД.
Логическая организация. Физическая организация.
Реляционная модель данных, реляционная алгебра и исчисление. Алгоритмы выполнения реляционных операций.
Структуры данных и языки запросов. Язык SQL.
Оптимизация запросов.
Тема 2. Проектирование баз данных Структуры хранения баз данных, индексы.
Согласованность данных и транзакции.
Обнаружение и разрешение тупиков в транзакционных системах.
Ведение журналов и восстановление после отказов системы и носителей данных.
Защита баз данных.
Параллельные операции над базой данных.
Интегрированные базы данных Тема 3. Управление базами данных Архитектура СУБД.
Серверы баз данных.
Параллельные СУБД на кластерной платформе.
Масштабируемость и эффективность.
Тема 4. Картографические базы данных Классификации и математическая основа географических карт. Создание и использование географических карт.
Ввод, хранение, редактирование и анализ в ГИС. Проектирование ГИС.
Картографическое моделирование.
Основные понятия и механизмы защиты информации в ГИС. Показатели и методики оценки средств безопасности ГИС Защита информации в ГИС на сетевом уровне.
Направления развития пространственных баз данных. Выполнение пространственных операций.
Системы управления защищенными картографическими базами данных.
Рекомендуемая литература Дейт К. Введение в системы баз данных, 6-е изд. – М.: Вильямс, 2000.
Гарсиа-Молина, Ульман, Видом. Системы баз данных. Полный курс. – М.: Вильямс, 2003.
Ульман Дж. Основы систем баз данных. – М.: Финансы и статистика, 1983.
Мартин Дж. Организация баз данных в вычислительных системах. – М.: Мир, 1980.
Озкарахан Э. Машины баз данных и управление базами данных. – М.: Мир, 1989.
Калиниченко Л.А., Рывкин В.М. Машины баз данных и знаний. – М.: Наука, 1990.
Федорук В.Г. Основы языка SQL – Интернет-ресурс http://www.opennet.ru/docs/RUS/sql/index.html.
Смирнов С.Н. Безопасность систем баз данных. – М.: Гелиос АРВ, 2007.
Чекалин С.И. Основы картографии, топографии и инженерной геодезии. Учебное пособие для ВУЗов. – М.:
Академический проект, 2009.
Майкл де Мерс. Географические информационные системы – М.: Дата+, 2000.
10.
Бабенко Л.К., Басан А.С., Журкин И.Г., Макаревич О.Б. Защита данных геоинформационных систем: учеб.
11.
пособие для студентов вузов /Под ред. И.Г. Журкина. – М.: Гелиос АРВ, 2010.
Молдовян А.А., Молдовян Н.А., Советов Б.Я. Криптография. – СПб.: Лань, 2002.
12.
Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии. – М.: Гелиос АРВ, 13.
Рябко Б. Я., Фионов А. Н. Криптографические методы защиты информации: Учебное пособие для вузов. – 14.
М.: Горячая линия – Телеком, 2005.
Балакин А.В., Репалов А, Шагов Г.Н. Современная стеганография: модели и методы преобразования информации. – Ростов-на-Дону: Изд-во СКНЦ ВШ, 2004.
Тема 1. Элементы теории передачи дискретной информации Энтропия и информация. Условная и предельная энтропии.
Источник и получатель сообщений. Классификация дискретных источников.
Кодирование источников дискретных сообщений.
Определение дискретного канала связи. Пропускная способность дискретного канала.
Теорема Шеннона о передаче сообщений по дискретному каналу без памяти. Понятие дискретного канала с памятью.
6. Универсальное кодирование: определение, код Колмогорова-Фитингофа.
Тема 2. Самокорректирующиеся коды Задача помехоустойчивого кодирования.
Определение блоков кодов, исправляющих и обнаруживаемых заданное число ошибок.
Код Хемминга. Задание блоковых кодов. Линейные коды.
Порождающая и проверочная матрицы кода. БЧХ коды.
Границы Гильберта и Варшамова-Гильберта.
Понятие о непрерывном не блоковом помехоустойчивом кодировании, сверточные коды.
Код Витерби.
Тема 3. Сети ЭВМ Разновидности сетей. Основные программные и аппаратные компоненты сети.
Сравнительный анализ различных методов коммутации данных..
Основные функции протоколов передачи данных Типы и особенности каналов передачи данных. Модемы.
Цифровая передача, ее особенности, форматы синхронного потока данных.
Технологии передачи данных в ЛВС. Программное обеспечение ЛВС.
Тема 4. Глобальные и территориально-распределенные сети Технология сетей Х.25.
Технология функционирования сетей Frame Relay.
Основы технологии АТМ.
Стандарты сетей TCP/IP.
Маршрутизация в составной сети с помощью IP-адресов.
Понятие TCP-соединения.
Протоколы прикладного уровня. Информационные сервисы Internet.
Проблема безопасности в сетях. Стратегии защиты сетевых данных. Организация виртуальных локальных сетей для защиты данных в корпоративных сетях.
Тема 5. Сетевые операционные системы Сетевые понятия и протоколы Сетевое программирование в.NET Работа с сокетами Сокеты групповой рассылки Криптография.NET Рекомендуемая литература 1. Вентцель Е.С., Овчаров А.А. Теория вероятностей и ее инженерные приложения. – М.: Наука 1988 г.
2. Попов И.И., Максимов Н.В., Храмцов П.Б. Введение в сетевые информационные ресурсы и технологии:
Учеб. пособие для вузов. – М.: Изд-во РГГУ, 2001.
3. Олифер В.Г., Олифер Н.А. Компьютерные сети. Принципы, технологии, протоколы: Учебник для вузов. 4-е изд. – СПб.: Питер, 2010.
4. Олифер В.Г., Олифер Н.А. Сетевые операционные системы: Учебник для вузов. 2-е изд. – СПб.: Питер, 2008.
5. Троелсен Э. С# и платформа.NET 3.0: Учебник для вузов. Спец. издание. – СПб.: Питер, 2008.
6. Ричард Стивенс. Протоколы TCP/IP. Практическое руководство. – СПб.: БХВ-Санкт-Петербург, 2003.
7. Кеннеди Кларк, Кевин Гамильтон. Принципы коммутации в локальных сетях Cisco. – М.: Вильямс, 2003.
8. Дуглас Э. Камер. Сети TCP/IP. Том 1. Принципы, протоколы и структура. – М.: Вильямс, 2003.
9. Рябко Б.Я., Фионов А.Н. Основы современной криптографии. – М.: Наука и мир, 2004.
Программу разработала комиссия в составе:
Председатель комиссии – Райхлин В.А., д.ф.-м.н., профессор КНИТУ-КАИ.
Члены комиссии – Барков И.А., д.т.н., профессор КНИТУ-КАИ.
«