Наименование разделов и тем
|
Содержание учебного материала, лабораторные и практические работы, самостоятельная работа обучающихся
|
Объем часов
|
Уровень освоения
|
1
|
2
|
3
|
4
|
Раздел 1. Анализ и разработка алгоритмов
|
Тема 1.1.
Основы анализа алгоритмов
|
Понятие вычислительного процесса, как дискретной последовательности состояний памяти вычислителя. Функции перехода. Представление о программе как о преобразователе, задающем семейство исполнений (процессов преобразования входных данных в выходные), управляемом входными данными.
Размер задачи как характеристика объема входных данных. Параметры, влияющие на размер задачи. Временная и емкостная сложность программы как функции размера задачи. Верхняя, нижняя и средняя оценки. Асимптотическая оценка, как поведение "в общем случае". О-нотация.
Классы вычислительной сложности алгоритмов: примеры задач, допускающих решение за логарифмическое, линейное, квадратичное, полиномиальное, экспоненциальное время. Нижние и верхние оценки для некоторых классов задач (генерация перестановок, поиск, сортировка).
|
2
|
1, 2
|
Самостоятельная работа обучающихся
|
4
|
3
|
Решение задач на циклы и работу с линейными массивами
|
2
|
2
|
Тема 1.2.
Анализ рекурсивных алгоритмов
|
Рекурсия как общий метод сведения задачи к самой себе. Примеры рекурсивных формул, данных, алгоритмов. Правила задания рекурсии: рекурсивный переход, условия выхода. Преобразование хвостовой рекурсии в итерацию (простой цикл). Ветвящаяся рекурсия (на примере алгоритмов, строящих древовидные процессы решений).
Рекурсивное определение чисел Фибоначчи. Факториал. Рекурсивное и итеративное вычисление факториала. Характер роста факториала как функции от n. Пример решения задачи о Ханойских башнях.
Практические приемы оценки вычислительной сложности алгоритмов:
изучение структуры и глубины циклов и рекурсии в программе;
формальный анализ входных данных и количества операций.
|
2
|
1, 2
|
Решение задач на работу с функциями, рекурсивные функции
|
2
|
2
|
Лабораторная работа № 1.1. Простые числа: реализация двумя способами (по определению и решето Эратосфена)
|
2
|
3
|
Самостоятельная работа обучающихся
|
4
|
Тема 1.3.
Стиль программирования
|
Понятие стиля программирования. Особенности программирования на Си
|
2
|
1, 2
|
Самостоятельная работа обучающихся. Расчетно-графическая работа №1
|
6
|
3
|
Лабораторная работа № 1.2. Треугольник Паскаля. Вычисление коэффициентов бинома Ньютона по формуле с помощью функции вычисления факториала
|
2
|
3
|
Раздел 2. Системы счисления и представление числовых данных
|
Тема 2.1.
Перевод целых чисел
|
Запись чисел цифрами и числовые значения. С.с. как система правил записи чисел. Правила записи значений целых и действительных чисел в позиционных с.с. по основанию b (b-с.с.).
Функции перевода "число-запись" и "запись-число" и алгоритмы их вычисления для произвольной b-с.с. Вычисления по схеме Горнера с минимальным числом операций.
Алгоритмы перевода целых чисел из одной b-с.с. в другую:
из произвольной b-c.с. в 10-с.с.; из 10-с.с. в произвольную b-с.с.;
из произвольной b1-с.с. в произвольную b2-с.с.
|
2
|
1.2
|
Тема 2.2.
Перевод дробных чисел
|
Правила записи значений действительных чисел в позиционных с.с. по основанию b (b-с.с.).
Алгоритмы перевода дробных частей чисел из одной b-с.с. в другую:
из произвольной b-c.с. в 10-с.с.; из 10-с.с. в произвольную b-с.с.;
из произвольной b1-с.с. в произвольную b2-с.с.
Кратные с.с. Приемы использования кратных с.с. для ускорения перевода чисел между произвольными b-с.с.
Универсальные алгоритмы вычисления арифметических операций для произвольных b-с.с.
Достаточное условие конечности представления рациональной дроби в произвольной b-с.с.
Понятие символьных вычислений. Формальное определение вычислений как преобразование цепочек символов по заданным правилам (на примере определения арифметических операций таблицами значений). Базовые операции символьных вычислений (выборка, идентификация, сравнение и подстановка
|
4
|
1.2
|
Решение задач на перевод чисел из одной с.с. в другую.
|
2
|
2
|
Самостоятельная работа обучающихся. Расчетно-графическая работа № 2
|
4
|
3
|
Лабораторная работа № 1.3. Перевод из одной системы счисления в другую
|
4
|
3
|
Тема 2.3.
Представление целых чисел в разрядной сетке
|
Модель машинной памяти как однородного линейно-адресуемого массива ячеек фиксированной разрядности. Влияние разрядности шин адреса и данных на размеры машинного слова и адресуемой памяти.
Понятие разрядной сетки; ее модель (линейно индексируемый массив цифр) и характеризующие параметры (разрядность и формат).
Особенности представления чисел и арифметики в конечной разрядной сетке: ограничения ширины представимого интервала чисел; ограничения точности представления (для действительных чисел).
Модель целых чисел конечной разрядности: вычеты (классы чисел, сравнимых по модулю). Арифметика вычетов. Понятие переполнения.
Модель беззнаковых целых чисел конечной разрядности. Формулы для min и max.
Модель целых чисел со знаком. Знаковый разряд. Формулы для min и max. Несимметричность представляемого диапазона. Проблемы выбора представления для отрицательного диапазона (сужение интервала, два нуля, усложнение операций). Правила представления чисел и арифметика в дополнительном коде.
Единообразие правил знаковой и беззнаковой арифметики. Примеры, иллюстрирующие зависимость результатов вычислений только от способа интерпретации представлений.
|
2
|
1, 2
|
Тема 2.4.
Представление действительных чисел в разрядной сетке
|
Модель действительных чисел конечной точности: интервалы (классы чисел, сравнимых с заданной точностью). Арифметика интервалов. Понятие погрешности (потери точности). Накопление погрешности при вычислениях.
Модель вещественной арифметики с фиксированной точкой (равномерная точность представления). Формулы для max и точности. Арифметика с фиксированной точкой: сведение к целочисленной арифметике со сдвигом. Округление, как способ повышения точности.
Модель вещественной арифметики с плавающей точкой (неравномерная точность представления).
Экспоненциальное (нормализованное, с плавающей точкой) представление вещественного числа. Мантисса и порядок, их вид. Нормализация. Особенности арифметики с плавающей точкой: денормализация аргументов при сложении; нормализация результата; расширение разрядной сетки при денормализации и округлении.
Представление вещественного числа в нормализованной форме как пары целых. Разрядность мантиссы и порядка. Формулы для max, E1 (минимальное ненулевое число, абсолютная точность), E2 (относительная точность).
Источники погрешности при арифметике с плавающей точкой:
бесконечность представления числа в данной с.с.; потеря точности при денормализации меньшего аргумента; потеря точности при округлении;
потеря точности при записи результата в память; потеря точности при переводе в с.с., используемую для вывода.
Параметры, характеризующие модели представления чисел в используемых вычислительных средствах. Характеристики числовых типов в Паскале и Си для процессоров Intel (integer, word, real, float, double и др.)
|
2
|
1, 2
|
Решение задач на представление чисел в памяти машины, доп. код, нормализованное представление, вычисление погрешности.
|
2
|
2
|
Самостоятельная работа обучающихся. Расчетно-графическая работа №3
|
4
|
3
|
|
Контрольная работа 1.1
|
2
|
3
|
Раздел 3. Сортировка и поиск
|
Тема 3.1.
Элементы комбинаторики
|
Перестановки набора. Подсчет числа перестановок.
Наборы, упорядоченные заданной операцией порядкового сравнения. Перестановки. Инверсии. Число инверсий, как мера сложности упорядочения набора. Таблицы инверсий. Алгоритм восстановления перестановки по таблице инверсий. Таблица инверсий как число в особой с.с. Итерационный алгоритм генерации всех таблиц инверсий.
Алгоритмы перебора перестановок: рекурсивный, итерационный через перебор таблиц инверсий, итерационный (Дейкстры) с лексикографическим упорядочением. Применение итерационного метода к задаче перебора всех подмножеств из заданного набора.
|
2
|
1, 2
|
Решение задач на перестановки, на работу с массивами и строками
|
2
|
2
|
Лабораторная работа № 1.4. Реализация одного из алгоритмов генерации перестановок на выбор преподавателя
|
2
|
3
|
Тема 3.2.
Поиск
|
Постановка задач поиска / сортировки записей (П/С) в произвольном наборе данных. Формализация: ключи как абстракции записей; требования к ключам (сравнимость по заданной порядковой функции); внешняя и внутренняя постановка задачи П/С (при не/доступности всего набора). Простые и мульти-ключи. Сведение лексикографических (словарных) П/С по мультиключу к П/С по простому ключу с помощью функции сравнения.
Методы простого поиска в массиве: линейный поиск, бинарный поиск. Оценки сложности (min, max, ave).
Методы поиска подстроки в строке: алгоритм прямого перебора, алгоритм Бойера-Мура. Оценки сложности в среднем.
|
2
|
1, 2
|
Решение задач на поиск в массиве и строке
|
2
|
2
|
Самостоятельная работа обучающихся. Расчетно-графическая работа № 4
|
4
|
3
|
Лабораторная работа № 1.5. Реализация алгоритма Бойера-Мура (поиск подстроки в строке)
|
2
|
Тема 3.3.
Простые сортировки
|
Задача сортировки массива. Простые сортировки: вставка, выбор, обмен (пузырёк, шейкер). Сортировка подсчётом.
Оценки сложности (min, max, ave) с примерами входных данных. Нижняя оценка сложности сортировки с помощью попарных сравнений.
|
2
|
1, 2
|
|
Лабораторная работа № 1.6. Реализация алгоритмов двух простых сортировок на выбор преподавателя
|
2
|
3
|
Тема 3.4.
Улучшенные сортировки
|
Улучшенные сортировки: сортировка Шелла, пирамидальная сортировка.
|
2
|
1, 2
|
Метод декомпозиции: разделяй и властвуй. Быстрая сортировка, сортировка слиянием.
|
2
|
Решение задач на элементы сортировки массива
|
2
|
2
|
Лабораторная работа № 1.7. Реализация одного из алгоритмов улучшенных сортировок на выбор преподавателя
|
4
|
3
|
Самостоятельная работа обучающихся. Расчетно-графическая работа №5
|
6
|
|
Контрольная работа 1.2.
|
2
|
Тема 3.5.
Внешние сортировки
|
Простое двухпутевое слияние. Сортировка файлов.
Другие методы сортировки: карманная, поразрядная. Анализ эффективности рассмотренных методов сортировки
|
2
|
1, 2
|
Решение задач на работу с файлами
|
2
|
2
|
Самостоятельная работа обучающихся
|
4
|
3
|
Раздел 4. Начальные сведения о транслирующих системах
|
Тема 4.1.
Трансляция
|
Компиляторы и интерпретаторы.
Основные этапы трансляции (лексический, синтаксический, семантический анализы, кодогенерация, редактирование связей, загрузка)
|
2
|
1
|
Решение задач на использование структур.
|
2
|
2
|
Самостоятельная работа обучающихся
|
4
|
3
|
|
Контрольная работа 1.3.
|
4
|
|
Дифференцированный зачет
|
4
|
Тема 4.2.
Оперативная память
|
Структура оперативной памяти на примере 16-разрядной машины. Понятие адреса (сегмент, смещение). Единицы измерения памяти. Основные разделы памяти. Способы распределения памяти (не включая динамику): статический, автоматический.
Статическое и динамическое распределение памяти: отличия по способу описания переменных, времени создания, способу и дисциплине доступа.
Динамическая память (куча). Правила работы с динамической памятью, основные операции, языковые средства доступа.
Способы доступа к данным: прямой, последовательный, индексная и косвенная разновидности.
Буферизация как прием совмещения различных способов доступа к данным, примеры ее использования.
Указатели, как средство организации данных с динамической структурой; средства работы с ними в Си.
Использование приведений указательных типов для описания неоднородных структур. Указатели и массивы.
|
4
|
1, 2
|
Самостоятельная работа обучающихся.
|
4
|
3
|
|
Лабораторная работа № 2.1. Сортировка файлов
|
2
|
|
Раздел 5. Списки
|
|
|
Тема 5.1.
Динамические списки
|
Списки. Односвязные, двусвязные, циклические, иерархические. Способы реализации (статика и динамика).
|
2
|
1, 2
|
Решение задач на создание, обход списков. Способы поиска, вставки и удаления элементов в списки.
|
2
|
2
|
Лабораторная работа № 2.2. Создание упорядоченного списка
|
2
|
3
|
Тема 5.2.
АСД на основе линейных списков
|
Абстрактные структуры данных: стек, очередь, реализация на массивах и списках. Перевод выражения из инфиксной формы записи в постфиксную и вычисление на стеке
|
2
|
1, 2
|
Лабораторная работа № 2.3. Перевод выражения из инфиксной формы записи в постфиксную
|
2
|
3
|
Самостоятельная работа обучающихся. Расчетно-графическая работа № 6
|
4
|
Раздел 6. Алгоритмы на деревьях
|
Тема 6.1.
Графы, деревья, основные определения
|
Граф как наиболее общая модель данных последовательного доступа. Пути и маршруты по графу. Определения различных типов графов: (не)ориентированного, (а)циклического, мультиграфа. Представление графа, как отношения на множестве вершин.
Дерево, как частный вид графа. Эквивалентные определения дерева характеристическими свойствами. Терминология для деревьев: отец, сын, корень, лист, глубина и др.
Классические типы деревьев: корневые, бинарные, упорядоченные, уравновешенные.
Представление полного дерева на массиве.
|
2
|
1, 2
|
Решение задач на деревья
|
2
|
2
|
Самостоятельная работа обучающихся
|
4
|
3
|
Тема 6.2.
Деревья поиска
|
Обходы деревьев (инфиксный, префиксный, постфиксный). Представление деревьев (левое/правое скобочное представление, список прямых предков).
Деревья двоичного поиска. Алгоритмы построения и поиска. Создание орфографического словаря по заданному набору слов.
Сбалансированные деревья. Алгоритмы добавления и удаления вершин. Сравнение эффективности алгоритмов поиска на деревьях с известными алгоритмами на массивах
|
2
|
1, 2
|
Самостоятельная работа обучающихся. Расчетно-графическая работа № 7
|
4
|
3
|
Решение задач на списки и деревья
|
2
|
2
|
Лабораторная работа № 2.4. Построение дерева двоичного поиска
|
2
|
3
|
|
Контрольная работа 2.1
|
2
|
3
|
Раздел 7. Алгоритмы на графах
|
Тема 7.1.
Представление графов
|
Модели представления графа в памяти машины. Матрицы смежности, инцидентности. Динамическая структура со списками дуг. Табличное представление.
Постановка задачи топологической сортировки. Примеры решения задачи на различных структурах данных (матрица смежности, иерархические списки)
|
2
|
1, 2
|
Решение задач на получение различных представлений графа
|
2
|
2
|
Лабораторная работа № 2.5. Топологическая сортировка, реализация на матрице смежности и на иерархических списках
|
4
|
3
|
Тема 7.2.
Пути в графе
|
Нахождение кратчайших путей в графе: алгоритмы Дейкстры (жадный) и Флойда (динамическое программирование).
Транзитивное замыкание графа.
|
2
|
1, 2
|
|
Самостоятельная работа обучающихся
|
4
|
3
|
Тема7.3.
Обходы графа
|
Метод поиска в глубину. Построение глубинного остовного дерева для ориентированных и неориентированных графов. Задача поиска компонент связности, топологическая сортировка.
Обход графа в ширину. Построение ширинного остовного дерева. Поиск кратчайшего пути в лабиринте, метод волны.
|
2
|
1, 2
|
Самостоятельная работа обучающихся
|
4
|
3
|
Лабораторная работа № 2.6. Поиск кратчайшего пути в лабиринте
|
4
|
Тема 7.4.
Остовные деревья
|
Остовные деревья. Построение минимального каркаса (алгоритмы Краскала, Прима). Анализ эффективности.
|
2
|
1, 2
|
Лабораторная работа № 2.7. Построение минимального каркаса графа
|
4
|
3
|
Тема 7.5.
Циклы в графе, раскраска
|
Эйлеровы циклы и эйлеровы графы. Задача о Кёнигсбергских мостах. Признаки, что граф – эйлеров. Алгоритмы нахождения эйлерова цикла (Флёри и с помощью стека). Задача о «рыбе».
Гамильтоновы графы. Построение гамильтонова цикла методом полного перебора. Задача коммивояжера, использование генерации всех перестановок.
Раскраска графов. Понятия правильной и оптимальной раскраски. Хроматическое число.
Планарные графы. Задача раскраски карты минимальным количеством красок. Задачи, сводимые к раскраске (составление расписания, распределение ресурсов, экономия памяти).
|
4
|
1, 2
|
Самостоятельная работа обучающихся. Расчетно-графическая работа № 8
|
6
|
3
|
Раздел 8. Задачи полного перебора
|
Тема 8.1.
Алгоритмы с возвратом
|
Алгоритмы перебора на абстрактных динамических структурах. Способы перебора. Итерационный, полный, с отсечением. Примеры.
Классические задачи на графах: транзитивное замыкание, задача коммивояжера (размеченные дуги), раскраска графа (размеченные вершины). Задачи, сводимые к данным алгоритмам.
Алгоритмы с возвратом — обход шахматной доски конем. Задача о ферзях. Классические задачи с отсечением (метод ветвей и границ): задача о рюкзаке, об устойчивых браках.
Анализ эффективности алгоритмов перебора: экспоненциальная оценка временной сложности.
|
2
|
1, 2
|
Самостоятельная работа обучающихся
|
4
|
3
|
Тема 8.2.
Динамическое программирование
|
Динамическое программирование как решение задач с помощью табличной техники.
Задачи о рюкзаке, о преобразовании строки, о расстановке скобок в выражении, о делимости, о гангстерах.
|
2
|
1, 2
|
Самостоятельная работа обучающихся
|
4
|
3
|
|
Контрольная работа 2.2.
|
2
|
|
Дифференцированный зачёт
|
2
|
|
Всего:
|
216
|
|
