Академия наук Республики Татарстан

Программа вступительного испытания в аспирантуру по дисциплине – Теоретические основы информатики

1. Кардинальные числа.

2. Операции над множествами. Упорядоченные множества.

3. Элементы теории нечетких множеств.

4. Исчисление высказываний и его свойства.

5. Исчисление предикатов первого порядка и его свойства.

6. Машины Тьюринга. Тезис Черча.

7. Эквивалентность некоторых комбинаторных задач.

8. Классы Р и NP. NP-трудные и NP-полные задачи.

1. Обработка экспериментальных данных.

2. Закон больших чисел. Центральная предельная теорема.

3. Статистическое оценивание и проверка статистических гипотез.

4. Понятие о случайной выборке. Оценка параметров по независимым наблюдениям.

5. Случайные процессы. Цепи Маркова.

6. Многомерный статистический анализ. Компонентный анализ. Факторный анализ. Кластер-анализ.

7. Классификация без обучения. Дискриминантный анализ. Классификация с обучением.

8. Множественный ковариационный анализ.

9. Метод наименьших квадратов.

10. Множественный корреляционно-регрессионный анализ.

1. Проблема распознавания объектов.

2. Обработка априорной информации.

3. Вероятностные системы распознавания.

4. Словарь признаков систем распознавания.

5. Логические системы распознавания.

6. Структурные методы распознавания.

7. Управление процессом распознавания.

8. Эффективность вероятностных и логических систем распознавания.

9. Распознавание в условиях противодействия.

1. Точечные преобразования изображения. Эквализация.

2. Преобразование Фурье. Обобщенные функции.

3. Линейные фильтры. Передаточная функция фильтра.

4. Теорема Котельникова-Шеннона.

5. Медианная фильтрация.

6. Фильтры Собеля и Канни для выделения границ образа.

7. Преобразование Хафа.

8. Особые точки изображения. Точки Харриса.

9. Способ обучения классификатора. Процедура Adaboost.

10. Трекинг объекта на изображениях.

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.

1. Понятие искусственного интеллекта. Формы представления знаний.

2. Логика и формальные системы. Логическое представление знаний.

3. Семантические сети. Классификация семантических сетей.

4. Основные задачи, решаемые с использованием семантических сетей.

5. Понятие сущности. Семантические отношения и их виды. Семантические модели «сущность - связь».

6. Фреймы - системно-структурное описание предметной области. Принципы фрейм-представлений, слоты.

7. Продукционные системы представления знаний.

Эволюционная методология.

Синергетика.

Генетические алгоритмы.

Нейросети.

Модально-логические подходы.

1. Основные понятия и виды поиска.

2. Информационно-поисковые языки.

3. Критерии выдачи.

4. Модели поиска. Стратегия поиска.

5. Функциональная эффективность поиска.

6. Поисковые массивы, способы их организации.

1. Онтология как вычислительная модель предметной области. Интеграции онтологического, когни­тивного и событийного моделирования.

2. Семантические инструменты. Языки обработки семантических сетей. Семантические модели ре­шателя интеллектуальных систем.

3. Онтологии и тезаурусы. Формальные онтологии. Построение тезаурусов средствами семанти­ческой технологии. Терминологические сети.

4. Исчисление позитивно-образованных формул и автоматическое доказательство теорем.

5. Семантика языков программирования. Онтологическая парадигма программирования.

6. Семантические технологии проектирования баз данных.

7. Семантические технологии проектирования баз знаний.

8. Семантические технологии в информационном поиске.

9. Логико-семантические модели прикладных интеллектуальных систем. Семантические технологии в проектировании. Семантические технологии в образовании.

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/Func- tional.pdf

12. Малышев Н.Г., Берштейн Л.С., Боженюк А.В. Нечеткие модели для экспертных систем в САПР. - М.: Энергоатомиздат, 1991.

13. Аверкин А.Н., Батыршин И.З., Блишун А.Ф. Нечеткие множества в моделях управления и искусственного интеллекта /Под ред. Д.А. Поспелова. - М: Наука, 1986.

14. Маннинг К., Рагхаван П., Шютце Х. Введение в информационный поиск. - М.: Вильямс, 2011.

15. Открытые семантические технологии проектирования интеллектуальных систем = OpenSemanticTechnologiesforIntelligentSystems (OSTIS-2012): материалы II Междунар. научн.-техн. конф. /редкол.: В.В. Голенков (отв. ред.) [и др.]. - Минск : БГУИР, 2012.

16. Открытые семантические технологии проектирования интеллектуальных систем = OpenSemanticTechnolo­giesforIntelligentSystems (OSTIS-2013): материалы III Междунар. научн.-техн. конф. /редкол.: В. В. Голен­ков (отв. ред.) [и др.]. - Минск : БГУИР, 2013.

17. Цаленко М.Ш. Моделирование семантики в базах данных. - М.: Наука. Главная редакция физико­математической литературы, 1989.

18. Барков И.А. Теория конструкторской семантики. - Ижевск: Изд-во ИжГТУ, 2003.

19. Васильев С.Н., Жерлов А.К., Федосов Е.А., Федунов Б.Е. Интеллектное управление динамическими сис­темами. - М.: Физматлит, 2000.

20. Попов Э.В. Экспертные системы: Решение неформализованных задач в диалоге с ЭВМ. - М.: Наука, 1987.

21. Джексон П. Введение в экспертные системы. - М.: Вильямс, 2001.

1. Детерминированные конечные автоматы. Диаграммы Мура (системы переходов).

2. Недетерминированные конечные автоматы.

3. Автоматные грамматики и конечные автоматы. Регулярные выражения.

4. Формальные грамматики, их основные классы.

5. КС-грамматики и деревья выводов в них.

6. Бинарные деревья.

7. Автоматы с магазинной памятью.

1. Области применения автоматного подхода.

2. Парадигма автоматного программирования.

3. Автоматные модели.

4. Процедурное программирование с явным выделением состояний.

5. Объектно-ориентированное программирование с явным выделением состояний.

1. Основные операции с регулярными выражениями.

2. Строки, кодировки и режимы. Стандартные метасимволы и возможности.

3. Типы механизмов обработки регулярных выражений.

4. Основы поиска совпадений. Максимализм, возврат. Хронометраж. Исключение случайных совпадений.

5. Стандартные оптимизации. Приемы построения быстрых выражений. Раскрутка цикла.

1. Структура сложных систем.

2. Объектная модель.

3. Классы и объекты.

4. Диаграммы.

5. Процессы проектирования.

Рекомендуемая литература

1. Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений. - М.: Вильямс, 2002.

2. Гладкий А. В. Формальные грамматики и языки. — М.: Наука, 1973.

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

4. Кобринский Н.Е., Трахтенброт Б.А. Введение в теорию конечных автоматов. - М.: Физматгиз, 1962.

5. Лавров С. С. Программирование. Математические основы, средства, теория. - СПб.: БХВ-Петербург, 2001.

6. Дейкстра Э. Взаимодействие последовательных процессов //Языки программирования. - М.: Мир, 1972.

7. Поликарпова Н. И., Шалыто А. А. Автоматное программирование. - СПб.: Питер, 2008.

8. Фридл Дж. Регулярные выражения, 3-е издание. - Пер. с англ. - СПб.: Символ-Плюс, 2008.

9. Ахо А., Сети Р., Ульман Д. Компиляторы. Принципы, технологии, инструменты. - М.: Вильямс, 2002.

10. Буч Г. Объектно-ориентированный анализ и проектирование с примерами на C++. Второе издание. - М.: Бином; СПб.: Невский диалект, 2000.

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.

VI. Телекоммуникационные системы

Тема 1. Элементы теории передачи дискретной информации

1. Энтропия и информация. Условная и предельная энтропии.

2. Источник и получатель сообщений. Классификация дискретных источников.

3. Кодирование источников дискретных сообщений.

4. Определение дискретного канала связи. Пропускная способность дискретного канала.

5. Теорема Шеннона о передаче сообщений по дискретному каналу без памяти. Понятие дискрет­ного канала с памятью.

6. Универсальное кодирование: определение, код Колмогорова-Фитингофа.

Тема 2. Самокорректирующиеся коды

1. Задача помехоустойчивого кодирования.

2. Определение блоков кодов, исправляющих и обнаруживаемых заданное число ошибок.

3. Код Хемминга. Задание блоковых кодов. Линейные коды.

4. Порождающая и проверочная матрицы кода. БЧХ коды.

5. Границы Гильберта и Варшамова-Гильберта.

6. Понятие о непрерывном не блоковом помехоустойчивом кодировании, сверточные коды.

7. Код Витерби.

Тема 3. Сети ЭВМ

1. Разновидности сетей. Основные программные и аппаратные компоненты сети.

2. Сравнительный анализ различных методов коммутации данных..

3. Основные функции протоколов передачи данных

4. Типы и особенности каналов передачи данных. Модемы.

5. Цифровая передача, ее особенности, форматы синхронного потока данных.

6. Технологии передачи данных в ЛВС. Программное обеспечение ЛВС.

Тема 4. Глобальные и территориально-распределенные сети

1. Технология сетей Х.25.

2. Технология функционирования сетей FrameRelay.

3. Основы технологии АТМ.

4. Стандарты сетей TCP/IP.

5. Маршрутизация в составной сети с помощью IP-адресов.

6. Понятие TCP-соединения.

7. Протоколы обмена информацией в сетиInternet.

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

Тема 5. Сетевые операционные системы

1. Сетевые понятия и протоколы

2. Потоки в .NET

3. Сетевое программирование в .NET

4. Работа с сокетами

5. Сокеты групповой рассылки

6. Криптография .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.

Настоящая программа разработана в соответствии с паспортом специальности ВАК 05.13.17 «Теоретические основы информатики». При этом учитывалась специфика научных направлений НИИ ПС АН РТ. Предполагается, что поступающий в аспирантуру экзаменуется только по темам, отвечающим научному направлению его руководителя.

В основу программы положены следующие дисциплины: теория множеств, логика, автоматы, алгоритмы; методы программирования; теория вероятностей и математическая статистика; теория информации и кодирования; базы данных; схемотехника ЭВМ; вычислительные машины, комплексы, системы и сети; сетевые операционные системы; системы искусственного интеллекта; архитектурно-­алгоритмические основы параллельных вычислений; параллельное программирование; защита сетевых и пространственных данных.

Программа рассмотрена и одобрена на заседании Ученого совета НИИ «Прикладная семиотика» АН РТ 30.01.2017, протокол №30.

Программу разработала комиссия в составе:

Председатель комиссии: д.т.н., профессор Сулейманов Д.Ш.

Члены комиссии: к.т.н., доцент Невзорова О.А.

к.ф.-м.н., доцент Гильмуллин Р.А.

к.т.н., доцент Гатиятуллин А.Р.