ПРОГРАММА
Государственного экзамена по информатике на математическом факультете МПГУ по специальности «Информатика» с дополнительной специальностью «Математика» в 2012/13 уч. г.
Дискретная математика
Основные комбинаторные конфигурации: выборки, размещения, перестановки, перестановки с повторениями, сочетания, сочетания с повторениями. Явные формулы для их числа. Простейшие задачи на разложение шаров по ящикам.
Принцип включения и исключения. Число разложений n различимых шаров по k различимым ящикам при условии того, что ящики не могут быть пустыми. Число представлений n–множества в виде объединения k непустых непересекающихся подмножеств.
Понятие рекуррентного соотношения. Биномиальные коэффициенты, их комбинаторная интерпретация. Основные тождества с биномиальными коэффициентами. Треугольник Паскаля.
Производящие функции. Применение производящих функций для решения рекуррентных соотношений. Явная формула для чисел Фибоначчи.
Числа Каталана. Явная формула для чисел Каталана. Примеры перечислительных задач, решением которых являются числа Каталана.
Основные понятия теории графов. Способы задания графов. Изоморфизм графов. Понятие инварианта графа. Примеры инвариантов графа.
Связные графы. Компоненты связности графа. Число компонент связности графа, имеющего p вершин и q ребер. Необходимое условие связности графа.
Деревья. Основные свойства деревьев. Остов графа. Задача о минимальном остове.
ЛИТЕРАТУРА
Основная
1. , , Тышкевич по теории графов. М.: Наука, 1990
2. , Сапоженко и упражнения по дискретной математике. М.: Физматлит, 2005.
Дополнительная
3. Рыбников в комбинаторный анализ. М.: МГУ, 1985.
4. Конкретная математика. Основы информатики. М.: Мир, 1998.
5. , , Ядренко комбинаторики. М. Наука, 1977.
6. Сачков в комбинаторные методы дискретной математики. М.: Наука, 1982
Математическая логика
Алгебра высказываний. Таблицы истинности для основных логических операций. Выполнимые и общезначимые формулы алгебры высказываний. Основные равносильности алгебры высказываний. Совершенная дизъюнктивная нормальная форма.
Исчисление высказываний. Доказуемые и выводимые формулы в исчислении высказываний. Непротиворечивость и полнота исчисления высказываний. Теорема дедукции. Семантика исчисления высказываний. Непротиворечивость и полнота исчисления высказываний.
Алгебра предикатов. Выполнимые и общезначимые формулы алгебры предикатов. Основные равносильности алгебры предикатов.
Исчисление предикатов. Доказуемые и выводимые формулы в исчислении предикатов. Семантика исчисления предикатов. Непротиворечивость исчисления предикатов.
ЛИТЕРАТУРА
1. Введение в математическую логику. –М.: Наука, 1984.
2.Тимофеева лекций по математической логике. ч. I, II. – М.: Прометей, 2003.
Теория алгоритмов
Понятие алгоритма. Основные свойства алгоритма. Вычислимые функции. Основные вычислительные модели. Тезис Черча.
Пример невычислимой функции. Алгоритмические проблемы. Проблема останова, ее алгоритмическая неразрешимость. Понятие алгоритмической сводимости. Теорема Успенского-Райса. Примеры алгоритмически неразрешимых проблем в информатике.
Понятие сложности алгоритма. Сложность основных алгоритмов сортировки. Оценка сложности рекурсивного алгоритма. Дихотомический алгоритм возведения в степень.
Полиномиальные алгоритмы, их важность для информатики. Понятие класса сложности. Классы P и NP. Проблема перебора.
Полиномиальная сводимость. NP-полные проблемы. Задача о выполнимости коньюнктивной нормальной формы. Примеры NP-полных проблем. Важность теории NP-полноты для практического программирования.
ЛИТЕРАТУРА
1. Матросов алгоритмов –М.: Прометей, 1989.
2. , , Тимофеева по теории алгоритмов. –М.: Прометей, 2005.
Численные методы
Решение системы линейных уравнений: точные методы, итерационные методы.
Решение нелинейного уравнения. Методы наилучшего приближения. Численная интерполяция.
Численное дифференцирование. Численное интегрирование.
ЛИТЕРАТУРА
Основная
1. , , Кобельков методы: Учебное пособие для вузов. СПб.: Физматлит, 2000.
2. , , Чижонков методы в задачах и упражнениях: Учебное пособие. М.: Высшая школа, 2000.
3. Демидович вычислительной математики. М.: Наука, 1970.
Дополнительная
1. , , Лапчик методы. М.: Просвещение, 1991.
2. , , Шувалова методы анализа. М.: Наука, 1967.
3. , Жидков вычислений. В 2 ч. М.: Физматгиз, 1962.
4. , , Стукалов методы. М.: Академия, 2001.
5. , "Численные методы" URSS 2010
Теоретические основы информатики
Понятие кодирования. Коды с исправлением ошибок. Алфавитное кодирование. Разделимая схема кодирования. Префиксная схема кодирования. Кодирование с минимальной избыточностью.
Теория автоматов. Понятие конечного автомата. Ограниченно-детерминированные функции.
Методы принятия решений в условиях полной информации. Методы принятия решений в условиях риска. Методы принятия решений в условиях неопределенности и многокритериальности. Игры в нормальной форме. Определение. Принципы оптимальности (гарантированный результат, равновесие по Нэшу, паретооптимальность, доминирующие и доминируемые стратегии). Матричная игра. Решение в чистых и смешанных стратегиях.
ЛИТЕРАТУРА
Основная
1. , , Угольникова основы информатики. М.: Изд. центр «Академия», 2009.
2. , Угольникова в теорию автоматов. М.: МПГУ, 2000.
3. Яблонский в дискретную математику. М.: Высшая школа, 2003.
Дополнительная
4. , Скрипкин распознавания. Учебное пособ. для вузов. М.: ВШ. 2002.
5. , Сапоженко и упражнения по дискретной математике. М.: Физматлит, 2005.
6. Новиков математика для программистов. СПб.: Питер, 2002.
Программирование
Процедурное программирование. Структурное программирование.
События и сообщения. Механизмы передачи и обработки сообщений в объектно-ориентированных средах. Конструирование программ на основе иерархии объектов.
Объектно-ориентированная парадигма программирования. Абстракция данных. Наследование. Инкапсуляция. Полиморфизм. Проектирование классов: строки, стеки, списки, очереди, деревья. Классы математических объектов: рациональные и комплексные числа, вектора, матрицы.
ЛИТЕРАТУРА
Основная
1. Информатика / , , М.: Академия, 2012.
2. Объектно-ориентированный анализ и проектирование с примерами приложений на С++. М.: Издательство Бином, СПб: Невский диалект, 1999.
3. Алгоритмы: построение и анализ. Классические учебники: Computer Science, М.: МЦНМО, 1999.
Дополнительная
4. Искусство программирования. Т.1. Основные алгоритмы. М.: Вильямс, 2000.
5. Искусство программирования. Т.2. Получисленные алгоритмы. М.: Вильямс, 2000.
6. Искусство программирования. Т.1. Сортировка и поиск. М.: Вильямс, 2000.
Программное обеспечение ЭВМ
Ресурсы компьютера: виды и организация памяти, устройства ввода-вывода информации. Программное обеспечение ЭВМ, его основные характеристики. Классификация программного обеспечения.
Операционные системы как средство распределения и управления ресурсами.
Представление информации. Измерение информации. Понятие об информационных процессах. Принципы организации информационных процессов.
Понятие о системе программирования, ее основные функции и компоненты. Этапы разработки программ.
Прикладное программное обеспечение общего назначения. Системы обработки текстов. Системы машинной графики. Базы данных и системы управления базами данных. Табличные процессоры. Решение математических задач на ЭВМ. Математические пакеты.
ЛИТЕРАТУРА
Основная
1. Информатика / , , М.: Академия, 2012.
2. Старков персонального компьютера: организация, устройство, работа. -- М: Горячая линия - Телеком, 2009.
3. OpenOffice. org 3. Полное руководство пользователя. – BHV-CПб , 2010.
4. Операционная система Linux. Курс лекций. – М.: ДМК Пресс , 2010.
Дополнительная
1. , Маняхина и прикладное программное обеспечение. М.: МПГУ, 2011.
2. Информатика. Базовый курс / Под ред. , СПб.: Питер, 2000.
3. Реестр Windows 2000. СПб.: BHV, 2000.
4. Львовский и вёрстка в пакете LaTeX. – М.: Космосинформ, 1994.
5. , Коньков операционных систем. Курс лекций. Учебное пособие. /Под ред. . – М.:ИНТУИТ. ру, 2004.
6. Могилев А. В., , Хеннер по информатике: Учебное пособие для студентов высших учебных заведений. / Под ред. – М.: Издательский центр «Академия», 2002.
7. Corel Draw 9 в подлиннике. СПб.: BHV, 2000.
8. IBM PC для пользователя. - М,: 2002.
Архитектура компьютера
Поколения ЭВМ и их классификация.
Информационно-логические основы построения ЭВМ. Центральные и внешние устройства ЭВМ, их характеристики. Канальная и шинная системотехника. Микропроцессор и память компьютера. Система прерываний, регистры и модель доступа к памяти. Защищенный режим работы процессора как средство реализации многозадачности. Принципы управления внешними устройствами персонального компьютера. Базовая система ввода/вывода.
Ассемблер как машинно-ориентированный язык программирования.
ЛИТЕРАТУРА
Основная
1. Д. Паттерсон, Дж. Хеннесси. «Архитектура компьютера и проектирование компьютерных систем». «Питер», 2012.
2. Э. Таненбаум. «Архитектура компьютера», 5 изд., «Питер», 2007.
3.. «Assembler», СПб: «Питер», 2010.
4., . «Архитектура ЭВМ и систем». Учебник для вузов. Питер, 2006.
5.. «Основы языка Ассемблера», учебный курс. М. «Горячая линия-Телеком», 2001.
Дополнительная литература:
1. В. Пирогов «Ассемблер», СПб:»Нолидж-БХВ», 2003.
2., . «Архитектура ЭВМ и систем». Учебник для вузов. Питер, 2006.
3.Пильщиков В. Н. Assembler. «Программирование на языке Ассемблера для IBM PC». М.: Дифлог-МИФИ, 2003.
Компьютерные сети, интернет и мультимедиа технологии
Глобальные компьютерные сети. Предпосылки и история возникновения Интернет. Интернет как технология и информационный ресурс (сеть). Технология электронной почты. Технология обмена файлами (FTP). Технология WWW. Поиск информации в Интернет.
Угрозы информации в телекоммуникационных системах. Способы защиты информации.
Язык HTML как средство создания информационных ресурсов Интернет. Язык JavaScript как средство создания интерактивных Интернет-ресурсов.
Понятие мультимедиа. Мультимедиа как средство и технология. Создание мультимедийных приложений.
ЛИТЕРАТУРА
Основная
1. Компьютерные сети. Принципы, технологии, протоколы: учебник для вузов. Санкт-Петербург: Питер, 2012.
2. Таненбаум сети : учебно-методическое пособие. СПб: Питер, 2012.
3. Степанов вычислительных систем и компьютерный сетей : учебное пособие для вузов. - СПб: Питер, 2007.
4. Основы Web-технологий : учебное пособие. - Москва: БИНОМ. ЛЗ: Интернет-Университет, 2007.
Дополнительная литература:
5. Видеоматериалы и сетевые видеосервисы в работе учителя: практическое пособие/ , , [и др.]. – М.: БИНОМ. ЛЗ, 2008.
6. Компьютерная графика: Photoshop CS3, CorelDRAW CS3, IIIustrator CS3. Трюки и эффекты: учебно-методическое пособие/ Ю. Гурский, И. Гурская, А. Жвалевский. - СПб: Питер, 2008.
1. Усенков Web-мастера : учебное пособие. – М.: БИНОМ. ЛЗ, 2004.
2. Колбин и локальные сети: создание, настройка и использование : учебное пособие. – М.: БИНОМ. ЛЗ, 2007..
3. , , Фридланд и компьютерные технологии: Основные термины: Толковый словарь. — М.: ООО»Издательство Астрель»: АСТ», 2003.
7. Пятибратов системы, сети и телекоммуникации: учебник/ , , . М.: Финансы и статистика: ИНФРА-М, 2008.
Информационные системы
Основные понятия теории ИС. Введение в теорию баз данных. Компоненты информационной системы: база данных (БД), система управления базами данных (СУБД), администратор БД, словарь данных, вычислительная система, обслуживающий персонал. Понятие модели данных. Реляционная модель данных.
СУБД Access. Создание таблиц, форм, запросов, отчетов, макросов. Создание главной кнопочной формы.
СASE-средства. Структурный подход. Методология SADT. Диаграммы DFD и ERD. Примеры CASE-средств: SILVERRUN, ERwin, BPwin, RationalRose, Design/IDEF.
CASE-средства. Объектно-ориентированный подход (ООП). Основные элементы ООП: абстрагирование, инкапсуляция, модульность, иерархия, типизация, параллелизм, устойчивость. Основные понятия ООП: объект, класс. Группы понятий ООП: полиморфизм, наследование. Унифицированный язык моделирования UML.
Общая характеристика и классификация CASE-средств.
Проектирование ИС. Жизненный цикл ИС. Этапы процесса проектирования ИС. Инфологическое проектирование. Идентификация сущностей (выделение объектов рассматриваемой предметной области). Определение атрибутов сущностей (существенных свойств объектов). Установление всех (структурных, иерархических, запросных) связей между сущностями. Нормализация модели. Минимизация числа сущностей.
Даталогическое проектирование. Выбор программного средства. Этапы процесса даталогического проектирования после выбора инструментального средства.
Язык структурированных запросов SQL. Константы, операторы, null-значения. Типы данных языка SQL. Основные запросы (5 типов). Предложение SELECT: основные функции, синтаксис, примеры. Многотабличные запросы. Использование подзапросов. Оптимизация SQL-запросов. Использование индексов. Понятие транзакции. Свойства. Программное управление транзакциями. Транзакции в многопользовательском режиме.
Перспективы развития СУБД. Направление Postgres. Направление Exodus/Genesis. Направление Starburst. Объектно-реляционные СУБД. Использование технологий Internet и Intranet. Направление Web-СУБД.
OLAP-технологии. Понятие о хранилище данных. Потоки информации в OLAP. Основные подходы к созданию хранилищ данных. Многомерные базы данных.
ЛИТЕРАТУРА
Основная
1. Вендров программного обеспечения экономических информационных систем. - М., Финансы и статистика, 20с.
2. Введение в системы баз данных /Перевод , . - М., Наука. Глав. редакция физико-математической литературы, 20с.
3. , , Соболева курса «Информационные системы» в структурно-логических схемах. Учебное пособие. –М., МПГУ, 20с.
Дополнительная
1. Базы данных: проектирование, реализация и сопровождение. Теория и практика, 2-е изд.: Пер. с англ.: Учеб. пособие. - М., Издательский дом “Вильямс”, 20с.: ил. - Парал. тит. англ.
2. , Мак Методология структурного анализа и проектирования. - М., МетаТехнология, 1993.
3. Саймон технологии баз данных: Менеджмент на 2000 год: пер. с англ. /Под ред. и с предисл. . - М., Финансы и статистика, 19с.: ил.
4. , , СASE-технологии: Практикум. –М., Горячая линия-Телеком, 2003. – 160с.
5. Якубайтис сети и системы. Справочная книга. - М., Финансы и статистика, 19с.: ил.
Основы искусственного интеллекта
Понятие об искусственном интеллекте, основные подходы и методы. Предпосылки искусственного интеллекта (философия, математика, экономика, неврология, психология, вычислительная техника, кибернетика). История искусственного интеллекта.
Понятие о логическом программировании. Язык логических программ (вопросы, факты, термы, правила). Алгоритм унификации. Алгоритм абстрактного интерпретатора логических программ. Логическая и вычислительная модель логических программ.
Понятие о распознавании, общая схема и постановка задач распознавания, основные этапы развития распознавания, их характеристика, методология распознавания. Задачи классификации и задачи обучения по прецедентам, признаковое описание, шкалы измерений и обучающая информация. Модель алгоритма распознавания, функционал качества, метод обучения, построение функционалов качества алгоритмов, постановка задачи обучения на основе функционалов качества и функций потерь. Вероятностная постановка задачи обучения. Переобучение и обобщающая способность алгоритмов, оценка обобщающей способности алгоритмов. Эвристические принципы обучения, методы построения алгоритмов на основе принципа сходства. Построение алгоритмов на основе принципа регуляризации. Построение алгоритмов на основе принципа разделимости и отделимости. Композиции алгоритмов и понятие об алгебраическом подходе к построению распознающих алгоритмов. Построение алгоритмов на основе принципа селекции и самоорганизации.
Понятие о нейронных сетях. Модели нейронов и нейронных сетей. Метод обратного распространения ошибки. Конструктивные методы обучения нейронных сетей.
ЛИТЕРАТУРА
Основная
1. Искусственный интеллект. Современный подход. – М.: Издательский дом «Вильямс». 2006 г. – 1408 с.
2. Искусство программирования на языке Пролог. М.: Мир. 1990 г. – 333 с.
3. Журавлев образов и распознавание изображений. – В сб. Распознавание. Классификация. Прогноз. Вып. 2. 1989 г. с. 5-72.
4. Машинное обучение (электронный ресурс).
http://www. *****/wiki/index. php? title=Машинное_обучение_(курс_лекций,_)
Дополнительная
1. , , Сенько . Математические методы. Программная система. Практические применения. 2005 г. – 159 с.
2. Осовский С. Нейронные сети для обработки информации. – М.: Финансы и статистика. 2002 г. – 341 с.
3. Горбань А. Н., Россиев сети на персональном компьютере. – Новосибирск: Наука. 1996 г. – 274 с.
Компьютерное моделирование
Моделирование как метод познания. Цели и задачи моделирования. Понятие «модель.
Информационные модели. Объекты и их связи. Основные структуры в информационном моделировании.
Понятие «математическая модель». Классификации математических моделей. Характеристики моделируемого явления. Уравнения математических моделей. Внешние и внутренние характеристики математической модели. Замкнутые математические модели.
Имитационные модели и системы. Области и условия применения. Этапы построения имитационной модели. Критерии оценки адекватности модели. Имитационные эксперименты.
Моделирование сложных систем, объектно-событийный подход.
ЛИТЕРАТУРА
1. , Петров построения моделей. М.: Фазис, 2000
2. Павловский модели и системы. М.: Фазис, 2000
