Программа вступительного экзамена в аспирантуру по специальности ВАК 05.13.17 - «Теоретические основы информатики»
Программа вступительного экзамена в аспирантуру по специальности ВАК 05.13.17 - «Теоретические основы информатики»
Настоящая программа разработана в соответствии с паспортом специальности ВАК 05.13.17 «Теоретические основы информатики». При этом учитывалась специфика научных направлений НИИ ПС АН РТ. Предполагается, что поступающий в аспирантуру экзаменуется только по темам, отвечающим научному направлению его руководителя.
В основу программы положены следующие дисциплины: теория множеств, логика, автоматы, алгоритмы; методы программирования; теория вероятностей и математическая статистика; теория информации и кодирования; базы данных; схемотехника ЭВМ; вычислительные машины, комплексы, системы и сети; сетевые операционные системы; системы искусственного интеллекта; архитектурно-алгоритмические основы параллельных вычислений; параллельное программирование; защита сетевых и пространственных данных.
I. Математические основы информатики
Тема 1. Множества, математическая логика и алгоритмы
1. Кардинальные числа.
2. Операции над множествами. Упорядоченные множества.
3. Элементы теории нечетких множеств.
4. Исчисление высказываний и его свойства.
5. Исчисление предикатов первого порядка и его свойства.
6. Машины Тьюринга. Тезис Черча.
7. Эквивалентность некоторых комбинаторных задач.
8. Классы Р и NP. NP-трудные и NP-полные задачи.
Тема 2. Статистические методы обработки данных
1. Обработка экспериментальных данных.
2. Закон больших чисел. Центральная предельная теорема.
3. Статистическое оценивание и проверка статистических гипотез.
4. Понятие о случайной выборке. Оценка параметров по независимым наблюдениям.
5. Случайные процессы. Цепи Маркова.
6. Многомерный статистический анализ. Компонентный анализ. Факторный анализ. Кластер-анализ.
7. Классификация без обучения. Дискриминантный анализ. Классификация с обучением.
8. Множественный ковариационный анализ.
9. Метод наименьших квадратов.
10. Множественный корреляционно-регрессионный анализ.
Тема 3. Методы распознавания
1. Проблема распознавания объектов.
2. Обработка априорной информации.
3. Вероятностные системы распознавания.
4. Словарь признаков систем распознавания.
5. Логические системы распознавания.
6. Структурные методы распознавания.
7. Управление процессом распознавания.
8. Эффективность вероятностных и логических систем распознавания.
9. Распознавание в условиях противодействия.
Тема 4. Методы обработки изображений
1. Точечные преобразования изображения. Эквализация.
2. Преобразование Фурье. Обобщенные функции.
3. Линейные фильтры. Передаточная функция фильтра.
4. Теорема Котельникова-Шеннона.
5. Медианная фильтрация.
6. Фильтры Собеля и Канни для выделения границ образа.
7. Преобразование Хафа.
8. Особые точки изображения. Точки Харриса.
9. Способ обучения классификатора. Процедура Adaboost.
10. Трекинг объекта на изображениях.
Тема 5. Модели и алгоритмы анализа данных
1. Основные понятия и принципы анализа данных.
2. Этапы подготовки данных к анализу.
3. Понятие технологии KDD и DataMining.
4. Методы отбора переменных для формирования обучающих выборок.
5. Понятие кластеризации. Алгоритм k-means.
6. Понятие деревьев решений. Алгоритмы построения деревьев решений.
7. Понятие нейрона и искусственной нейронной сети.
8. Принципы и алгоритмы обучения нейронных сетей.
9. Алгоритм обратного распространения ошибки.
10. Оценка эффективности и сравнение моделей.
Рекомендуемая литература
1. Клини С.К. Введение в метаматематику. - М: Либроком, 2008.
2. Успенский В.А., Семенов А.Л. Теория алгоритмов: основные открытия и приложения. - М.: Наука, 1987.
3. Кофман А. Введение в теорию нечетких множеств. - М.: Радио и связь, 1982.
4. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. - М.: Мир, 1979.
5. Феллер В. Введение в теорию вероятностей и её приложения. В 2-х т. - М.: Мир, 1982
6. Вентцель Е.С., Овчаров А.А. Теория вероятностей и ее инженерные приложения. - М.: Наука 1988.
7. Барковский С.С., Захаров В.М., Лукашов А.М., Нурутдинова А.Р., Шалагин С.В. Многомерный анализ данных методами прикладной статистики. Учеб. пособие. - Казань: Изд-во КГТУ, 2010.
8. Мерков А.Б. Распознавание образов. Введение в методы статистического обучения. - М.: Едиториал УРСС, 2011.
9. Потапов А.С. Распознавание образов и машинное восприятие - М.: Политехника, 2007.
10. Горелик А.Л., Скрипкин В.А. Методы распознавания - М.: Высшая школа, 2004.
11. Форсайт Д., Понс Ж. Компьютерное зрение. Современный подход. - М.: Вильямс, 2004.
12. Паклин Н.Б., Орешков В.И. Бизнес-аналитика: от данных к знаниям: учебное пособие. 2-е изд. - СПб.: Питер, 2013.
13. Барсегян А.А., Куприянов М.С., Холод И.И., Тесс М.Д. Анализ данных и процессов: учебное пособие. 3-е изд. - СПб.: БХВ-Петербург, 2009.
14. Кацко И.А., Паклин Н.Б. Практикум по анализу данных на компьютере: Учеб. пособие для вузов. - М.: Издательство "КолосС", 2009.
15. Ризаев И.С. Интеллектуальный анализ данных для поддержки принятия решений. - Казань: Изд-во МОиН РТ, 2011.
II. Искусственный интеллект
Тема 1. Представление знаний
1. Понятие искусственного интеллекта. Формы представления знаний.
2. Логика и формальные системы. Логическое представление знаний.
3. Семантические сети. Классификация семантических сетей.
4. Основные задачи, решаемые с использованием семантических сетей.
5. Понятие сущности. Семантические отношения и их виды. Семантические модели «сущность - связь».
6. Фреймы - системно-структурное описание предметной области. Принципы фрейм-представлений, слоты.
7. Продукционные системы представления знаний.
Тема 2. Эволюционное моделирование
Эволюционная методология.
Синергетика.
Генетические алгоритмы.
Нейросети.
Модально-логические подходы.
Тема 3. Информационный поиск
1. Основные понятия и виды поиска.
2. Информационно-поисковые языки.
3. Критерии выдачи.
4. Модели поиска. Стратегия поиска.
5. Функциональная эффективность поиска.
6. Поисковые массивы, способы их организации.
Тема 4. Семантическое моделирование
1. Онтология как вычислительная модель предметной области. Интеграции онтологического, когнитивного и событийного моделирования.
2. Семантические инструменты. Языки обработки семантических сетей. Семантические модели решателя интеллектуальных систем.
3. Онтологии и тезаурусы. Формальные онтологии. Построение тезаурусов средствами семантической технологии. Терминологические сети.
4. Исчисление позитивно-образованных формул и автоматическое доказательство теорем.
5. Семантика языков программирования. Онтологическая парадигма программирования.
6. Семантические технологии проектирования баз данных.
7. Семантические технологии проектирования баз знаний.
8. Семантические технологии в информационном поиске.
9. Логико-семантические модели прикладных интеллектуальных систем. Семантические технологии в проектировании. Семантические технологии в образовании.
Тема 5. Экспертные системы
1. Формальные основы и методология построения..
2. Общая структура и схема функционирования.
3. Взаимодействие пользователей с ЭС.
4. Методы поиска решений в ЭС.
5. Управление функционированием ЭС.
6. Объяснительные способности ЭС.
Рекомендуемая литература
1. Осипов Г.С. Методы искусственного интеллекта. - М.: Физматлит, 2011.
2. Рассел С., Норвиг П. Искусственный интеллект. - М.: Вильямс, 2007.
3. Лорьер Ж.-Л. Системы искусственного интеллекта. - М.: Мир, 1991.
4. Представление и использование знаний /Под. ред. Х. Уэно, М. Иси-дзука. - М.: Мир, 1989.
5. Тейз А., Грибомон П., Луи Ж. и др. Логический подход к искусственному интеллекту. От классической логики к логическому программированию. - М.: Мир. 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. Открытые семантические технологии проектирования интеллектуальных систем = OpenSemanticTechnologiesforIntelligentSystems (OSTIS-2012): материалы II Междунар. научн.-техн. конф. /редкол.: В.В. Голенков (отв. ред.) [и др.]. - Минск : БГУИР, 2012.
16. Открытые семантические технологии проектирования интеллектуальных систем = OpenSemanticTechnologiesforIntelligentSystems (OSTIS-2013): материалы III Междунар. научн.-техн. конф. /редкол.: В. В. Голенков (отв. ред.) [и др.]. - Минск : БГУИР, 2013.
17. Цаленко М.Ш. Моделирование семантики в базах данных. - М.: Наука. Главная редакция физикоматематической литературы, 1989.
18. Барков И.А. Теория конструкторской семантики. - Ижевск: Изд-во ИжГТУ, 2003.
19. Васильев С.Н., Жерлов А.К., Федосов Е.А., Федунов Б.Е. Интеллектное управление динамическими системами. - М.: Физматлит, 2000.
20. Попов Э.В. Экспертные системы: Решение неформализованных задач в диалоге с ЭВМ. - М.: Наука, 1987.
21. Джексон П. Введение в экспертные системы. - М.: Вильямс, 2001.
IV. Схемо- и системотехника
Тема 1. Автоматы и цифровые схемы
1. Синтез автоматов по неформальному заданию.
2. Минимизация таблиц переходов.
3. Кодирование состояний автомата.
4. Состязания в комбинационных схемах.
5. Состязания в асинхронных последовательностных схемах.
6. Способы реализации синхронных схем.
Тема 2. Элементы теории модульных структур
1. Многофункциональные логические модули.
2. Модульные реализации последовательностных схем.
3. Однородные сети.
4. Операционные среды.
Тема 3. Системы параллельной обработки данных
1. Ретроспектива и предметные предпосылки параллелизма.
2. Классификации, тенденции развития и показатели производительности.
3. Ассоциативные параллельные процессоры.
4. ОКМД-системы. Банки памяти. Элементы теории коммутационных сетей.
5. SMP- и MPP-системы. Организация главной памяти. RAID-массивы.
6. Кластерные архитектуры.
7. Суперпроцессоры.
Тема 4. Параллельное программирование
1. Базовое программное обеспечение вычислительного кластера.
2. Инструментальные средства создания параллельных программ.
3. Коллективные и парные операции приема и передачи сообщений MPI.
4. Основные директивы OpenMP.
5. Особенности технологии CUDA и границы ее применимости.
6. Иерархия памяти в GPU.
7. Преимущества подходов OpenCL и OpenACC перед CUDA.
1. Райхлин В.А. Основы цифровой схемотехники. Издание второе. - Казань: Изд. КГТУ, 2006.
2. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2004.
3. Райхлин В.А. Системы параллельной обработки данных. - Казань: Фэн (Наука), 2010.
4. Илья Федотов. Модели параллельного программирования. - М.: Салон-Пресс, 2012.
5. А. Линев, Д. Боголепов, С. Бастраков, Технологии параллельного программирования для процессоров новых архитектур. - М.: Изд-во МГУ, 2010.
6. А. Боресков, А. Харламов и др., Параллельные вычисления на GPU. Архитектура и программная модель CUDA. - М.: Изд-во МГУ, 2012.
7. Шпаковский Г.И., Серикова Н.В. Программирование для многопроцессорных систем в стандарте MPI - Минск: Изд-во БГУ, 2002.
8. Митчел, Марк, Оулдем и др. Программирование для Linux. Профессиональный подход - М.: Вильямс, 2003.
9. Таненбаум Э. Современные операционные системы. 2-е изд. - СПб.: Питер, 2002.
V. Системы баз данных
Тема 1. Организация баз данных
1. Языки описания данных.
2. Концептуальная, внешняя схемы и схема хранения БД.
3. Модели данных. Целостность БД.
4. Логическая организация. Физическая организация.
5. Реляционная модель данных, реляционная алгебра и исчисление. Алгоритмы выполнения реляционных операций.
6. Структуры данных и языки запросов. Язык SQL.
7. Оптимизация запросов.
Тема 2. Проектирование баз данных
1. Структуры хранения баз данных, индексы.
2. Согласованность данных и транзакции.
3. Обнаружение и разрешение тупиков в транзакционных системах.
4. Ведение журналов и восстановление после отказов системы и носителей данных.
5. Защита баз данных.
6. Параллельные операции над базой данных.
7. Интегрированные базы данных
Тема 3. Управление базами данных
1. Архитектура СУБД.
2. Серверы баз данных.
3. Параллельные СУБД на кластерной платформе.
4. Масштабируемость и эффективность.
Тема 4. Картографические базы данных
1. Классификации и математическая основа географических карт. Создание и использование географических карт.
2. Ввод, хранение, редактирование и анализ в ГИС. Проектирование ГИС.
3. Картографическое моделирование.
4. Основные понятия и механизмы защиты информации в ГИС. Показатели и методики оценки средств безопасности ГИС
5. Защита информации в ГИС на сетевом уровне.
6. Направления развития пространственных баз данных. Выполнение пространственных операций.
7. Системы управления защищенными картографическими базами данных.
Рекомендуемая литература
1. Дейт К. Введение в системы баз данных, 6-е изд. - М.: Вильямс, 2000.
2. Гарсиа-Молина, Ульман, Видом. Системы баз данных. Полный курс. - М.: Вильямс, 2003.
3. Ульман Дж. Основы систем баз данных. - М.: Финансы и статистика, 1983.
4. Мартин Дж. Организация баз данных в вычислительных системах. - М.: Мир, 1980.
5. Озкарахан Э. Машины баз данных и управление базами данных. - М.: Мир, 1989.
6. Калиниченко Л.А., Рывкин В.М. Машины баз данных и знаний. - М.: Наука, 1990.
7. Федорук В.Г. Основы языка SQL - Интернет-ресурс http://www.opennet.ru/docs/RUS/sql/index.html.
8. Смирнов С.Н. Безопасность систем баз данных. - М.: Г елиос АРВ, 2007.
9. Чекалин С.И. Основы картографии, топографии и инженерной геодезии. Учебное пособие для ВУЗов. - М.: Академический проект, 2009.
10. Майкл де Мерс. Географические информационные системы - М.: Дата+, 2000.
11. Бабенко Л.К., Басан А.С., Журкин И.Г., Макаревич О.Б. Защита данных геоинформационных систем: учеб. пособие для студентов вузов /Под ред. И.Г. Журкина. - М.: Гелиос АРВ, 2010.
12. Молдовян А.А., Молдовян Н.А., Советов Б.Я. Криптография. - СПб.: Лань, 2002.
13. Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии. - М.: Гелиос АРВ, 2005.
14. Рябко Б. Я., Фионов А. Н. Криптографические методы защиты информации: Учебное пособие для вузов. - М.: Горячая линия - Телеком, 2005.
15. Балакин А.В., Репалов А, Шагов Г.Н. Современная стеганография: модели и методы преобразования информации. - Ростов-на-Дону: Изд-во СКНЦ ВШ, 2004.
Программу разработала комиссия в составе:
Председатель комиссии: д.т.н., профессор Сулейманов Д.Ш.
Члены комиссии: к.т.н., доцент Невзорова О.А.
к.ф.-м.н., доцент Гильмуллин Р.А.
к.т.н., доцент Гатиятуллин А.Р.