Ответы на билеты по предмету: Программирование (Пример)
Содержание
Информация 6
1. Понятие информации. Носители информации. Понятие сообщения. Формы сообщений. 6
2. Понятие сообщения. Передача сообщений. 6
3. Понятие информации. Способы измерения информации. 7
4. Понятие информационного процесса. Виды информационных процессов. 7
5. Понятие кибернетики. Кибернетический подход к управлению. 7
6. Понятие информационных ресурсов, информационных систем. Эволюция информационных технологий. 7
7. Понятие информационных ресурсов, информационных систем. Характеристики современных информационных систем. 9
8. Понятие информационных ресурсов, информационных систем. Классификация информационных систем. 9
Числа в памяти ЭВМ 10
9. Представление целых чисел в памяти ЭВМ. 10
10. Представление вещественных чисел и символьной информации в памяти ЭВМ. 10
11. Представление графики, звука и видео в памяти ЭВМ. 11
Программное обеспечение 11
12. Классификация программного обеспечения ЭВМ. Способы распространения программного обеспечения. 11
13. Жизненный цикл программного обеспечения. Программы с большой и с малой жизнью. 12
14. Этапы проектирования программ по ГОСТ ЕСПД, по Майерсу. Технология макетирования. 13
Языки программирования 14
15. Поколения языков программирования. 14
16. Классификация парадигм программирования 15
Структурное программирование 16
17. Понятие структурного программирования. Принципы структурного программирования. 16
Системы счисления 17
18. Понятие системы счисления. Классификация систем счисления. Характеристика непозиционных систем счисления. 17
19. Понятие систем счисления. Запись чисел в позиционных системах счисления. Алгоритмы перевода целой части между системами счисления с различными основаниями. 17
20. Понятие систем счисления. Запись чисел в позиционных системах счисления. Алгоритмы перевода дробной части между системами счисления с различными основаниями. 18
21. Правила проведения операций сложения и вычитания в позиционных системах счисления. 18
22. Правила проведения операций умножения и деления в позиционных системах счисления. 19
23. Понятие смешанной системы счисления, их назначение. Алгоритмы перевода между смешанными системами счисления. 19
Теория алгоритмов 20
24. Понятие алгоритма. Свойства алгоритмов. 20
25. Понятие исполнителя алгоритма. Точное определение алгоритма. 20
26. Словесная запись алгоритмов. Запись алгоритмов с помощью формул и таблиц. 20
27. Запись алгоритмов с помощью блок-схем. 21
28. Запись алгоритмов с помощью псевдокода. Понятие языка программирования. 22
29. Машина Тьюринга. 22
30. Композиции машин Тьюринга. 23
31. Алгорифмы Маркова. 24
32. Композиции алгорифмов Маркова 24
Решение задач с помощью ЭВМ 24
33. Методика решения задач с помощью ЭВМ. 24
34. Этапы прохождения заданий через ЭВМ. 25
Рекуррентные вычисления и рекурсия 25
35. Понятие рекуррентных вычислений. Правила организации рекуррентных вычислений в программах. 25
36. Понятие рекурсии. Прямой и обратный ход рекурсии. Рекурсивный стек. 26
37. Сравнение рекурсии и итерации. Оценка сложности вычисления n-го числа Фибоначчи рекурсивным и итерационным способами. 26
Алгоритмы построения кривых 28
38. Реализация построения кривой Гильберта 28
39. Реализация построения кривой Серпинского. 29
Задачи с возвратами 31
40. Понятие задачи с возвратами. Реализация задачи о ходе коня. 31
41. Понятие задачи с возвратами. Реализация задачи о 8 ферзях 33
Оценка сложности алгоритмов 34
42. Оценка сложности нерекурсивного алгоритма по управляющему графу. 34
43. Оценка сложности рекурсивных алгоритмов. 35
44. Оценка сложности алгоритмов Expression, Addend и Factor. 35
45. Верхние и нижние оценки сложности алгоритмов. Разрешимые и неразрешимые задачи. Классы сложности алгоритмов P, EXP, NP. 37
Типы данных 37
46. Концепция типа данных 37
47. Понятие типа данных. Классификации типов данных в языках Pascal и С. 38
48. Характеристика типа данных integer языка Pascal. 39
49. Характеристика типа данных real языка Pascal. 39
50. Характеристика типов данных char, boolean языка Pascal. 40
51. Характеристика типов данных перечисление, отрезок, множество языка Pascal. 40
52. Характеристика типов данных «массив» и «запись» языка Pascal. 41
53. Характеристика типа данных «файл» языка Pascal. 42
54. Характеристика типа данных «ссылка» языка Pascal. 43
55. Характеристика скалярных типов данных языка С. 43
56. Характеристика составных типов данных языка С. 43
57. Характеристика ввода/вывода в языке С. 44
Массивы 45
58. Схемы перебора элементов массива. 45
59. Классы задач на массивах. Правила решения задач соответствующих классов. 46
Динамические структуры. 48
60. Понятие списка. Реализация операций со списком. 48
61. Понятие стека. Реализация операций со стеком. 52
62. Понятие очереди. Реализация операций с очередью. 53
63. Понятие дека. Реализация операций с деком. 55
64. Решение задачи о сложении многочленов. 57
Деревья 57
65. Понятие дерева. Способы изображения деревьев. Способы представления деревьев. Обход дерева. 57
66. Реализация алгоритма построения идеально-сбалансированного дерева. Оценка сложности алгоритма. 59
67. Реализация алгоритма поиска по дереву с включением. Оценка сложности алгоритма 59
68. Реализация алгоритма идентификации. 60
69. Реализация алгоритмов удаления вершины дерева, полного удаления дерева. 61
70. Реализация алгоритмов сравнения деревьев, слияния деревьев. 62
71. Понятие АВЛ-дерева (Адельсон-Вельский, Ландис).
Реализация алгоритма включения в АВЛ-дерево 63
72. Реализация удаления из АВЛ-дерева 64
73. Реализация алгоритмов поворотов деревьев 64
74. Понятие красно-чёрного дерева. Реализация алгоритма включения в красно-чёрное дерево 64
75. Понятие красно-чёрного дерева. Реализация алгоритма удаления из красно-чёрного дерево 64
76. Понятие дерева случайного поиска. Реализация алгоритма включения в дерево случайного поиска. 65
77. Понятие дерева случайного поиска. Реализация алгоритма удаления из дерева случайного поиска. 65
78. Понятие В-дерева. Реализация алгоритма вставки в В-дерево 65
79. Понятие В-дерева. Реализация алгоритма удаления из В-дерева 65
Разряженные структуры данных 65
80. Разряженные структуры данных. Последовательные и связные формы хранения. Особые случаи хранения. 65
Сортировки 67
81. Понятие сортировки. Параметры оценки алгоритмов сортировки. Классификация сортировок. 67
82. Характеристики внутренних методов сортировки. Дополнительные факторы, учитываемые при сортировке. 67
83. Реализация алгоритма простых вставок. Оценка сложности алгоритма. 68
84. Реализация алгоритма простого выбора. Оценка сложности алгоритма. 69
85. Реализация алгоритма простого обмена. Оценка сложности алгоритма. 69
86. Реализация алгоритма простого подсчета. Оценка сложности алгоритма. 70
87. Реализация алгоритма бинарных вставок. Оценка сложности алгоритма. 70
88. Реализация алгоритма парного обмена. Оценка сложности алгоритма. 71
89. Реализация алгоритма центрированных вставок. Оценка сложности алгоритма. 71
90. Реализация алгоритма квадратичного выбора. Оценка сложности алгоритма. 72
91. Реализация алгоритма поразрядной сортировки. Оценка сложности алгоритма. 72
92. Реализация алгоритма быстрой сортировки. Оценка сложности алгоритма. 73
93. Реализация алгоритма сортировки Шелла. Оценка сложности алгоритма. 74
94. Реализация алгоритма внешней сортировки. 74
Хеширование 76
95. Хеширование. Рехеширование. 76
Строки и подстроки 77
96. Понятие строки и подстроки. Средства работы со строками в языках Pascal и С. Реализация алгоритма простого поиска подстрок 77
97. Понятие строки и подстроки. Реализация алгоритма Рабина-Карпа [не доделано!]
78
98. Понятие строки и подстроки. Реализация алгоритма Кнута-Морриса-Пратта 78
99. Понятие строки и подстроки. Реализация алгоритма поиска подстрок с помощью построения конечного автомата. 79
100. Понятие строки и подстроки. Реализация алгоритма Бойера-Мура. 80
Перестановки, подмножества, сочетания, разбиения. 81
101. Понятие перестановки, подмножества, сочетания и разбиения. Средства работы с перестановками, подмножествами, сочетаниями и разбиениями. 81
102. Понятие перестановки, подмножества, сочетания и разбиения. Реализация алгоритмов порождения перестановок в лексикографическом порядке, с помощью векторов инверсий, вложенных циклов и в порядке минимального изменения. 83
103. Понятие перестановки, подмножества, сочетания и разбиения. Реализация алгоритмов порождения подмножеств. 86
104. Понятие перестановки, подмножества, сочетания и разбиения. Коды Грея. 86
105. Понятие перестановки, подмножества, сочетания и разбиения. Композиции и разбиения целых чисел и реализация алгоритмов их порождения 88
Тестирование и отладка. 89
106. Понятие тестирования. Тестирование с точки зрения «черного ящика» и «белого ящика». Пошаговое, нисходящее, восходящее тестирование. 89
107. Понятие тестирования. Принципы тестирования. 89
108. Методы ручного тестирования. 90
109. Понятие отладки. Методы отладки. 90
110. Понятие отладки. Принципы отладки. Анализ ошибок 91
Графы 91
111. Понятие графа. Способы изображения графов. Способы представления графов. 91
112. Реализация алгоритмов обхода графа. 94
113. Реализация алгоритма нахождения кратчайшего пути в графе. 94
114. Реализация алгоритма нахождения множества достижимых вершин в графе. 95
115. Реализация алгоритмов добавления вершин и дуг в граф. 96
116. Реализация алгоритмов удаления вершин и дуг из графа. 96
117. Реализация алгоритмов нахождения сильносвязных и двусвязных компонент графа . 97
118. Понятие остовного дерева. Остовное дерево минимальной стоимости и реализация алгоритмов их построения . 97
119. Реализация алгоритма Беллмана-Форда . 97
120. Потоки в сетях . 9
Выдержка из текста
1. Информация и информационные процессы.
a. Понятие информации и ее характеристики
b. Понятие информационных процессов, их характеристики
c. Кибернетический подход к управлению
d. Информационные технологии: понятие, эволюция, классификация
e. Представление информации в памяти ЭВМ: типы, форматы, особенности
2. Программное обеспечение ЭВМ.
a. Отличительные особенности «хороших» программ.
b. Классификация программного обеспечения ЭВМ
c. Жизненный цикл программного обеспечения. Понятие технологии и методики (методологии) программирования.
d. Этапы проектирования программ по ГОСТ ЕСПД
e. Этапы проектирования программ по Майерсу.
f. Программы с большой и малой жизнью
g. Подходы к проектированию программ: поэтапный, технология макетирования.
h. Системы программирования. Характеристики языков программирования. Парадигмы программирования.
i. Структурное программирование
3. Системы счисления (САМОСТОЯТЕЛЬНО – ВСПОМНИТЬ ИЗ КУРСА «ИНФОРМАТИКА»)
a. Понятие системы счисления
b. Запись чисел
c. Перевод чисел из одной системы счисления в другую
d. Операции в различных системах счисления
e. Смешанные системы счисления
4. Введение в теорию алгоритмов (САМОСТОЯТЕЛЬНО ДО МАШИНЫ ТЬЮРИНГА, на занятиях только кратко вспоминают понятие алгоритма и его свойства, а также перечисляют все способы записи алгоритма)
a. Понятие алгоритма
b. Исполнитель алгоритмов
c. Свойства алгоритмов
d. Словесная запись алгоритмов
e. Запись алгоритмов в виде формул и таблиц
f. Блок-схема
g. Псевдокод
h. Запись алгоритма на языке программирования
i. Машина Тьюринга
j. Композиция машин Тьюринга
k. Алгорифмы Маркова
l. Композиция алгорифмов Маркова
5. Методика решения задач на ЭВМ
a. Этапы решения задачи на ЭВМ
b. Этапы прохождения задачи через ЭВМ
c. Последовательное построение алгоритма
d. Рекуррентные вычисления
e. Рекурсия
f. Итерация
g. Алгоритмы с возвратами
6. Оценка сложности алгоритмов
a. Построение управляющего графа программы
b. Оценка сложности по управляющему графу
c. Оценка сложности рекурсивных алгоритмов
d. Классы сложности алгоритмов
e. Разрешимые и неразрешимые задачи
7. Сложные типы данных
a. Понятие сложного типа данных
b. Классификация сложных типов данных
c. Характеристика типа данных
d. Концепция типа данных
8. Задачи на массивах
a. Схемы перебора элементов массива
b. Перебор подмассивов
c. Нелинейные схемы перебора элементов
d. Классификация задач на массивах
9. Списковые структуры данных
a. Статические и динамические переменные
b. Ссылочный тип данных
c. Список
d. Стек
e. Дек
f. Очередь
g. Операции над ссылочными значениями
h. Особые случаи хранения списков
10. Деревья
a. Основные определения на деревьях
b. Способы изображения дерева
c. Способы представления деревьев
d. Обход дерева
e. Удаление вершины/ удаление дерева
f. Слияние деревьев
g. Повороты деревьев
h. Поиск по дереву с включением
i. Идеально-сбалансированное дерево
j. АВЛ-дерево
k. Красно-черное дерево
l. Дерево случайного поиска
m. В-берево
11. Разряженные матрицы
a. Коэффициент слабой заполненности
b. Последовательные формы хранения
c. Связные формы хранения
d. Треугольная матрица
e. Ленточная матрица
12. Сортировка и поиск
a. Понятие сортировки. Параметры оценки сортировки
b. Классификация сортировок
c. Характеристики внутренних сортировок
d. Улучшенные методы сортировок
e. Хеширование
f. Рехеширование
13. Строки и подстроки
a. Средства работы со строками
b. Алгоритм простого поиска подстрок
c. Алгоритм Рабина-Карпа
d. Алгоритм Кнута-Морриса-Пратта
e. Алгоритм поиска подстрок с помощью построения конечного автомата
f. Алгоритм Бойера-Мура
14. Перестановки, подмножества, сочетания и разбиения
a. Средства работы с перестановками, подмножествами, сочетаниями и разбиениями
b. Порождение перестановок в лексикографическом порядке, с помощью векторов инверсий, вложенных циклов и в порядке минимального изменения
c. Алгоритмы порождения подмножеств
d. Коды Грея
e. Композиции и разбиения целых чисел и алгоритмы их порождения
15. Графы
a. Понятие графа. Основные определения на графах
b. Способы изображения графа
c. Способы представления графа
d. Обход графа
e. Добавление вершины/дуги
f. Удаление вершины/дуги
g. Поиск кратчайшего пути в графе
h. Определение множества достижимых вершин в графе
i. Алгоритмы нахождения сильносвязных и двусвязных компонент графа
j. Остовные деревья минимальной стоимости и алгоритмы их построения
k. Алгоритм Беллмана-Форда
l. Потоки в сетях
16. Тестирование и отладка программ
a. Понятие тестирования, отладки
b. Принципы тестирования
c. Тестирование с точки зрения «черного ящика» и «белого ящика». Пошаговое, нисходящее, восходящее тестирование.
d. Методы ручного тестирования.
e. Принципы отладки. Анализ ошибок.
f. Методы отладки
Список использованной литературы
2. Бауэр Ф.Л., Гооз Г. Информатика. Вводный курс: в 2-х т. – М., Мир, 1990. – 336с. и 423с.
3. Брукшир Дж. Введение в компьютерные науки. Общий обзор. – М., Издательский Дом «Вильямс», 2001. – 688с.
4. Лядова Л.Н., Мызникова Б.И., Фролова Н.В. Основы информатики и информационных технологий. – Пермь, Перм. ун-т, 2004. – 328с.
5. Румянцев Д., Монастырский Л. Путь программиста: опыт создания личности программиста. – М., Издательский Дом ИНФРА-М, 2000. – 864с.
6. Семакин И.Г., Залогова Л.А., Русаков С.В., Шестакова Л.В. Информатика. Базовый курс для 7-9 классов. – М., Лаборатория Базовых Знаний, 2000. – 384с.
7. Вирт Н. Алгоритмы + структуры данных = программы. – М.:, Мир, 1985.
8. Вирт Н. Алгоритмы и структуры данных. – М.:, Мир, 1989.
9. Кнут Д. Искусство программирования для ЭВМ. Том
1. Основные алгоритмы. – М.:, Мир, 1976.
10. Кнут Д. Искусство программирования для ЭВМ. Том
3. Сортировка и поиск. – М.:, Мир, 1978.
11. Дейкстра Э. Дисциплина программирования. – М.:, Мир, 1978.
12. Дал У., Дейкстра Э., Хоор К. Структурное программирование. – М.:, Мир, 1975.
13. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. – М.: Мир, 1998. – 703 с.
14. Королев Л.Н., Миков А.И. Информатика. Введение в компьютерные науки. – М.: Высшая школа, 2002.
15. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – М.:, Мир, 1979.
16. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. – М.:, Мир, 1980.
17. Баррон Д. Рекурсивные методы в программировании. – М.:, Мир, 1974.
18. Берзтисс А. Структуры данных. М: Статистика, 1974. – 408с.
19. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М., МЦНМО, 2000. – 960с.
20. Липский В. Комбинаторика для программистов. М: Мир, 1988. – 213с.
21. Майерс Г. Искусство тестирования программ. М: Финансы и статистика, 1982. – 176с.
22. Майерс Г. Надежность программного обеспечения. М: Мир, 1980. – 360с.
23. Проценко В.С., Чаленко П.И., Сорока Р.А. Техника программирования. Киев: Выщы школа, 1990. – 183с.
