- Понятие информации. Информационные процессы и системы. Информационные ресурсы и технологии.
- Структура информатики и ее связь с другими науками.
- Информация. Понятие обработки информации: канал связи, сигнал, дискретные и непрерывные сообщения. Количество информации: энтропийный и объемный подходы, энтропия источника сообщений.
- Информация. Как подсчитать количество информации, приходящейся на один символ, в заданном тексте?
- Представление информации в цифровых автоматах. Понятие кодирования. Алфавит. Позиционные системы счисления. Преобразование целых неотрицательных чисел из одной системы счисления в другую.
- Представление информации в цифровых автоматах. Преобразование правильных дробей из одной системы счисления в другую.
- Арифметические операции в позиционных системах счисления: сложение, вычитание, умножение и деление. Примеры.
- Системы счисления по основанию 2, 8, 10, 16. Представление целых неотрицательных и отрицательных чисел в ЭВМ. Прямой, обратный и дополнительный коды. Примеры прямого, обратного и дополнительного кодов восьмибитового положительного и отрицательного целого числа. Запишите в десятичной с.с. целое число по его дополнительному коду.
- Двоично-десятичная система счисления. Преобразование целых неотрицательных чисел из десятичной системы счисления в двоично-десятичную систему и обратно.
- Представление вещественных чисел в ЭВМ. Двоичный код с избытком. Арифметические операции над нормализованными числами. Понятие погрешности их представления.
- Логические основы построения цифровых автоматов. Двоичные логические элементы. Логические сложение, умножение, инверсия, штрих Шеффера, функция Пирса, сложение по модулю 2, импликация, исключающее ИЛИ, исключающее , разность. Таблицы истинности, условные обозначения и характеристики основных логических элементов.
- Логические основы построения цифровых автоматов. Законы булевой алгебры и следствия из них. Таблицы истинности. Примеры.
- Логические основы построения цифровых автоматов. Булевы
формулы и функции. Количество булевых функций от n переменных. Существенные и фиктивные переменные. Эквивалентные функции. Двойственные функции. Принцип двойственности.
- Логические основы построения цифровых автоматов. Разложение булевых функций по переменным. Специальные случаи разложения – теоремы Шеннона. Примеры.
- Логические основы построения цифровых автоматов. Определение функционально полной системы функций алгебры логики. Примеры полных систем. Полином Жегалкина. Его построение по таблице истинности и по СДНФ. Теорема Жегалкина.
- Логические основы построения цифровых автоматов. Важнейшие замкнутые классы функций алгебры логики – классы Поста. Перечислите эти классы. Какая система функций алгебры логики называется функционально полной? Приведите примеры полных систем. Теорема о полноте. Представление о результатах Поста.
- Логические основы построения цифровых автоматов. Схемы из функциональных элементов. Структура. Операции. Примеры.
- Логические основы построения цифровых автоматов. Синтез схем из функциональных элементов. Сложность. Функции Шеннона. Асимптотические оценки для базиса из инвертора, конъюнктора и дизъюнктора.
- Логические основы построения цифровых автоматов. Задача синтеза схем из функциональных элементов. Пример схемы для сложения двух двоичных чисел.
- Интуитивное понятие алгоритма. Свойства алгоритма. Исполнитель алгоритма. Средства описания алгоритмов. Известнейшие алгоритмы в истории математики – Евклида и Эратосфена.
- Развитие понятия алгоритма. Понятие процедурного, объектно-ориентированного, распределенного алгоритма, их свойства.
- Понятие о методах разработки алгоритмов: «Разделяй и властвуй», итерация, рекурсия, последовательные приближения, построение обратной задачи, полного перебора, эвристические методы.
- Понятие рекурсивного алгоритма. Рекурсивная процедура. Техническая реализация рекурсии. Сравнение механизмов реализации рекурсии и итерации.
- Основы анализа алгоритмов. Анализ сложности алгоритмов. Временная и емкостная сложность. Верхняя, нижняя и средняя оценки сложности. Примеры.
- Общий алгоритм вида «Разделяй и властвуй». Анализ сложности рекурсивного алгоритма. Примеры.
- Нижняя оценка сложности алгоритма. Сложность задачи. Примеры: сортировки массивов.
- Аналогии между методами построения алгоритмов и методами построения данных. Данные со статической и динамической структурой. Примеры.
- Алгоритм последовательного поиска в в списке. Анализ сложности алгоритма.
- Алгоритм бинарного поиска в в списке. Анализ сложности алгоритма.
- Алгоритм интерполяционного поиска в в списке. Анализ сложности алгоритма.
- Данные со статической структурой. Алгоритм сортировки массива вставками. Анализ сложности алгоритма.
- Данные со статической структурой. Алгоритм сортировки массива выбором. Анализ сложности алгоритма.
- Данные со статической структурой. Алгоритм сортировки массива обменом. Анализ сложности алгоритма.
- Данные со статической структурой. Алгоритм сортировки массива слиянием. Анализ сложности алгоритма.
- Данные со статической структурой. Алгоритм быстрой сортировки Хоара. Анализ сложности алгоритма.
- Данные с динамической структурой. Линейные и нелинейные структуры. Рекурсивные данные.
- Данные с динамической структурой. Стек и очередь. Схематическое представление основных операций.
- Данные с динамической структурой. Линейные списки. Схематическое представление основных операций. Сложность основных операций.
- Этапы разработки программ с использованием технологии структурного программирования.
