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

Расчет количества вариантов: формулы перемножения и сложения количества вариантов. Количество текстов данной длины в данном алфавите.

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

Высказывания. Простые и сложные высказывания. Диаграммы Эйлера-Венна. Логические значения высказываний. Логические выражения. Логические операции: «и» (конъюнкция, логическое умножение), «или» (дизъюнкция, логическое сложение), «не» (логическое отрицание). Правила записи логических выражений. Приоритеты логических операций.

Таблицы истинности. Построение таблиц истинности для логических выражений.

Логические операции следования (импликация) и равносильности (эквивалентность).Свойства логических операций. Законы алгебры логики. Использование таблиц истинности для доказательства законов алгебры логики. Логические элементы. Схемы логических элементов и их физическая (электронная) реализация. Знакомство с логическими основами компьютера.

Списки, графы, деревья

Список. Первый элемент, последний элемент, предыдущий элемент, следующий элемент. Вставка, удаление и замена элемента.

Граф. Вершина, ребро, путь. Ориентированные и неориентированные графы. Начальная вершина (источник) и конечная вершина (сток) в ориентированном графе. Длина (вес) ребра и пути. Понятие минимального пути. Матрица смежности графа (с длинами ребер).

Дерево. Корень, лист, вершина (узел). Предшествующая вершина, последующие вершины. Поддерево. Высота дерева. Бинарное дерево. Генеалогическое дерево.

Алгоритмы и элементы программирования

Исполнители и алгоритмы. Управление исполнителями

Исполнители. Состояния, возможные обстановки и система команд исполнителя; команды-приказы и команды-запросы; отказ исполнителя. Необходимость формального описания исполнителя. Ручное управление исполнителем.

Алгоритм как план управления исполнителем (исполнителями). Алгоритмический язык (язык программирования) – формальный язык для записи алгоритмов. Программа – запись алгоритма на конкретном алгоритмическом языке. Компьютер – автоматическое устройство, способное управлять по заранее составленной программе исполнителями, выполняющими команды. Программное управление исполнителем. Программное управление самодвижущимся роботом.

Словесное описание алгоритмов. Описание алгоритма с помощью блок-схем. Отличие словесного описания алгоритма, от описания на формальном алгоритмическом языке.

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

Понятие об этапах разработки программ и приемах отладки программ.

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

Алгоритмические конструкции

Конструкция «следование». Линейный алгоритм. Ограниченность линейных алгоритмов: невозможность предусмотреть зависимость последовательности выполняемых действий от исходных данных.

Конструкция «ветвление». Условный оператор: полная и неполная формы.

Выполнение и невыполнения условия (истинность и ложность высказывания). Простые и составные условия. Запись составных условий.

Конструкция «повторения»: циклы с заданным числом повторений, с условием выполнения, с переменной цикла. Проверка условия выполнения цикла до начала выполнения тела цикла и после выполнения тела цикла: постусловие и предусловие цикла. Инвариант цикла.

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

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