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

Тексты и кодирование

Равномерные и неравномерные коды. Условие Фано.

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

Сравнение чисел, записанных в двоичной, восьмеричной и шестнадцатеричной системах счисления. Сложение и вычитание чисел, записанных в этих системах счисления.

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

Операции "импликация", "эквивалентность". Примеры законов алгебры логики. Эквивалентные преобразования логических выражений. Построение логического выражения с данной таблицей истинности. Решение простейших логических уравнений.

Нормальные формы: дизъюнктивная и конъюнктивная нормальная форма.

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

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