25. Опишите структуру исчисления предикатов (ИП). Приведите пример формального вывода в ИП.
26. Опишите понятия интерпретации и модели. Что означает полнота, семантическая и синтаксическая непротиворечивость, разрешимость формальных теорий? Каково практическое значение исследования этих свойств?
27. Что такое алгоритм?
28. Опишите машину Тьюринга. Опишите способы задания МТ в виде таблицы, графа, системы команд. Приведите примеры алгоритмов. Реализуемых на МТ.
29. Что такое универсальная МТ? В чем заключается «тезис Тьюринга», каков его практически значимый смысл?
30. В чем заключается проблема остановки МТ? Докажите, что проблема остановки является неразрешимой задачей для МТ.
31. Чем обосновывается существование алгоритмически неразрешимых задач?
2.4. Вопросы для подготовки к зачету (4 семестр)
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. Что такое стек? Привести примеры из жизни.
31. Что такое очередь? Привести примеры из жизни.
32. Как построить дерево двоичного поиска из заданных элементов?
33. Что такое коллизия и как с ними бороться? Привести пример.
34. Описать метод цепочек и метод открытой адресации. Привести пример.
35. Описать алгоритм умножения матрицы на матрицу. Привести пример.
36. Решить уравнение методом деления отрезка пополам.
37. Описать метод прямоугольников.
38. Описать метод трапеций.
39. Описать метод Симпсона.
40. Что такое погрешность численного метода?
3.3. Список рекомендуемой основной и дополнительной литературы
Основная литература
1. Пестунова Т.М. Теоретическая информатика (учебное пособие). / Т.М. Пестунова, В.М.Белолипецкий, Т.А.Тушко. – Красноярск: КГТУ , 1999 - 156с[1].
2. Пестунова Т.М. Дискретная математика. Основы теории графов (учебное пособие[2]) / Н.А.Богульская, Т.М.Пестунова – Красноярск: КГТУ , 2005 – 82с.
3. Пестунова Т.М. Введение в комбинаторику (учебное пособие). / Т.М.Пестунова. – Красноярск: КГТУ , 203 - 96 с[3]
4. Пестунова Т.М. Множества, отношения, алгебраические структуры (методические указания) / Т.М.Пестунова – Красноярск: КГТУ, 1999[4].
5. Кузнецов О.П. Дискретная математика для инженера. / О.П.Кузнецов. – С-Пб: «Лань», 2007 – 400с.[5]
6. Пестунов А.И. Структуры данных и алгоритмы./ А.И. Пестунов. –НГУЭУ, 2006. – 30 с.
7. Кнут Д. Искусство программирования./Д. Кнут. – Т. 3. Сортировка и поиск. М.: Вильямс, 2004. – 822 с.
8. Вирт Н. Алгоритмы и структуры данных./ Н. Вирт. – СПб.: Невский Диалект, 2005. – 357 с.
9. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ./ Т. Кормен, Ч. Лейзерсон, Р. Ривест. - М.: Бином: МЦНТО, 2004. – 955 с.
Дополнительная литература
1. Виленкин Н.Я. Комбинаторика. – М.: Наука, 1969
2. Липский В. Комбинаторика для программистов – М.:Мир, 1988.
3. Дмитриев В.И. Прикладная теория информации – М.: Высш. Шк., 1986
4. Седжвик Р. Фундаментальные алгоритмы на С++./ Р. Седжвик. – СПб.: ООО «ДиаСофтЮП», 2002. – 688 с.
5. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов./ А. Ахо, Дж. Хопкрофт, Дж .Ульман. – М.: Мир, 1979. - 383 с.
6. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов./ С. Гудман, С. Хидетниеми. – М.: Мир, 1981. – 368 с.
7. Новиков Ф.А. Дискретная математика для программистов./ Ф.А. Лэнгсам Й., Огенстайн М., Тененбаум А. Структуры данных для персональных ЭВМ./ Й. Лэнгсам, М. Огенстайн, А. Тененбаум. – М.: Мир, 1989. – 568 с.
[1] Авторское учебное пособие в НГУЭУ доступно в отсканированном электронном виде
[2] Рекомендовано Сиб РУМО ВПО для межвузовского использования в качестве учебного пособия для студентов по специальностям в области информационной безопасности. Авторское учебное пособие в НГУЭУ доступно в электронном виде
[3] Авторское учебное пособие в НГУЭУ доступно в отсканированном электронном виде
[4] Авторское учебное пособие в НГУЭУ доступно в отсканированном электронном виде
[5] Существуют более ранние издания данного пособия: Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженеров – М.:Энергоатом издат, 1988.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.