Главная > Программа


Программа кандидатского минимума

по специальности 01.01.09

(дискретная математика и математическая кибернетика)

 

I Основная часть

 

Раздел 1. ТЕОРИЯ ИНФОРМАЦИИ И КОДИРОВАНИЯ

  1. Энтропия и ее свойства. Количество информации.

Источник сообщения, его энтропия и избыточность.

Общая схема линии связи. Поток информации и пропускная способность канала связи.

Оптимальное кодирование.

Конечные поля и их основные свойства.

  1. Линейный код и способы его задания. Процесс декодирования линейного кода. Корректирующие свойства кодов. БЧХ-коды. Код Хемминга.

 

Раздел 2. МАТЕМАТИЧЕСКАЯ ЛОГИКА

7.     Булевы функции. Представление булевых функций формулами алгебры высказываний и  многочленами  Жегалкина.

8.     Замкнутые классы функций. Критерии полноты для булевых функций. 

  1. Исчисления высказываний и предикатов, их полнота и непротиворечивость.

10.  Основные подходы к формализации понятия алгоритма: машины Тьюринга, рекурсивные функции, нормальные алгоритмы Маркова.

11.  Понятие сложности алгоритма. Классы сложности.

 

Раздел 3. АВТОМАТЫ

  1. Определение автомата и полуавтомата. Способы задания автомата и полуавтомата.

Изоморфные автоматы. Сравнимые автоматы. Автономные автоматы. Автономные компоненты автомата.

Бинарное отношение. Отношение эквивалентности.

Эквивалентность, к-эквивалентность состояний автомата. Различимость  и неразличимость состояний.

  1. Достижимость состояний автомата. Сильно связный автомат. Теорема о сильно связных сравнимых автоматах, имеющих эквивалентные состояния.

 

Раздел 4. ФОРМАЛЬНЫЕ ЯЗЫКИ

17.  Грамматика. Язык, порождаемый грамматикой. Примеры.

18.  Виды грамматик и языков. Теорема о контекстно-зависимых и контекстно-свободных языках.

19.  Акцепторы. Распознаваемые языки. Регулярные языки.

20.  Критерий распознаваемости языка. Теорема Клини.

21.  Критерий регулярности языка.

 

 

Раздел 3. ДИСКРЕТНАЯ ОПТИМИЗАЦИЯ

  1. Машины Тьюринга. Вычислимые функции. Универсальные машины Тьюринга.

Алгоритмы на графах.  Обход графа в глубину, построение глубинного остовного леса и классификация ребер не вошедших в лес.

Алгоритмы нахождения компонент связности, двусвязных компонент неориентированных графах и сильно связных компонент ориентированных графов.

Алгоритмы построения остовных деревьев минимальной стоимости (алгоритм Крускала). Поиск в ширину и кратчайшие пути в графе.

Алгоритм нахождения кратчайших расстояний от выделенной вершины до всех остальных вершин графа (алгоритм Дейкстры). Оценки сложности.

Структуры данных для задач, касающихся работы с непересекающимися множествами. Операции с непересекающимися множествами (объединить и найти). Реализация множеств с помощью списков и деревьев. Оценки трудоемкости.

Алгоритмы внутренней сортировки. Сортировки сравнениями: сортировка вставками в дерево, пирамидальная сортировка, быстрая сортировка. Лексикографическая сортировка как пример распределяющей сортировки. Оценки трудоемкости.

  1. Алгоритмы поиска в деревьях. Деревья двоичного поиска, сбалансированные по высоте. Оценка максимальной и средней высоты сбалансированного дерева с n узлами. Алгоритм вставки и удаления элемента в дерево двоичного поиска, сбалансированное по высоте.

 

 

 

II Специальная часть

 

Раздел 4. ОПЕРАЦИОННЫЕ СИСТЕМЫ

  1. Понятие операционной системы. Поколения ОС. Классификация ОС. Основные функции ОС. ОС как менеджер ресурсов.

Оперативная память. Организация памяти: страничная, сегментная, сегментно-страничная. Принципы защиты основной памяти. Подкачка. Свопинг. Управление памятью с помощью битовых массивов. Управление памятью с помощью связных списков. Виртуальная память.

Реализация файловой системы. Структура файловой системы. Организация дискового пространства и учет свободных блоков. Связные списки. FAT, Ext2, NTFS.

  1. Примитивы  межпроцессного  взаимодействия.  Проблема производителя  и потребителя.  Разделяемая память. Примитивы sleep и wakeup. Семафоры. Мьютексы. Передача сообщений. Барьеры.

 

Раздел 5. КОМПЬЮТЕРНЫЕ СЕТИ

  1. Стек  протоколов  TCP/IP.  Адресация  в  IP-сетях:   понятие  IP-адреса,  адреса  сети,  маски  подсети, зарезервированные адреса. Маршрутизация в IP-сетях: виды маршрутизации, таблица маршрутизации

Понятие вычислительной сети. Топологии сетей. Физическая организация сетей: Ethernet, Token Ring, FDDI Семиуровневая модель ISO/OSI.

Технология Ethernet. Принцип случайного множественного доступа к среде передачи - CSMA/CD. Ограничение   на   максимальный   размер   широковещательной   сети   (домена   коллизий)   Ethernet. Полнодуплексные   линии   Ethernet.   Условия   для   организации   полного   дуплекса,   преимущества использования.

  1. Понятие  концентратора,   коммутатора.   Принципы   их  работы.   Управляемые  коммутаторы  Ethernet. Spanning Tree. VLAN.

 

Раздел 6. БАЗЫ ДАННЫХ

  1. Основные модели данных: иерархическая, сетевая, реляционная, дедуктивная.

Классификация баз данных. Понятие Банка Данных. Свойства банка данных:    НЕЗАВИСИМОСТЬ, ОГРАНИЧЕННОСТЬ ДОСТУПА. По отношению к каким параметрам/точкам (объектам) банка данных можно ограничить доступ,  как это реализуется.  Понятие целостности  и  непротиворечивости базы данных. Методы и средства обеспечения целостности и непротиворечивости.

Реляционная   модель   данных.   Суть,   достоинства   и   недостатки.   Понятие   о   нормализации,   виды нормальных форм, какие недостатки они устраняют.

Базы   Данных.    Системы   с   коллективным   использованием   файлов(файл-серверная   архитектура): описание, достоинства и недостатки. Системы с архитектурой клиент-сервер: организация, достоинства и недостатки.

Базы Данных. Типы данных. Общий вид оператора SQL (Select, insert, update, delete). Многотабличные запросы, вложенные подзапросы, объединения. Примеры.

  1. Oracle.    Понятие    схемы,    логическое    представление    базы   данных,    объекты    схемы:    таблица, представление. Общие и различные черты, использование.

 

Раздел 7. ЗАЩИТА ПРОГРАММ И ДАННЫХ ОТ НЕСАНКЦИОНИРОВАННОГО ДОСТУПА

  1. Отладка приложений. Типы отладчиков(уровня ядра и пользователя). Win32 Debug API. Механизмы постановки и обработки точек останова. Обнаружение факта выполнения приложения в контексте отладчика. Дизассемблеры.

Процессор. Принципы работы. Команды процессора. Счетчик команд. Указатель стека. Слово состояния процессора. Режимы работы процессора. Квантование времени.

Программно-технические методы защиты портативных носителей информации от несанкционированного копирования и использования.

Формат исполнимых файлов Portable Executable (PE). Общая структура. Специальные структуры PE: директория импорта, отложенного импорта, привязанного импорта (Import Directory, Delay Import, Bound Import), директория экспорта, директория TLS, директория отладки, директория безопасности (Security Directory), директория перемещаемых элементов (Relocation Table).

Драйверы операционной системы Windows. Уровни запросов прерываний. Диспетчер управления службами. Служба как объект Windows. Процедуры диспетчеризации запросов ввода-вывода. Взаимодействие с драйвером из приложения пользователя.

  1. Трассировка кода. Механизмы SEH и VEH. Основные понятия. Примеры использования. Достоинства и недостатки. Финальный обработчик исключений.

 

 

ЛИТЕРАТУРА

К разделу «ТЕОРИЯ ИНФОРМАЦИИ И КОДИРОВАНИЯ»

  1. Лидл Р., Нидеррайтер Г. Конечные поля: В 2-ч т. Т. 1. Пер. с англ. – М.: Мир, 1988. – 430 с.

Блейхут Р. Теория и практика кодов, контролирующих ошибки: Пер. с англ. – М.: Мир, 1986. – 576 с., ил.

Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов. Пер. с англ. – М.: Мир, 1989. – 448 с., ил.

Ross N. Williams. Элементарное руководство по CRC алгоритмам обнаружения ошибок. Перевод выполнен на сайте: . - 36c(pdf).

  1. М. Вернер Основы кодирования. Учебник для ВУЗов. Москва: Техносфера, 2004.-288с.

 

К разделу «МАТЕМАТИЧЕСКАЯ ЛОГИКА»

  1. Элементы математической логики : Методические указания к практическим и индивидуальным занятиям/ С.Ю.Белецкая, Л.Д.Кретова, Е.Н.Королев, Н.Б.Ускова. Воронеж.: ВГТУ, 1998. 20 с.

Минимизация булевых функций :  Методические  указания  к практическим и индивидуальным занятиям/ С.Ю.Белецкая, Л.Д.Кретова, Н.Б.Ускова. Воронеж.: ВГТУ, 1998. 38 с.

Мендельсон Э. Введение в математическую логику. М.: Наука, 1976. 320 с.

  1. Мощенский С.С. Лекции по математической логике. М.: Наука, 1970.

 

К разделу «АВТОМАТЫ»

  1. Лидл Р., Пильц Г. Прикладная абстрактная алгебра: Учебное пособие: Пер. с англ. – Екатеринбург: Издательство Уральского университета, 1996. – 744 с.

Яблонский С.В. Введение в дискретную математику. М.: Высш. школа, 2001.

  1. Оре О. Теория графов. М.: Наука, 1980.

 

К разделу «ФОРМАЛЬНЫЕ ЯЗЫКИ»

  1. Пентус А. Е., Пентус М. Р. Теория формальных языков. 2004

А. Ахо, Дж. Ульман. Теория синтаксического анализа, перевода и компиляции. М. Мир. 1978 г. тт 1,2.

Новиков Ф.А.  Дискретная математика для программистов. С.-П.: Питер, 2001.

Малявко А.А. Теория формальных языков: Учеб. пособие. – Новосибирск: Изд-во НГТУ, 2002. – Ч.1, Ч2.

  1. Малявко А.А.  Теория формальных языков: Учеб. Пособие. – Новосибирск: Изд-во НГТУ, 2004. – Ч. 3.

 

К разделу «ДИСКРЕТНАЯ ОПТИМИЗАЦИЯ»

  1. Гермейер Ю.Б. Введение в теорию исследования операций. М.: Наука, 1969.

Мальцев А. И. Алгоритмы и вычислимые функции. М.: Наука, 1986.

  1. Дональд Э. Кнут. Искусство программирования, 3-е издание, 1-3 т.

 

К разделу «ОПЕРАЦИОННЫЕ СИСТЕМЫ»

  1. Соломон Д. и Руссинович М. Внутреннее устройство Microsoft Windows 2000. Мастер-класс / Пер. с англ. – СПб.: Питер; М.; Издательско-торговый дом «Русская Редакция». 2004. – 746 стр.: ил.

Рихтер. Windows для профессионалов: создание эффективных Win32-приложений с учетом специфики 64-разрядной версии Windows. Пер. с англ.- СПб.: Питер, 2004. - 722 c.

  1. Таненбаум Э. Современные операционные системы. 2-е изд - СПб.: Питер, 2002. – 1040 с. с ил.

К разделу «КОМПЬЮТЕРНЫЕ СЕТИ»

  1. Э. Таненбаум. Компьютерные сети. 4-е изд. — СПб.: Питер, 2003. — 992 с: ил. — (Серия Классика computer science).

М.В. Кульгин. Компьютерные сети. Практика построения. Для профессионалов. 2-е изд. – СПб.: Питер, 2003. – 462с.: ил.

  1. В.Г. Олифер, Н.А. Олифер. Компьютерные сети. Принципы, технологии, протоколы. - СПб.: Питер, 2001. – 472с.: ил.

 

К разделу «БАЗЫ ДАННЫХ»

  1. Конноли Б., Бегг К. Базы данных. Проектирование, реализация и сопровождение. Теория и практика. 3-е издание.: Пер. с англ. – М.: Издательский дом «Вильямс», 2003. – 1440 с.: ил.

Рик Гринвальд, Роберт Стаковьяк, Гэри Додж, Дэвид Кляйн, Бен Шапиро, Кристофер Дж. Челья. Программирование баз данных Oracle для профессионалов.: Пер. с англ. – М.: Издательский дом «Диалектика», 2007. -  784 стр., с ил.

Мартин Дж., Организация баз данных в вычислительных системах, Москва, «Мир», 1980г.

А Ахо., Дж. Хопкрофт, Дж. Ульман, Построение и анализ вычислительных алгоритмов, Москва, «Мир», 1972г.

  1. Гасанов Э.Э., Кудрявцев В.Б., Теория хранения и поиска информации. Москва, «Физматлит», 2002 г.

 

К разделу «ЗАЩИТА ПРОГРАММ И ДАННЫХ ОТ НЕСАНКЦИОНИРОВАННОГО ДОСТУПА»

  1. Гук М. Интерфейсы ПК: справочник – СПб: ЗАО «Издательство «Питер», 1999. – 416 с.: ил.

Касперски К. Техника защиты компакт-дисков от копирования. – СПб.: БХВ-Петербург, 2004. – 464 с.: ил.

Солдатов В.П. Программирование драйверов Windows. Изд. 3-е, перераб. и доп. – М.: ООО «Бином-Пресс», 2006г. – 576 с.: ил.

Ховард М., Лебланк Д.  Защищенный код: Пер. с англ. -2-е изд., испр. М.: Издательский дом ";Русская Редакция";, 2004. – 704 с.

Свен Шрайбер, ";Недокументированные возможности Windows 2000";, изд. ";Питер";, 2002.

  1. Электронное издание книги: Oney,Walter. Programming the Microsoft Windows Driver Model / Walter Oney -- 2nd ed. – на англ. Яз.



Скачать документ

Похожие документы:

  1. Программа кандидатского минимума

    Программа
    Программакандидатскогоминимума по специальности 01.01. ... черты, использование. Раздел 7. ЗАЩИТА ПРОГРАММ И ДАННЫХ ОТ НЕСАНКЦИОНИРОВАННОГО ДОСТУПА Отладка ... «Физматлит», 2002 г. К разделу «ЗАЩИТА ПРОГРАММ И ДАННЫХ ОТ НЕСАНКЦИОНИРОВАННОГО ДОСТУПА» Гук ...
  2. Программа кандидатского минимума по специальности 08

    Программа-минимум
    ... ) по экономическим наукам ОБЩИЕ ПОЛОЖЕНИЯ Программакандидатскогоминимума по специальности 08.00.05 ... в каждой конкретной программекандидатскогоминимума данного Научного центра. На экзамене кандидатскогоминимума по специальности 08 ...
  3. Программа кандидатского минимума по специальности «микология» 03 02 12 введение

    Программа
    ПРОГРАММАКАНДИДАТСКОГОМИНИМУМА ПО СПЕЦИАЛЬНОСТИ «МИКОЛОГИЯ» 03.02. ...
  4. Программа кандидатского минимума по специальности «микология» 03 02 12 введение

    Программа
    ПРОГРАММАКАНДИДАТСКОГОМИНИМУМА ПО СПЕЦИАЛЬНОСТИ «МИКОЛОГИЯ» 03.02. ...
  5. Программа кандидатского минимума по специальности «ботаника» 03 02 01 1 системы водорослей общий очерк основных положений и тенденций

    Программа
    ПРОГРАММАКАНДИДАТСКОГОМИНИМУМА ПО СПЕЦИАЛЬНОСТИ «БОТАНИКА» 03.02. ...

Другие похожие документы..