Программа государственного экзамена по информатике и вычислительной технике

(специальность «Информатика» заочное отделение – 2012 г.)

!!!Подсказки!!! Раздел 1. Теоретические основы информатики (3 вопроса)

Информатика как наука и как вид практической деятельности. Место информатики в системе наук.

Информация и ее виды. Передача, хранение и обработка информации. Кодирование информации. Измерение дискретной информации. Системы счисления, используемые в информатике. Перевод чисел из одной системы счисления в другую. Представление информации в ЭВМ.

Информация и энтропия. Информационный процесс. Формы представления информации. Дискретизация сигнала. Теорема отсчетов (Котельникова). Вероятностный (содержательный) подход к измерению информации: энтропия, условная энтропия, связь энтропии и информации, формула Шеннона, формула Хартли. Объемный подход к измерению информации. Соотношение объёмной и содержательной мер информации.

Задачи теории кодирования. Код, кодирование, декодирование. Условие обратимого кодирования. Длина кода. Избыточность кода. Первая теорема Шеннона. Классификация двоичных кодов. Префиксные коды. Коды Хаффмана и Шеннона-Фано.

Реальные каналы связи. Характеризация каналов связи с помехами. Вторая теорема Шеннона. Помехоустойчивые коды. Классификация помехоустойчивых кодов. Задача помехоустойчивого кодирования. Принципы обнаружения и исправления ошибок. Код Хэмминга.

Раздел 2. Основы микроэлектроники и архитектура компьютера (3 вопроса)

Базовые логические функции и элементы. Способы представления «0» и «1» в ЭВМ. История элементной базы ЭВМ. Поколения ЭВМ.

Комбинационные логические устройства (шифраторы, дешифраторы, мультиплексоры, демультиплексоры).

Последовательностные логические устройства (триггеры, регистры).

Классификация компьютеров. Принципы фон Неймана и классическая архитектура компьютера. Архитектура персонального компьютера. Центральные и внешние устройства ЭВМ. Шины адреса, данных, управления.

Микропроцессор 8086. Программно доступные регистры: РОН, индексные и указательные регистры, сегментные регистры. Система прерываний.

Система команд микропроцессора 8086. Мнемоническое кодирование. Форматы данных. Способы адресации данных.

Раздел 3. Элементы абстрактной и компьютерной алгебры (1 вопрос)

Понятие группы. Пример использования свойств мультипликативной группы для шифрования с открытым ключом. Электронная подпись.

Кольцо классов вычетов. Применение свойств колец классов вычетов для организации шифрования с закрытым ключом.

Кольцо многочленов от одной переменной. Алгоритм деления.

.

Раздел 4. Теория алгоритмов (2 вопроса)

Понятие алгоритма в интуитивном смысле. Массовые проблемы и их взаимная сводимость.

Сложность алгоритмов и массовых проблем. Понятие NP-полноты.

Формализация понятия алгоритма. Частично рекурсивные функции. Оператор минимизации. Теорема об ограниченном операторе минимизации.

Нормальные алгорифмы Маркова. Машина Тьюринга и вычислимые на ней функции. Тезис Чёрча. Понятие об алгоритмической неразрешимости задач.

Свойства и типы алгоритмов. Понятие исполнителя алгоритма. Способы записи алгоритмов.

Раздел 5. Программирование (6 вопросов)

Алгоритмические структуры и их реализация на языке программирования Паскаль.

Алфавит языка Паскаль. Идентификаторы. Простые типы данных в Паскале: целые, вещественные, логические, символьные. Переменные. Константы. Арифметические и логические выражения.

Структура программы на языке Паскаль. Разделы описаний. Организация ввода-вывода данных. Форматированный вывод. Оператор присваивания. Составной оператор. Условный оператор: полный и неполный. Оператор варианта. Оператор цикла с предусловием. Оператор цикла с постусловием. Оператор цикла с параметром.

Подпрограммы, их виды, описание, обращение к ним. Формальные и фактические параметры. Локальные и глобальные переменные. Рекурсивные функции.

Структурированные типы данных. Массивы в языке программирования Паскаль. Описание и задание массива. Одномерные и двумерные массивы. Алгоритмы обработки массивов: поиск в массиве (линейный, бинарный), вставка и удаление элементов, сортировка массива. Строки. Описание и задание строк. Операции, процедуры и функции работы со строками. Моделирование множеств в языке программирования Паскаль (способы описании и задания множеств, операции над ними). Записи (комбинированный тип). Описание записей, задание записей, обращение к полям записи. Оператор with. Записи с вариантной частью. Файлы: текстовые, типизированные, нетипизированные. Процедуры и функции для работы с файлами.

Основы объектно-ориентированного программирования. Понятие объекта. Принципы инкапсуляции, наследования, полиморфизма