Дискретный анализ и теория информации
Министерство образования и науки Российской Федерации
ФГБОУ ВПО «Пензенский государственный университет»
ПРОГРАММА
ВСТУПИТЕЛЬНОГО ЭКЗАМЕНА В МАГИСТРАТУРУ
ПО НАПРАВЛЕНИЮ ПОДГОТОВКИ
231000.68 «ПРОГРАММНАЯ ИНЖЕНЕРИЯ»
Пенза 2013
Общие вопросы информатики и вычислительной техники
Операционные системы
2.1 Основные средства аппаратной поддержки функций ОС: система прерываний, защита памяти, механизм преобразования адресов в системах виртуальной памяти, управление периферийными устройствами.
2.3 Распределение и использование ресурсов вычислительной системы. Управление ресурсами. Основные подходы и алгоритмы планирования. Системы реального и разделенного времени.
Системы программирования
3.2 Понятие о методах трансляции. Лексический, синтаксический, семантический анализ. Основные алгоритмы генерации объектного кода. Машинно-ориентированные языки (ассемблеры), области применения, мнемоники, метки (символы).
Методы хранения, организация и доступ к данным
4.1 Концепция типа и моделей данных. Абстрактные типы данных. Объекты (основные свойства и отличительные черты). Иерархическая, сетевая, и реляционная модель данных.
4.2 Основные структуры данных, алгоритмы обработки и поиска. Организация физического уровня баз данных. Методы индексирования и сжатия данных.
Математическая логика и теория алгоритмов
5.4 Теория вычислимости. Примитивно-рекурсивные, общерекурсивные и частично-рекурсивные функции. Машины Тьюринга, теорема о правильной вычислимости частично-рекурсивных функций. Кодировка машин Тьюринга. Нормальная форма Клини. Эквивалентность классов вычислимых функций.
5.5 Представление рекурсивных функций в арифметике Пеано. Теорема Гёделя о неполноте. Теоремы о неразрешимости логики предикатов и арифметики. Существование рекурсивно-перечислимого, но не рекурсивного множества, неразрешимость проблемы остановки программы.
Дискретный анализ и теория информации
6.1 Полнота и замкнутость систем булевых функций. Основные замкнутые классы. Теорема Поста о полноте. Сложность реализации булевых функций в классе схем из функциональных элементов. Теорема Шеннона о сложности реализации булевых функций в классе схем из функциональных элементов.
6.3 Формула включений и исключений. Производящие функции, возвратные последовательности и линейные рекуррентные соотношения; общее решение линейного рекуррентного соотношения.
6.4 Циклические коды. Определение циклического кода. Теорема о необходимом и достаточном условии существования циклического кода с порождающим многочленом g(x). Кодирование и декодирование циклических кодов. Примеры циклических кодов: коды Хэмминга.
6.5 Разделимые и префиксные коды. Оптимальное кодирование. Метод Хаффмена. Метод Шеннона для бернуллиевских источников. Критерий разделимости побуквенного кодирования. Теоремы Маркова.