Математические основы информатики

Тексты и кодирование. Передача данных

Знаки, сигналы и символы. Знаковые системы.

Равномерные и неравномерные коды. Префиксные коды. Условие Фано. Обратное условие Фано. Алгоритмы декодирования при использовании префиксных кодов.

Сжатие данных. Учет частотности символов при выборе неравномерного кода. Оптимальное кодирование Хаффмана. Использование программ-архиваторов. Алгоритм LZW.

Передача данных. Источник, приемник, канал связи, сигнал, кодирующее и декодирующее устройства.

Пропускная способность и помехозащищенность канала связи. Кодирование сообщений в современных средствах передачи данных.

Искажение информации при передаче по каналам связи. Коды с возможностью обнаружения и исправления ошибок.

Способы защиты информации, передаваемой по каналам связи. Криптография (алгоритмы шифрования). Стеганография.

Дискретизация

Измерения и дискретизация. Частота и разрядность измерений. Универсальность дискретного представления информации.

Дискретное представление звуковых данных. Многоканальная запись. Размер файла, полученного в результате записи звука.

Дискретное представление статической и динамической графической информации.

Сжатие данных при хранении графической и звуковой информации.

Системы счисления

Свойства позиционной записи числа: количество цифр в записи, признак делимости числа на основание системы счисления.

Алгоритм перевода десятичной записи числа в запись в позиционной системе с заданным основанием. Алгоритмы построения записи числа в позиционной системе счисления с заданным основанием и вычисления числа по строке, содержащей запись этого числа в позиционной системе счисления с заданным основанием.

Арифметические действия в позиционных системах счисления.

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

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

Элементы комбинаторики, теории множеств и математической логики

Операции "импликация", "эквиваленция". Логические функции.

Законы алгебры логики. Эквивалентные преобразования логических выражений. Логические уравнения.

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

Логические элементы компьютеров. Построение схем из базовых логических элементов.

Дискретные игры двух игроков с полной информацией. Выигрышные стратегии.

Дискретные объекты

Решение алгоритмических задач, связанных с анализом графов (примеры: построения оптимального пути между вершинами ориентированного ациклического графа; определения количества различных путей между вершинами).

Обход узлов дерева в глубину. Упорядоченные деревья (деревья, в которых упорядочены ребра, выходящие из одного узла).

Использование деревьев при решении алгоритмических задач (примеры: анализ работы рекурсивных алгоритмов, разбор арифметических и логических выражений). Бинарное дерево. Использование деревьев при хранении данных.

Использование графов, деревьев, списков при описании объектов и процессов окружающего мира.