Элементы комбинаторики, теории множеств и математической логики
Расчет количества вариантов: формулы перемножения и сложения количества вариантов. Количество текстов данной длины в данном алфавите.
Множество. Определение количества элементов во множествах, полученных из двух или трех базовых множеств с помощью операций объединения, пересечения и дополнения.
Высказывания. Простые и сложные высказывания. Диаграммы Эйлера-Венна. Логические значения высказываний. Логические выражения. Логические операции: «и» (конъюнкция, логическое умножение), «или» (дизъюнкция, логическое сложение), «не» (логическое отрицание). Правила записи логических выражений. Приоритеты логических операций.
Таблицы истинности. Построение таблиц истинности для логических выражений.
Логические операции следования (импликация) и равносильности (эквивалентность). Свойства логических операций. Законы алгебры логики. Использование таблиц истинности для доказательства законов алгебры логики. Логические элементы. Схемы логических элементов и их физическая (электронная) реализация. Знакомство с логическими основами компьютера.
Списки, графы, деревья
Список. Первый элемент, последний элемент, предыдущий элемент, следующий элемент. Вставка, удаление и замена элемента.
Граф. Вершина, ребро, путь. Ориентированные и неориентированные графы. Начальная вершина (источник) и конечная вершина (сток) в ориентированном графе. Длина (вес) ребра и пути. Понятие минимального пути. Матрица смежности графа (с длинами ребер).
|
|
|
Дерево. Корень, лист, вершина (узел). Предшествующая вершина, последующие вершины. Поддерево. Высота дерева. Бинарное дерево. Генеалогическое дерево.
Алгоритмы и элементы программирования
Исполнители и алгоритмы. Управление исполнителями
Исполнители. Состояния, возможные обстановки и система команд исполнителя; команды-приказы и команды-запросы; отказ исполнителя. Необходимость формального описания исполнителя. Ручное управление исполнителем.
Алгоритм как план управления исполнителем (исполнителями). Алгоритмический язык (язык программирования) – формальный язык для записи алгоритмов. Программа – запись алгоритма на конкретном алгоритмическом языке. Компьютер – автоматическое устройство, способное управлять по заранее составленной программе исполнителями, выполняющими команды. Программное управление исполнителем. Программное управление самодвижущимся роботом.
Словесное описание алгоритмов. Описание алгоритма с помощью блок-схем. Отличие словесного описания алгоритма, от описания на формальном алгоритмическом языке.
Системы программирования. Средства создания и выполнения программ.
|
|
|
Понятие об этапах разработки программ и приемах отладки программ.
Управление. Сигнал. Обратная связь. Примеры: компьютер и управляемый им исполнитель (в том числе робот); компьютер, получающий сигналы от цифровых датчиков в ходе наблюдений и экспериментов, и управляющий реальными (в том числе движущимися) устройствами.
Алгоритмические конструкции
Конструкция «следование». Линейный алгоритм. Ограниченность линейных алгоритмов: невозможность предусмотреть зависимость последовательности выполняемых действий от исходных данных.
Конструкция «ветвление». Условный оператор: полная и неполная формы.
Выполнение и невыполнение условия (истинность и ложность высказывания). Простые и составные условия. Запись составных условий.
Конструкция «повторения»: циклы с заданным числом повторений, с условием выполнения, с переменной цикла. Проверка условия выполнения цикла до начала выполнения тела цикла и после выполнения тела цикла: постусловие и предусловие цикла. Инвариант цикла.
Запись алгоритмических конструкций в выбранном языке программирования.
Примеры записи команд ветвления и повторения и других конструкций в различных алгоритмических языках.
|
|
|
Разработка алгоритмов и программ
Оператор присваивания. Представление о структурах данных.
Константы и переменные. Переменная: имя и значение. Типы переменных: целые, вещественные, символьные, строковые, логические. Табличные величины (массивы). Одномерные массивы. Двумерные массивы.
Примеры задач обработки данных:
· нахождение минимального и максимального числа из двух, трех, четырех данных чисел;
· нахождение всех корней заданного квадратного уравнения;
· заполнение числового массива в соответствии с формулой или путем ввода чисел;
· нахождение суммы элементов данной конечной числовой последовательности или массива;
· нахождение минимального (максимального) элемента массива.
Знакомство с алгоритмами решения этих задач. Реализации этих алгоритмов в выбранной среде программирования.
Составление алгоритмов и программ по управлению исполнителями Робот, Черепашка, Чертежник и др.
Знакомство с постановками более сложных задач обработки данных и алгоритмами их решения: сортировка массива, выполнение поэлементных операций с массивами; обработка целых чисел, представленных записями в десятичной и двоичной системах счисления, нахождение наибольшего общего делителя (алгоритм Евклида).
|
|
|
Понятие об этапах разработки программ: составление требований к программе, выбор алгоритма и его реализация в виде программы на выбранном алгоритмическом языке, отладка программы с помощью выбранной системы программирования, тестирование.
Простейшие приемы диалоговой отладки программ (выбор точки останова, пошаговое выполнение, просмотр значений величин, отладочный вывод).
Знакомство с документированием программ. Составление описание программы по образцу.
Анализ алгоритмов
Сложность вычисления: количество выполненных операций, размер используемой памяти; их зависимость от размера исходных данных. Примеры коротких программ, выполняющих много шагов по обработке небольшого объема данных; примеры коротких программ, выполняющих обработку большого объема данных.
Определение возможных результатов работы алгоритма при данном множестве входных данных; определение возможных входных данных, приводящих к данному результату. Примеры описания объектов и процессов с помощью набора числовых характеристик, а также зависимостей между этими характеристиками, выражаемыми с помощью формул.
Робототехника
Робототехника – наука о разработке и использовании автоматизированных технических систем. Автономные роботы и автоматизированные комплексы. Микроконтроллер. Сигнал. Обратная связь: получение сигналов от цифровых датчиков (касания, расстояния, света, звука и др.
Примеры роботизированных систем (система управления движением в транспортной системе, сварочная линия автозавода, автоматизированное управление отопления дома, автономная система управления транспортным средством и т.п.).
Автономные движущиеся роботы. Исполнительные устройства, датчики. Система команд робота. Конструирование робота. Моделирование робота парой: исполнитель команд и устройство управления. Ручное и программное управление роботами.
Пример учебной среды разработки программ управления движущимися роботами. Алгоритмы управления движущимися роботами. Реализация алгоритмов "движение до препятствия", "следование вдоль линии" и т.п.
Анализ алгоритмов действий роботов. Испытание механизма робота, отладка программы управления роботом Влияние ошибок измерений и вычислений на выполнение алгоритмов управления роботом.
Математическое моделирование
Понятие математической модели. Задачи, решаемые с помощью математического (компьютерного) моделирования. Отличие математической модели от натурной модели и от словесного (литературного) описания объекта. Использование компьютеров при работе с математическими моделями.
Компьютерные эксперименты.
Примеры использования математических (компьютерных) моделей при решении научно-технических задач. Представление о цикле моделирования: построение математической модели, ее программная реализация, проверка на простых примерах (тестирование), проведение компьютерного эксперимента, анализ его результатов, уточнение модели.
Дата добавления: 2019-08-30; просмотров: 1682; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!