ПЕРЕЧЕНЬ ВОПРОСОВ ДЛЯ ПОДГОТОВКИ К ЭКЗАМЕНУ ПО ДИСЦИПЛИНЕ
“ТЕОРИЯ АЛГОРИТМОВ”
Семестр
Программное обеспечение вычислительной техники и автоматизированных систем
(базовый уровень и повышенный уровень)
1. Основные понятия алгоритмизации. Алгоритм. Исполнитель.
2. Свойства алгоритма.
3. Основные правила написания алгоритма.
4. Способы описания алгоритмов.Алгоритм на естественном языке.
5. Способы описания алгоритмов. Графическое описание алгоритма. Блок-схема.
6. Способы описания алгоритмов. Псевдокод.
7. Трассировочная таблица.
8. Блок-схема. Блок вычислений. Логический блок. Блок ввода - вывода данных. Блок начало-конец. Соединитель.
9. Разновидности алгоритмов. Их особенности.
10. Базовые алгоритмические конструкции. Следование. Блок-схема. Псевдокод. Пример.
11. Базовые алгоритмические конструкции.Ветвление. Разновидности ветвлений.
12. Базовые алгоритмические конструкции.Ветвление. Разновидности ветвлений. Алгоритмическая конструкция «Неполное ветвление». Блок-схема. Псевдокод. Пример.
13. Базовые алгоритмические конструкции.Ветвление. Разновидности ветвлений. Алгоритмическая конструкция «Полное ветвление». Блок-схема. Псевдокод. Пример.
14. Базовые алгоритмические конструкции.Ветвление. Разновидности ветвлений. Алгоритмическая конструкция «Выбор». Блок-схема. Псевдокод. Пример.
15. Базовые алгоритмические конструкции.Ветвление. Разновидности ветвлений. Алгоритмическая конструкция «Выбор-иначе». Блок-схема. Псевдокод. Пример.
16. Базовые алгоритмические конструкции.Цикл. Цикл с постусловием.Блок-схема. Псевдокод. Пример.
17. Базовые алгоритмические конструкции.Цикл.Цикл с предусловием.Блок-схема. Псевдокод. Пример.
18. Базовые алгоритмические конструкции.Цикл.Цикл с параметром.Блок-схема. Псевдокод. Пример.
19. Алгоритмическая конструкция «Вложенные циклы».
20. Простые и структурированные данные.
21. Понятие последовательности.
22. Алгоритмы обработки простых данных. Примеры.
23. Алгоритм вычисления значения функции от заданного аргумента. Блок-схема. Псевдокод.
24. Алгоритм табулирования функции, т.е. вычисления таблицы ее значений на заданном интервале с заданным шагом. Блок-схема. Псевдокод.
25. Алгоритм нахождения цифр в заданном натуральном числе. Блок-схема. Псевдокод.
26. Алгоритм вычисления факториала числа. Блок-схема. Псевдокод.
27. Алгоритм нахождения частного и остатка от деления двух заданных целых чисел. Блок-схема. Псевдокод.
28. Алгоритм Евклида — нахождения наибольшего общего делителя двух натуральных чисел (НОД(а,в)).Блок-схема. Псевдокод.
29. Алгоритм возведения в целую степень заданного натурального числа. Блок-схема. Псевдокод.
30. Алгоритм вычисления суммы n слагаемых ряда: 1+х+х2+х3+...+ хn.Блок-схема. Псевдокод.
31. Алгоритмы обработки последовательностей. Примеры.
32.
33. Алгоритм подсчета в последовательности суммы положительных четных элементов. Блок-схема. Псевдокод.
34. Понятие массива данных. Алгоритмы обработки массивов. Примеры.
35. Понятие одномерного и двумерного массивов. Особенности обработки одномерных и многомерных массивов.
36. Алгоритм нахождения максимального (минимального элемента) в одномерном массиве. Блок-схема. Псевдокод.
37. Алгоритм замены в элементов одномерном массиве. Пример. Блок-схема. Псевдокод.
38. Алгоритм перестановки элементов в одномерном массиве. Пример. Блок-схема. Псевдокод.
39. Алгоритм вставки одного элемента в одномерный массив. Пример. Блок-схема. Псевдокод.
40. Алгоритм вставки нескольких элементов в одномерный массив. Пример. Блок-схема. Псевдокод.
41. Алгоритм удаления одного элемента из одномерного массива. Пример. Блок-схема. Псевдокод.
42. Алгоритм удаления нескольких элементов из одномерного массива. Пример. Блок-схема. Псевдокод.
43. Алгоритм нахождения в двумерном массиве суммы положительных элементов. Блок-схема. Псевдокод.
44. Алгоритм нахождения максимальных элементов строк двумерного массива. Блок-схема. Псевдокод.
45. Алгоритм перестановки строки и столбца двумерного массива. Пример. Блок-схема. Псевдокод.
46. Понятие сортировки. Признаки сортировки. Алгоритмы сортировки.
47.
48. Сортировка. Алгоритм сортировки обменом. Блок-схема. Пример.
49. Сортировка. Алгоритм сортировки вставкой. Блок-схема. Пример.
50. Сортировка. Алгоритм сортировки выбором. Блок-схема. Пример.
51. Поиск в массиве. Линейный поиск. Блок-схема. Пример.
52. Поиск в упорядоченном массиве. Бинарный поиск. Блок-схема. Пример.
53. Понятие рекурсии. Рекурсивные алгоритмы. Примеры.
54. Свойства рекурсивных алгоритмов. Примеры.
55. Рекурсивный алгоритм вычисления факториала. Блок-схема. Псевдокод.
56. Схема рекурсивных вызовов алгоритма вычисления 6!
57. Понятие правильности алгоритма. Способы проверки правильности алгоритма.
58. Понятие эффективности алгоритма. Сложность алгоритма.
59. Пространственная и временная сложность алгоритма.
60. Методы оценки сложности алгоритма.
61. Порядок сложности алгоритма. О-запись. Виды О-функций.
62. Правила вычисления сложности алгоритмов. Примеры.
63. Оценка сложности циклических алгоритмов. Примеры.
64. Оценка сложности рекурсивных алгоритмов. Примеры.
65. Сравнительная характеристика порядков сложности алгоритмов сортировки.
66. Оценка сложности алгоритма бинарного поиска.
67. Анализ алгоритмов. Способы понижения сложности алгоритмов.
Составил преподаватель Бабикова Т. М.
Литература
Основная
1. Подбельский В.В. Язык Си++: Учеб.пособие. – 5-е изд.-М.: Финансы и статистика, 2004. – 560 с.: ил.
2. С/С++. Структурное программирование: Практикум/ Т.А. Павловская, Ю.А.Щупак. – СПб.: Питер, 2004. -239 с.: ил.
3. Страуструп Б. Дизайн и эволюция С++. Пер. с англ. – М.: ДМК Прессб 2000 – 448 с.: ил.
4. Язык программирования Си++ /Фридман А.Л./ М.: ИНТУИТ.РУ «Интернетуниверситет Информационных технологий», 2003. – 288 с.
Дополнительная
5. Вирт Н. Алгоритмы и структуры данных. - М.: Мир, 1989. – 360 с., ил.
6. Пирогов В.Ю. Программирование на Visual C++.NET. –СПб.: БХВ-Петербург, 2003. – 800 с.: ил.
7. Сэмюел П. Харбисон, Гай Л.Стил. Язык программирования С. Пер. с англ. – М.: ООО «Бином-Пресс», 2004 г. – 528 с.: ил.
8. Хусаинов Б.С. Структуры и алгоритмы обработки данных. Примеры на языке Си: Учеб.пособие.-Финансы и статистика, 2004. – 464 с.: ил.