ПРОГРАММА ВСТУПИТЕЛЬНОГО ИСПЫТАНИЯ
для поступающих на основную образовательную программу подготовки научно-педагогических кадров в аспирантуре «Информатика»
по направлению подготовки 09.06.01 «Информатика и вычислительная техника»
по предмету «Информатика»
РАЗДЕЛ I. СОДЕРЖАНИЕ ОСНОВНЫХ ТЕМ
1. Математические основы программирования
Понятие алгоритма и его уточнения: машины Тьюринга, нормальные алгоритмы Маркова, рекурсивные функции. Понятие сложности алгоритмов. Полиномиальная сводимость и полиномиальная эквивалентность задач. Классы P и NP. Примеры эффективных (полиномиальных) алгоритмов: быстрые алгоритмы поиска и сортировки; полиномиальные алгоритмы для задач на графах и сетях (поиск в глубину и ширину, о минимальном остове, о кратчайшем пути, о назначениях). Исчисление предикатов первого порядка. Понятие интерпретации. Выполнимость и общезначимость формулы первого порядка. Понятие модели. Формальная арифметика. Теорема Геделя о неполноте арифметики. Отношения и функции. Отношение эквивалентности и разбиения. Фактор множества. Отношения частичного порядка. Формальные языки и способы их описания. Классификация формальных грамматик. Их использование в лексическом и синтаксическом анализе. Основы комбинаторного анализа. Метод производящих функций, метод включений и исключений. Примеры применения. Коды с исправлением ошибок. Алфавитное кодирование. Методы сжатия информации.2. Вычислительные машины, системы и сети
3. Языки и системы программирования. Технология разработки программного обеспечения
Языки программирования. Процедурные языки программирования (Фортран, Си), Функциональные языки программирования (Лисп), логическое программирование (Пролог), объектно-ориентированные языки программирования (Ява). Процедурные языки программирования. Основные управляющие конструкции, структура программы. Работа с данными: переменные и константы, основные типы данных, структуры данных (массивы и записи). Процедуры (функции): вызов процедур, передача параметров (по ссылке, по значению, по результату). Объектно-ориентированное программирование. Классы и объекты, наследование, интерфейсы. Понятие об объектном окружении. Рефлексия. Библиотеки классов. Средства обработки объектов (контейнеры и итераторы). Распределенное программирование. Процессы и их синхронизация. Семафоры, мониторы Хоара. Объектно-ориентированное распределенное программирование. CORBA. Параллельное программирование над общей памятью. Нити. Стандартный интерфейс Open MP. Основы построения трансляторов. Структура оптимизирующего транслятора. Промежуточные представления программы: последовательность символов, последовательность лексем, синтаксическое дерево, абстрактное синтаксическое дерево. Анализ исходной программы в компиляторе. Автоматные (регулярные) грамматики и сканирование, контекстно свободные грамматики и синтаксический анализ, организация таблицы символов программы, имеющей блочную структуру, хеш-функции. Оптимизация программ при их компиляции. Оптимизация базовых блоков, чистка циклов. Анализ графов потока управления и потока данных. Генерация объектного кода в компиляторах. Перенастраиваемые (retargetable) компиляторы, gcc (набор компиляторов Gnu). Переработка термов (term rewriting). Машинно-ориентированные языки, язык ассемблера. Представление машинных команд и констант. Команды транслятору. Их типы, принципы реализации. Системы программирования (СП), типовые компоненты СП: языки, трансляторы, редакторы связей, отладчики, текстовые редакторы. Отладка, тестирование, верификация и оценивание сложности программ. Генерация тестов. Системы генерации тестов. Методы спецификации программ. Методы проверки спецификации. Схемное, структурное, визуальное программирование. Разработка пользовательского интерфейса, стандарт CUA.4. Операционные системы
5. Методы хранения данных и доступа к ним. Организация баз данных и знаний
Концепция типа данных. Абстрактные типы данных. Объекты (основные свойства и отличительные признаки). Основные структуры данных, алгоритмы обработки и поиска. Сравнительная характеристика методов хранения и поиска данных. Основные понятия реляционной и объектной моделей данных. Теоретические основы реляционной модели данных (РДМ). Реляционная алгебра, реляционное исчисление. Функциональные зависимости и нормализация отношений. CASE-средства и их использование при проектировании базы данных (БД). Организация и проектирование физического уровня БД. Методы индексирования. Обобщенная архитектура, состав и функции системы управления базой данных (СУБД). Характеристика современных технологий БД. Примеры соответствующих СУБД. Основные принципы управления транзакциями, журнализацией и восстановлением. Язык баз данных SQL. Средства определения и изменения схемы БД, определения ограничений целостности. Контроль доступа. Средства манипулирования данными. Основные понятия технологии клиент—сервер. Характеристика SQL-сервера и клиента. Сетевое взаимодействие клиента и сервера.I. Теория вероятностей
II. Дискретные цепи Маркова
Однородные марковские цепи с дискретным пространством состояний. Начальное распределение и матрица перехода. Матрица перехода за несколько шагов. Классификация марковских цепей. Возвратность. Стационарные распределения и финальные вероятности. Теорема о предельном поведении переходных вероятностей в марковской цепи. Марковские цепи с произвольным пространством состояний. Конечномерные распределения. Поглощающие состояния.III. Случайные процессы.
Марковские процессы. Начальное распределение и переходная функция. Конечномерные распределения. Стационарные в широком смысле процессы. Ковариационная функция и спектральная мера. Процесс авторегрессии и скользящего суммирования. Гауссовские процессы. Простейшие свойства. Примеры.IV. Математическая статистика
Оценивание. Точечные оценки, их свойства. Оценки максимального правдоподобия. Доверительные интервалы. Меры зависимости. Коэффициент корреляции Пирсона, Спирмена. Корреляционное отношение. Принципы построения критериев для проверки гипотез. Уровень значимости. Мощность критерия. Примеры критериев.V. Метод Монте-Карло
Моделирование случайных величин. Основные методы получения псевдослучайных чисел. Методы моделирования случайных величин с заданным распределением. Трудоемкость моделирования. Моделирование марковских процессов. Моделирование гауссовских процессов. Моделирование стационарных в широком смысле процессов. Вычисление интегралов методом Монте-Карло. Методы уменьшения трудоемкости. Оценки по поглощению и столкновению для решения интегральных уравнений. Решение задач переноса излучения. Решение простейших задач математической физики. Принципы и методы имитационного моделирования.VI. Стохастические модели систем.
Принцип узловых точек. Дt-принцип. Случайный поиск с адаптацией. Процесс противоборства и принцип неопределенности.VII. Теория автоматов
Понятие о вероятностном конечном автомате. Автоматы частного вида. Детерминированные автоматы. Способ задания вероятностных автоматов. Методы задания детерминированных автоматов (графы, автоматная матрица, таблицы переходов и выходов, системы канонических уравнений).VIII. ЭВМ и программирование
Операционные системы. Управление памятью. Управление процессами. Управление процессором. Управление устройствами. Управление файлами. Основные этапы решения задач на ЭВМ. Алгоритмические языки высокого уровня. Объектно-ориентированное программирование (С++, Visual C++).Моделирование физических процессов и численная реализация
1. Простейшая краевая задача для обыкновенного линейного дифференциального оператора.
2. Собственный спектр положительно определенных операторов /понятие о спектре, собственные числа и элементы/.
3. Разложение по собственному спектру положительно определенного оператора.
4. Задача Штурма - Лиувилля.
5. Дифференциальные уравнения 2-го порядка, краевые условия и краевые задачи. Задача Коши, проблема существования и единственности решения.
6. Задачи Дирихле и Неймана.
7. Вариационный метод.
8 Уравнение теплопроводности, волновое уравнение.
9. Метод итерации. Теорема о сжатых отображениях.
10. Решение систем алгебраических уравнений методами итераций
11. Решение системы алгебраических уравнений методами исключений.
12. Оценки погрешности приближенного решения системы.
13. Итерационный метод нахождения собственных значений и собственных векторов матриц.
14. Интерполирование. Погрешность, конечные разности.
15. Формулы Лагранжа и Ньютона.
Вычислительные методы
16. Машинные представления действительного числа. Влияние формы представления на вычислительный процесс.
17. Задачи линейной алгебры. Понятие о псевдорешении.
18. Гладкая аппроксимация и интерполяция. Сплайны Шонберга. Минимальные сплайны.
19. Производная нелинейной операции. Метод Ньютона.
20. Вторая производная нелинейной операции. Скорость сходимости метода Ньютона.
21. Вычисление многократных интегралов. Кубатурные формулы. Метод Монте-Карло.
22. Метод последовательных приближений для интегральных уравнений.
23. Метод механических квадратур. Метод моментов.
24. Некорректные задачи. Постановки Адамара и Тихонова, Понятие о регуляризаторе.
25. Некорректная задача для интегрального уравнения первого рода.
26. Вариационный метод. Абстрактная схема.
27. Метод Ритца для задачи Дирихле.
28. Вариационно-сеточные методы. Оценка сходимости.
29. Сеточные методы. Постановка задачи. Аппроксимация, сеточный шаблон.
30. Устойчивость и сходимость. Теорема о порядке сходимости на решении.
31. Нестационарная задача. Оценка сходимости.
32. Задача Коши. Периодические решения. Условие Неймана.
33. Задача линейного программирования. Понятие вершины. Базисные переменные.
34. Симплекс-метод для задач линейного программирования.
Теория сплайнов и вейвлетов
35. Интерполяция и аппроксимация функций. Интерполяция Лагранжа, Эрмита, Эрмита-Биркгофа. Интерполяционные полиномы. Нахождение неточно заданной входной информации и исправление. Влияние округления при вычислениях на ЭВМ. Приближение различными типами сплайнов.
36. Эрмитовы кубические сплайны. В-сплайны. Минимальные сплайны. Минимальные лагранжевы сплайны. Аппроксимационные тождества.
37. Обработка информации с помощью сплайнов. Применение минимальных сплайнов для сжатия и восстановления числовых потоков. В том числе - сложной графической информации.
38. Применение к решению задач математической физики и распараллеливание. Решение краевых задач вариационно-разностным методом. Устойчивость вычислений. Приближения в комплексной области. Всплески и цифровые фильтры.
39. О понятии «всплеск». Цифровые фильтры. Быстрое дискретное преобразование Фурье.
40. Обработка сигналов и изображений. Естественная параллельная структура всплесковых преобразований.
41. Кратно-масштабное уравнение и масштабирующая функция. Примеры масштабирующих функций. Прямое разложение и пространство всплесков. Ортогональное разложение.
42. Переход от одного базиса к другому. Формулы декомпозиции и реконструкции.
43. Ортовсплески в ортогональном разложении цепочки вложенных пространств. Кратно-масштабный анализ.
44. Образующие минимальные сплайны. Пространства минимальных сплайнов. Приведенный образующий минимальный сплайн и его характеристический многочлен.
45. Псевдосвертка и калибровочное соотношение. Цепочки приведенных сплайнов. Распараллеливание всплесковой фильтрации сигнала.
46. Формулы декомпозиции и реконструкции и их распараллеливание. Распараллеливание всплесковой фильтрации сигнала с гарантированным порядком аппроксимации.
О построении вейвлетного разложения на неравномерной сетке.Случайные процессы. Математическая статистика.
Метод Монте-Карло.
48. Марковские процессы. Начальное распределение и переходная функция. Конечномерные распределения.
49. Стационарные в широком смысле процессы. Ковариационная функция и спектральная мера. Процесс авторегрессии и скользящего суммирования.
50. Гауссовские процессы. Простейшие свойства. Примеры.
51. Оценивание. Точечные оценки, их свойства. Оценки максимального правдоподобия. Доверительные интервалы.
52. Меры зависимости. Коэффициент корреляции Пирсона, Спирмена. Корреляционное отношение.
53. Принципы построения критериев для проверки гипотез. Уровень значимости. Мощность критерия. Примеры критериев.
54. Моделирование случайных величин. Основные методы получения псевдослучайных чисел. Методы моделирования случайных величин с заданным распределением. Трудоемкость моделирования.
55. Моделирование марковских процессов. Моделирование гауссовских процессов. Моделирование стационарных в широком смысле процессов.
56. Вычисление интегралов методом Монте-Карло. Методы уменьшения трудоемкости. Оценки по поглощению и столкновению для решения интегральных уравнений. Решение задач переноса излучения. Решение простейших задач математической физики.
Теория автоматов. Операционные системы. Распараллеливание
57. Понятие о вероятностном конечном автомате. Автоматы частного вида. Детерминированные автоматы.
58. Способ задания вероятностных автоматов. Методы задания детерминированных автоматов (графы, автоматная матрица, таблицы переходов и выходов, системы канонических уравнений).
59. Операционные системы. Управление памятью. Процессы и распараллеливание в Unix.
60. Файловая структура в Unix. Управление файлами.
61. Алгоритмические языки высокого уровня. Объектно-ориентированное программирование (С++, Visual C++, Fortran).
62. Программные средства для распараллеливания (MPI, Open MP, DVM).
63. Концепция неограниченного параллелизма; область ее применимости.
64. Распараллеливание методов решения систем линейных алгебраических уравнений.
РАЗДЕЛ II. ИСТОЧНИКИ И ЛИТЕРАТУРА
Математические основы программирования; Вычислительные машины, системы и сети; Языки и системы программирования. Технология разработки программного обеспечения; Операционные системы; Методы хранения данных и доступа к ним. Организация баз данных и знаний
Основная литература
Ахо, Ульман Дж. Компиляторы: принципы, техника реализации и инструменты. М., 2001. , , Интеллектуальное программирование. Турбо Пролог и Рефал-5 на персональных компьютерах. – СПб.: Издательство СПбГУ, 1992. Введение в криптографию / Под ред. . СПб.: МЦНМО, 2001. ж. Введение в системы баз данных. М.: Вильямс, 1999. ведение в операционные системы. М.: Мир, 1987. скусство программирования. Т. 1 – 3. М., СПб., Киев: ИД «Вильямс», 2000. Энциклопедия технологий баз данных. М.: Финансы и статистика, 2002. Компьютерные сети. Учебный курс Microsoft Corporation, 1997. лгоритмы, построение и анализ. М.: МЦНМО, 2000. Элементы математической логики и её приложения к теории субрекурсивных алгоритмов. Изд. Ленинградского университета, 1981. 192 с. Основы теории элементарных алгоритмов. — Л.: Изд. ЛГУ, 1987. , Теория схем программ. М.: Наука, 1991. еханизмы защиты в сетях ЭВМ. М.: Мир, 1993. Защита информации в компьютерных системах. М.: Финансы и статистика, 1997. Введение в дискретную математику. М.: Наука, 2001.Дополнительная литература
ети передачи данных. М., «Мир», 1989. ети ЭВМ: протоколы, стандарты, интерфейсы. М., «Мир», 1990 овые стандарты высокоскоростных сетей. // Открытые системы, 3(7), 1994. UNIX – универсальная среда программирования. М.: Финансы и статистика, 1992. Параллельные вычислительные системы. М.: Нолидж, 1999. Структуры ЭВМ и их математическое обеспечение. М.: Наука, 1980. нутреннее устройство Microsoft Windows 2000. СПб.: Питер, 2001. Ульман Дж. Основы систем баз данных. М., Финансы и статистика, 1983. Фокс Дж. Проектирование и создание программных комплексов. М., "Мир", 1984.Теория вероятностей; Дискретные цепи Маркова; Случайные процессы; Математическая статистика; Метод Монте-Карло; Стохастические модели систем; Теория автоматов; ЭВМ и программирование
Вероятность. М., МЦНМО, 2007. Теория вероятностей. М., Либроком, 2009 Курс теории случайных процессов. М.: Наука 1996 Теория вероятностей, математическая статистика и случайные процессы, Наука, 1989. Численные методы Монте-Карло. М., Наука, 1973. , Курс статистического моделирования. М., Наука, 1982. митационное моделирование систем - искусство и наука. М., Мир, 1978. , Математическая статистика. М.: ЛКИ, 2010. Статистические модели систем. СПб: Изд-во СПбГУ, 2004. , Стационарные детерминированные и вероятностные автоматы (Теория автоматных моделей). СПб: Издательство СПбГУ, 2008. Объектно-ориентированное программирование на C++. Невский диалект, 2001. нформатика (ч.1,2,3) М.: Диалог-МИФИ, 1996. Visual C++ и MFC. СПб.: БХВ, 2000. Метод Монте-Карло в вычислительной математике. Вводный курс. - СПб.: Невский Диалект, М.: Бином. Лаборатория знаний, 2009. - 192 с. Метод Монте-Карло в вычислительной математике. Вводный курс. СПб.: Невский Диалект, М.: Бином. Лаборатория знаний, 2009, 192 с.Моделирование физических процессов и численная реализация; Вычислительные методы; Теория сплайнов и вейвлетов; Случайные процессы. Математическая статистика. Метод Монте-Карло; Теория автоматов. Операционные системы. Распараллеливание
1. , . Функциональный анализ. Наука.1977 (главы 1,2,4-7,9,11,12-14,17,18).
2. . Лекции по функциональному анализу. М.: МЦНМО, 2004. 552 с.
3. . Линейные уравнения в частных производных. Высшая школа. 1977 (главы 1-5,8-12,14,15,17,18,20-24).
4. . Лекции по методам вычислений. СПб. 1998.
5. . Введение в классическую теорию приближенияфункций. СПб. 2011. 232 с.
6. , , . Эффективные по времени и памяти алгоритмические приближения чисел и функций. СПб. 2012. 256 с.
7. . Вариационные методы в математической физике. 1970. 512 с.
8. , . Теория минимальных сплайнов. СПб.: -Петербургского университета, 2000. 317 с.
9. Yukiya Aoyama, Jun Nakano. RS/6000 SP: Practical MPI Programming. IBM. Technical Sup-port Organization. 2000. 221 p. www. redbook. , 2003.
10. И. Добеши. Десять лекций по вейвлетам. Ижевск: НИЦ "Регулярная и хаотическая динами-ка". 2001. 464 с.
11. . Минимальные сплайны \& всплески. СПб. 2003. 200 с.
12. , . Курс статистического моделирования. М., Наука, 1982.
13. . Основы общей теории конечных автоматов. Изд-во ЛГУ, 1975.
14. , Вл. В.Воеводин. Параллельные вычисления. СПб. 2002.
15. Ю. К.,Демьянович, и др. Параллельные алгоритмы. Разработка и реализация. М., 2012. 344 с.
Базы данных, информационно-справочные и поисковые системы
Библиотеки
Российская государственная библиотека www. rsl. ru
Российская национальная библиотека www. nlr. ru
Библиотека Академии наук www. rasl. ru
Библиотека по естественным наукам РАН www. benran. ru
Научная библиотека СПбГУ www. bio. spbuu. ru/library
Научная электронная библиотека eLIBRARY. RU www. elibrary. ru
РАЗДЕЛ III. ОРГАНИЗАЦИОННО-МЕТОДИЧЕСКИЙ РАЗДЕЛ
Форма проведения вступительного испытания: устно-письменная
Продолжительность вступительного испытания:
На письменную часть экзамена (2 вопроса) отводится 1 час 30 мин.
На подготовку к устной части (1 вопрос) – 30 мин.
При проверке письменных ответов члены комиссии имеют право задавать поступающему уточняющие вопросы по ответу.
РАЗДЕЛ IV. КРИТЕРИИ ОЦЕНИВАНИЯ ВСТУПИТЕЛЬНОГО ИСПЫТАНИЯ
Письменный ответ на каждый вопрос оценивается от 0 до 15 баллов, устный – от 0 до 20 баллов. Минимальный проходной балл за экзамен – 20 баллов.
Критерии оценивания письменных ответов
Дан полный ответ, отсутствуют ошибки и неточности – 15 баллов.
Ответ изложен в целом правильно, имеются незначительные неточности или несущественные ошибки – 11-14 баллов.
Ответ изложен недостаточно полно, имеются ошибки, не носящие принципиального характера – 6-10 баллов.
Ответ не раскрывает существа вопроса или допущены грубые ошибки – 0-5 баллов.
Критерии оценивания устного ответа
Дан полный ответ, продемонстрировано знание предмета и навыки устного изложения – 20 баллов.
Ответ в целом правильный, имеются незначительные погрешности, исправленные в ходе дискуссии – 15-19 баллов.
Ответ в целом правильный, но неполный или изложение недостаточно профессиональное или имеются погрешности, не носящие принципиального характера – 10-14 баллов.
Ответ схематичен, но отражает существо вопроса и не содержит грубых ошибок – 6-9 баллов.
Ответ не раскрывает существа вопроса или допущены грубые ошибки – 0-5 баллов.
ПЕРЕВОД В ПЯТИБАЛЛЬНУЮ ШКАЛУ ОЦЕНИВАНИЯ
41 – 50 баллов – «отлично»
31 – 40 баллов – «хорошо»
20 – 30 баллов – «удовлетворительно»
0 – 19 баллов – «неудовлетворительно»
