ВОПРОСЫ ПО ТЕОРИИ АЛГОРИТМОВ
.doc-
РАССМОТРЕНО
на заседании ЦМК
«Программное обеспечение информационных технологий»
Протокол от «21» ноября 2012 г. №3
_____________В. А. Мирошниченко
УТВЕРЖДАЮ
Зам. Директора по УР
________________Л. В. Гурьян
«__» ______________2012 г.
ПЕРЕЧЕНЬ ВОПРОСОВ ДЛЯ ПОДГОТОВКИ К ЭКЗАМЕНУ ПО ДИСЦИПЛИНЕ
“ТЕОРИЯ АЛГОРИТМОВ”
3 семестр
230115 Программирование в компьютерных системах (базовый уровень и повышенный уровень)
-
Основные понятия алгоритмизации. Алгоритм. Исполнитель.
-
Свойства алгоритма.
-
Основные правила написания алгоритма.
-
Способы описания алгоритмов. Алгоритм на естественном языке.
-
Способы описания алгоритмов. Графическое описание алгоритма. Блок-схема.
-
Способы описания алгоритмов. Псевдокод.
-
Трассировочная таблица.
-
Блок-схема. Блок вычислений. Логический блок. Блок ввода - вывода данных. Блок начало-конец. Соединитель.
-
Разновидности алгоритмов. Их особенности.
-
Базовые алгоритмические конструкции. Следование. Блок-схема. Псевдокод. Пример.
-
Базовые алгоритмические конструкции. Ветвление. Разновидности ветвлений.
-
Базовые алгоритмические конструкции. Ветвление. Разновидности ветвлений. Алгоритмическая конструкция «Неполное ветвление». Блок-схема. Псевдокод. Пример.
-
Базовые алгоритмические конструкции. Ветвление. Разновидности ветвлений. Алгоритмическая конструкция «Полное ветвление». Блок-схема. Псевдокод. Пример.
-
Базовые алгоритмические конструкции. Ветвление. Разновидности ветвлений. Алгоритмическая конструкция «Выбор». Блок-схема. Псевдокод. Пример.
-
Базовые алгоритмические конструкции. Ветвление. Разновидности ветвлений. Алгоритмическая конструкция «Выбор - иначе». Блок-схема. Псевдокод. Пример.
-
Базовые алгоритмические конструкции. Цикл. Цикл с постусловием. Блок-схема. Псевдокод. Пример.
-
Базовые алгоритмические конструкции. Цикл. Цикл с предусловием. Блок-схема. Псевдокод. Пример.
-
Базовые алгоритмические конструкции. Цикл. Цикл с параметром. Блок-схема. Псевдокод. Пример.
-
Алгоритмическая конструкция «Вложенные циклы».
-
Простые и структурированные данные.
-
Понятие последовательности.
-
Алгоритмы обработки простых данных. Примеры.
-
Алгоритм вычисления значения функции от заданного аргумента. Блок-схема. Псевдокод.
-
Алгоритм табулирования функции, т.е. вычисления таблицы ее значений на заданном интервале с заданным шагом. Блок-схема. Псевдокод.
-
Алгоритм нахождения цифр в заданном натуральном числе. Блок-схема. Псевдокод.
-
Алгоритм вычисления факториала числа. Блок-схема. Псевдокод.
-
Алгоритм нахождения частного и остатка от деления двух заданных целых чисел. Блок-схема. Псевдокод.
-
Алгоритм Евклида — нахождения наибольшего общего делителя двух натуральных чисел НОД(а,в).Блок-схема. Псевдокод.
-
Алгоритм возведения в целую степень заданного натурального числа. Блок-схема. Псевдокод.
-
Алгоритм вычисления суммы n слагаемых ряда: 1+х+х2+х3+...+ хn .Блок-схема. Псевдокод.
-
Алгоритмы обработки последовательностей. Примеры.
-
Алгоритм подсчета в последовательности суммы положительных четных элементов. Блок-схема. Псевдокод.
-
Понятие массива данных. Алгоритмы обработки массивов. Примеры.
-
Понятие одномерного и двумерного массивов. Особенности обработки одномерных и многомерных массивов.
-
Алгоритм нахождения максимального (минимального элемента) в одномерном массиве. Блок-схема. Псевдокод.
-
Алгоритм замены элементов одномерном массиве. Пример. Блок-схема. Псевдокод.
-
Алгоритм перестановки элементов в одномерном массиве. Пример. Блок-схема. Псевдокод.
-
Алгоритм вставки одного элемента в одномерный массив. Пример. Блок-схема. Псевдокод.
-
Алгоритм вставки нескольких элементов в одномерный массив. Пример. Блок-схема. Псевдокод.
-
Алгоритм удаления одного элемента из одномерного массива. Пример. Блок-схема. Псевдокод.
-
Алгоритм удаления нескольких элементов из одномерного массива. Пример. Блок-схема. Псевдокод.
-
Алгоритм нахождения в двумерном массиве суммы положительных элементов. Блок-схема. Псевдокод.
-
Алгоритм нахождения максимальных элементов строк двумерного массива. Блок-схема. Псевдокод.
-
Алгоритм перестановки строки и столбца двумерного массива. Пример. Блок-схема. Псевдокод.
-
Понятие сортировки. Признаки сортировки. Алгоритмы сортировки.
-
Сортировка. Алгоритм сортировки обменом. Блок-схема. Пример.
-
Сортировка. Алгоритм сортировки вставкой. Блок-схема. Пример.
-
Сортировка. Алгоритм сортировки выбором. Блок-схема. Пример.
-
Поиск в массиве. Линейный поиск. Блок-схема. Пример.
-
Поиск в упорядоченном массиве. Бинарный поиск. Блок-схема. Пример.
-
Понятие рекурсии. Рекурсивные алгоритмы. Примеры.
-
Свойства рекурсивных алгоритмов. Примеры.
-
Рекурсивный алгоритм вычисления факториала. Блок-схема. Псевдокод.
-
Схема рекурсивных вызовов алгоритма вычисления 6!
-
Понятие правильности алгоритма. Способы проверки правильности алгоритма.
-
Понятие эффективности алгоритма. Сложность алгоритма.
-
Пространственная и временная сложность алгоритма.
-
Методы оценки сложности алгоритма.
-
Порядок сложности алгоритма. О-запись. Виды О-функций.
-
Правила вычисления сложности алгоритмов. Примеры.
-
Оценка сложности циклических алгоритмов. Примеры.
-
Оценка сложности рекурсивных алгоритмов. Примеры.
-
Сравнительная характеристика порядков сложности алгоритмов сортировки.
-
Оценка сложности алгоритма бинарного поиска.
-
Анализ алгоритмов. Способы понижения сложности алгоритмов.
-
Оценка сложности алгоритма вычисления значения функции от заданного аргумента. Псевдокод. Вычисление порядка сложности.
-
Оценка сложности алгоритма возведения в целую степень заданного натурального числа. Псевдокод. Вычисление порядка сложности.
-
Оценка сложности алгоритма табулирования функции, т.е. вычисления таблицы ее значений на заданном интервале с заданным шагом. Псевдокод. Вычисление порядка сложности.
-
Оценка сложности алгоритма нахождения цифр в заданном натуральном числе. Псевдокод. Вычисление порядка сложности.
-
Оценка сложности алгоритма вычисления суммы n слагаемых ряда: 1+х+х2+х3+...+ хn Псевдокод. Вычисление порядка сложности.
-
Оценка сложности алгоритма вычисления факториала числа. Псевдокод. Вычисление порядка сложности.
-
Оценка сложности алгоритма Евклида — нахождения наибольшего общего делителя двух натуральных чисел НОД(а,в). Псевдокод. Вычисление порядка сложности.
-
Оценка сложности алгоритма подсчета в последовательности суммы положительных четных элементов. Псевдокод. Вычисление порядка сложности.
-
Оценка сложности алгоритма нахождения максимального (минимального элемента) в одномерном массиве. Псевдокод. Вычисление порядка сложности.
-
Оценка сложности алгоритма замены в элементов одномерном массиве. Псевдокод. Вычисление порядка сложности.
-
Оценка сложности алгоритма перестановки элементов в одномерном массиве. Псевдокод. Вычисление порядка сложности.
-
Оценка сложности алгоритма удаления одного элемента из одномерного массива. Псевдокод. Вычисление порядка сложности.
-
Оценка сложности алгоритма вставки одного элемента в одномерный массив. Псевдокод. Вычисление порядка сложности.
-
Оценка сложности алгоритма вставки нескольких элементов в одномерный массив. Псевдокод. Вычисление порядка сложности.
-
Оценка сложности алгоритма удаления нескольких элементов из одномерного массива. Псевдокод. Вычисление порядка сложности.
-
Оценка сложности алгоритма нахождения в двумерном массиве суммы положительных элементов. Псевдокод. Вычисление порядка сложности.
-
Оценка сложности алгоритма нахождения максимальных элементов строк двумерного массива. Псевдокод. Вычисление порядка сложности.
Составил преподаватель Бабикова Т. М.
Литература
1 Основная
-
Гринченков Д.В. Математическая логика и теория алгоритмов для программистов: учебное пособие/ Д.В. Гринченков, С.И. Потоцкий. – М.: КНОРУС, 2010. – 208 с.
-
Игошин В.И. Математическая логика и теория алгоритмов. М.: Издательский центр «Академия»,2008.
-
Кнут Дональд Э. Искусство программирования. В 3-х томах. Пер. с англ./ Дональд Э. Кнут. – 3-е изд. – М.: Вильямс, 2006.-Т.1.: Основные алгоритмы. - 720 с.
-
Кнут Дональд Э. Искусство программирования. В 3-х томах. Пер. с англ./ Дональд Э. Кнут. – 3-е изд. – М.: Вильямс, 2007.-Т.2.: Полученные алгоритмы. - 832 с.
-
Кнут Дональд Э. Искусство программирования. В 3-х томах. Пер. с англ./ Дональд Э. Кнут. – 3-е изд. – М.: Вильямс, 2007.-Т.3.: Сортировка и поиск. - 824 с.
-
Крупский В.Н., Плиско В.Е. Теория алгоритмов: учебное пособие. – М.: Издательский центр «Академия»,2009. - 208 с.
-
Крупский В.Н. Введение в сложность вычислений. – М.: Факториал Пресс, 2006.
2 Дополнительная
-
Вирт Н. Алгоритмы и структуры данных. - М.: Мир, 1989. – 360 с.
-
Хусаинов Б.С. Структуры и алгоритмы обработки данных. Примеры на языке Си: учеб. пособие. - Финансы и статистика, 2004. – 464 с.