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