Программа государственного экзамена по информатике
на математическом факультете МПГУ по специальности 050201.65 Математика
с дополнительной специальностью Информатика в 2014 г.
Дискретная математика. Математическая логика. Теория алгоритмов. Численные методы. Исследование операций. Теоретические основы информатики. Основы искусственного интеллекта.
Основные комбинаторные конфигурации: выборки, размещения, перестановки, перестановки с повторениями, сочетания, сочетания с повторениями. Явные формулы для их числа. Простейшие задачи на разложение шаров по ящикам. Принцип включения и исключения. Число разложений n различимых шаров по k различимым ящикам при условии того, что ящики не могут быть пустыми. Число представлений n–множества в виде объединения k непустых непересекающихся подмножеств. Понятие рекуррентного соотношения. Биномиальные коэффициенты, их комбинаторная интерпретация. Основные тождества с биномиальными коэффициентами. Треугольник Паскаля. Производящие функции. Применение производящих функций для решения рекуррентных соотношений. Явная формула для чисел Фибоначчи. Основные понятия теории графов. Способы задания графов. Изоморфизм графов. Понятие инварианта графа. Примеры инвариантов графа. Связные графы. Компоненты связности графа. Число компонент связности графа, имеющего p вершин и q ребер. Необходимое условие связности графа. Деревья. Основные свойства деревьев. Остов графа. Задача о минимальном остове. Плоские графы. Формула Эйлера. Раскраска плоских графов. Эйлеровы графы. Критерий эйлеровости. Гамильтоновы графы. Необходимое условие гамильтоновости графа.
Логика высказываний (ЛВ). Высказывания и операции над ними. Формулы языка ЛВ. Тавтологии. Равносильные формулы ЛВ. Основные законы равносильности ЛВ. Исчисления высказываний. Системы естественного вывода. Правила вывода как формализация правил и методов неформального доказательства. Понятие выводы в виде дерева как естественная модель понятия доказательства в математике. Характеристики исчислений: непротиворечивость, семантическая корректность и полнота, разрешимость. Логика предикатов (ЛП). Формулы языка ЛП. Выполнимые и общезначимые формулы языка ЛП. Равносильные формулы ЛП. Основные законы равносильности ЛП. Теории первого порядка. Примеры: теория групп, формальная арифметика. Модель теории. Непротиворечивые теории. Разрешимые теории. Критерий независимости аксиомы.
Понятие алгоритма в математике. Основные свойства алгоритмов. Вычислимые функции. Необходимость уточнения интуитивных понятий алгоритма и вычислимой функции. Математические уточнения интуитивных понятий алгоритма и вычислимой функции. Частично рекурсивные функции. Тезис Чёрча. Машины Тьюринга. Вычислимые по Тьюрингу функции. Тезис Тьюринга-Чёрча. Совпадение классов частично рекурсивных функций и функций, вычислимых по Тьюрингу. Разрешимые и перечислимые множества. Рекурсивные и рекурсивно перечислимые множества. Критерии рекурсивно перечислимости множества. Важные примеры множеств и функций. Алгоритмически неразрешимые проблемы. Проблема самоприменимости и проблема остановки для машин Тьюринга. Алгоритмическая сводимость. Теорема Успенского-Райса. Проблема диофантовых уравнений.
Решение системы линейных уравнений. Итерационные методы: метод простой итерации, метод Зейделя. Точные методы, число операций в методе Гаусса. Численное решение нелинейного уравнения. Метод половинного деления, метод хорд, метод касательных, метод секущих, метод итераций. Численное решение систем нелинейных уравнений (понятие о методе Ньютона). Методы наилучшего приближения. Дискретный вариант среднеквадратических приближений, нахождение многочлена наилучшего приближения. Численная интерполяция. Интерполяционный многочлен в форме Лагранжа. Интерполяционный многочлен в форме Ньютона. Численное дифференцирование. Нахождение производной в точке, не принадлежащей отрезку интерполирования. Нахождение производной в узле таблицы. Численное интегрирование. Квадратурные формулы прямоугольников. Квадратурная формула трапеций. Квадратурная формула Симпсона. Квадратурная формула Гаусса.
Методы принятия решений в условиях полной информации. Задачи на безусловный и условный экстремум. Необходимые и достаточные условия экстремума. Задача математического программирования. Выпуклое программирование. Теорема Куна-Таккера. Линейное программирование. Симплекс метод. Двойственность в линейном программировании. Методы принятия решений в условиях риска (случайных неконтролируемых факторов). Математическое ожидание и дисперсия как оценки эффективности и риска. Задача Марковица формирования инвестиционного портфеля. Методы принятия решений в условиях неопределенности и многокритериальности. Критерии Вальда, Гурвица, Сэвиджа, Лапласа. Паретооптимальность, методы свертки критериев и идеальной точки. Игры в нормальной форме. Определение. Принципы оптимальности (гарантированный результат, равновесие по Нэшу, разрешимость по доминированию). Биматричные игры, нахождение равновесия в чистых и смешанных стратегиях. Матричная игра. Решение в чистых и смешанных стратегиях. Связь с линейным программированием.
Понятие кодирования. Криптографические алгоритмы. Коды с исправлением ошибок. Алфавитное кодирование. Кодирование с минимальной избыточностью. Методы сжатия. Теория автоматов. Понятие конечного автомата. Ограниченно-детерминированные функции.
Понятие об искусственном интеллекте, основные подходы и методы. Предпосылки искусственного интеллекта (философия, математика, экономика, неврология, психология, вычислительная техника, кибернетика). История искусственного интеллекта. Основы теории обучения по прецедентам, оценка качества и обобщающей способности алгоритмов и методов, методы ее оценки, методы отбора по внешним и внутренним критериям качества. Эвристические принципы обучения, методы построения алгоритмов на основе принципа сходства. Построение алгоритмов на основе принципа регуляризации. Композиции алгоритмов и понятие об алгебраическом подходе к построению распознающих алгоритмов. Построение алгоритмов на основе принципа селекции и самоорганизации. Понятие о нейронных сетях. Модели нейронов и нейронных сетей. Теоретические основы обучаемости на базе нейронных сетей. Методы обучения нейронных сетей.
Список рекомендуемой литературы
1. , Лекции по дискретной математике, М.: МПГУ, 1997.
2. Деза дискретной математики. М.: URSS, 2010.
3. Конспект лекций по курсу «Введение в математическую логику», М.: МГУ, 2007. (http:/math. msu. su/department/dm/dmmc/index. htm)
4. Теория алгоритмов, М.: Прометей, МГПИ, 1989.
5. , , Макаренков алгоритмов. Сборник задач. – М.: Прометей, МПГУ, 2010.
6. Введение в математическую логику. –– 4-е изд. – М.: Либроком, 2010.
7. Тимофеева логика. Курс лекций. – 2-е изд., перераб. – М.: КДУ, 2007.
8. , "Численные методы" URSS 2010
9. Горелик операций и методы оптимизации. М.: Изд. центр «Академия», 2013.
10. Матросов основы информатики. М.: Академия, 2009.
11. Теоретическая информатика. Введение в теорию автоматов, теорию вычислимости, теорию алгоритмов, рандомизацию, теорию связи и криптографию. СПб: БХВ-Петербург, 2010.
12. Новиков математика для программистов. СПб: Питер, 2002.
13. Искусственный интеллект. Современный подход. – М.: Издательский дом «Вильямс». 2006 г. – 1408 с.
14. Машинное обучение (электронный ресурс). http://www. *****/wiki/index. php? title=Машинное_обучение_ (курс_лекций,_)
Программирование. Программное обеспечение. Архитектура компьютера. Компьютерные сети, интернет и мультимедиа технологии. Информационные системы.
Процедурное программирование. Структурное программирование. Объектно-ориентированная парадигма программирования. Абстракция данных. Наследование. Инкапсуляция. Полиморфизм. Объектно-ориентированное проектирование. Объектно-ориентированный анализ. Основные этапы создания объектно-ориентированной программы. Базовые структуры данных (стеки, списки, очереди, деревья). Алгоритмы сортировки и поиска.
Программное обеспечение ЭВМ, его основные характеристики. Классификация программного обеспечения. Операционные системы, назначение и функции. Архитектура ОС. Обзор операционных систем семейств Windows, Unix, Mac OS. Вирусы и другие вредоносные программы, классификация. Средства защиты компьютера, типы антивирусного программного обеспечения. Правила безопасной работы. Прикладное программное обеспечение общего назначения. Системы обработки текстов. Системы машинной графики. Табличные процессоры. Системы компьютерной математики. Интегрированные среды разработки программного обеспечения, основные функции и компоненты.
Информационно-логические основы построения ЭВМ. Представление данных в компьютере. Центральные и внешние устройства ЭВМ, их характеристики. Канальная и шинная системотехника. Микропроцессор и память компьютера. Система прерываний, регистры и модель доступа к памяти. Защищенный режим работы процессора как средство реализации многозадачности. Принципы управления внешними устройствами персонального компьютера. Базовая система ввода/вывода. Принципы разработки современных компьютеров: параллелизм на уровне команд и параллелизм на уровне процессоров.
Принципы построения локальных и глобальных вычислительных сетей. Стандартизация в области вычислительных сетей. Эталонная семиуровневая модель ISO OSI, требования, предъявляемые к современным вычислительным сетям. Стек протоколов TCP/IP. Принципы цифровой фотографии. Цифровые форматы представления реалистических изображений. Средства создания интернет-ресурсов.
Основные понятия теории ИС. Компоненты информационной системы. Модели данных (реляционная, иерархическая, сетевая). Проектирование ИС. Жизненный цикл ИС. Этапы процесса проектирования ИС. CASE-технологии и CASE-средства как инструмент разработки и проектирования информационных систем. Различные методологии проектирования информационных систем. Модели SADT, DFD, ERD. . СУБД: назначение, функции, основные характеристики. Технология создания баз данных. Язык структурированных запросов SQL как инструмент реализации информационных систем. Перспективы развития СУБД.
Список рекомендуемой литературы
1. Информатика / , , М.: Академия, 2012.
2. , Маняхина и прикладное программное обеспечение. М.: Прометей, 2011.
3. Язык программирования Java и среда NetBeans. СПб: БХВ, 2011.
4. Финогенов языка Ассемблера. М.: Радио и связь, 2001.
5. Д. Паттерсон, Дж. Хеннесси Архитектура компьютера и проектирование компьютерных систем. Питер, 2012.
6. Архитектура компьютера, Питер, 2003.
7. , Олифер сети. Принципы, технологии, протоколы. Учебник для вузов. 3-е изд. – СПб.: Питер, 2006.
8. 100% самоучитель. Локальная сеть своими руками М.: Технолоджи – 3000: Изд-во Триумф, 20с.
9. Популярная энциклопедия мультимедиа. М.: ABF, 1997.
10. Звуковая студия в PC. Киев: BHV, 1998.
11. Введение в системы баз данных. М.: Наука, 2008.
12. Пирогов системы и базы данных: организация и проектирование. СПб: БХВ, 2009.
