Вузы по математике
Готовые работы по математике
Как писать работы по математике
Примеры решения задач по математике
Решить задачу по математике onlineМатематическая логика и теория алгоритмов
Индивидуальные вопросы и задания по курсу
Математическая логика и теория алгоритмов
Обязательными для изучения каждым студентом являются вопросы О1, О2.
Ответы на вопросы индивидуального задания (номер билета определяется по номеру в журнале) необходимо оформить в электронном виде.
Вопросы Д3 – дополнительные.
О1. – Основные понятия: программирование, программа, алгоритмизация, алгоритм
О2.– Современные технологии программирования и алгоритмизации.
– Структурное программирование: следование, ветвление, цикл
– нисходящее проектирование
– модульное программирование
– объектно-ориентированное программирование (ООП): инкапсуляция, наследование полиморфизм
Д3.– Современные технологии программирования и алгоритмизации.
– CASE-системы
– индустрия искусственный интеллект: системы, основанные на знаниях
– экспертные системы
– универсальное программирование
– динамическое программирование
– визуальное программирование
Варианты индивидуальных заданий
№ 1 Математическая логика и теория алгоритмов
1. Основные понятия, предмет, метод, цели и задачи теории алгоритмов.
2. Трудоемкость алгоритмов и временные оценки. Основные алгоритмические конструкции
3. Алгоритм точного решения задачи о сумме (метод перебора).
4. Решить задачи 1 и 7.
№ 2 Математическая логика и теория алгоритмов
1. Введение в теорию алгоритмов. Понятие алгоритма ученых древних цивилизаций.
2. Анализ простых алгоритмов. Задача суммирования элементов квадратной матрицы
3. NP – полные задачи. Задача о выполнимости схемы.
4. Решить задачи 2 и 8
№ 3 Математическая логика и теория алгоритмов
1. Формализация понятия вычислимости Поста и Тьюринга.
2. Анализ простых алгоритмов. Задача поиска максимума в массиве. Худший случай.
3. NP – полные задачи. Задача о сумме
4. Решить задачи 3 и 9
№ 4 Математическая логика и теория алгоритмов
1. Формализация понятия вычислимости (Гедель, Черч и Клини).
2. Анализ простых алгоритмов. Задача поиска максимума в массиве. Лучший случай.
3. NP – полные задачи. Задача о клике и ее особенности
4. Решить задачи 4 и 10
№ 5 Математическая логика и теория алгоритмов
1. Формализация понятия вычислимости Маркова.
2. Анализ простых алгоритмов. Задача поиска максимума в массиве. Средний случай.
3. Рекурсивные функции и алгоритмы.
4. Решить задачи 5 и 11.
№ 6 Математическая логика и теория алгоритмов
1. Основные типы формальных конструкций алгоритмов.
2. Алгоритм точного решения задачи о сумме (метод перебора).
3. Реализация линейных алгоритмов.
4. Решить задачи 6 и 12.
№ 7 Математическая логика и теория алгоритмов
1. Алгоритмические машины.
2. Задача перехода от функции трудоемкости к оценке времени работы алгоритма.
3. Реализация разветвляющихся алгоритмов.
4. Решить задачи 7 и 13.
№ 8 Математическая логика и теория алгоритмов
1. Функции вычислимые алгоритмом.
2. Проблема позиционирования в машине Поста.
3. Реализация циклических алгоритмов.
4. Решить задачи 8 и 14.
№ 9 Математическая логика и теория алгоритмов
1. Исчисления.
2. Этапы разработки программы. Формальная постановка задачи разработки алгоритма.
3. Рекурсивная реализация алгоритмов.
4. Решить задачи 9 и 15.
№ 10 Математическая логика и теория алгоритмов
1. Понятие неразрешимости задачи. Алгоритмически неразрешимые проблемы
2. Асимптотический анализ функций. Оценка Q (тетта).
3. Дерево рекурсивных вызовов.
4. Решить задачи 10 и 16.
№ 11 Математическая логика и теория алгоритмов
1. Понятие «эффективного» алгоритма. Классы P — и NP-задач.
2. Энтропийная устойчивость.
3. Этапы разработки алгоритма и программы.
4. Решить задачи 11 и 17.
№ 12 Математическая логика и теория алгоритмов
1. Основные направления в теории алгоритмов и их краткая характеристика.
2. Асимптотический анализ функций. Оценка О (О большое).
3. Формальная постановка задачи разработки программы (алгоритма).
4. Решить задачи 12 и 18.
№ 13 Математическая логика и теория алгоритмов
1. Классическая теория алгоритмов: методы асимптотического и практического анализа.
2. Пооперационный временной анализ. Задача умножения двух комплексных чисел. Алгоритм А1.
3. Унифицированная форма записи формальной постановки задачи разработки программы (алгоритма).
4. Решить задачи 13 и 19
№ 14 Математическая логика и теория алгоритмов
1. Формализация понятия алгоритма: определения 1.1, 1.2 (Колмогоров), 1.3 (Марков).
2. Асимптотический анализ функций. Оценка W (Омега).
3. Введение в анализ алгоритмов. Сравнительные оценки алгоритмов.
4. Решить задачи 14 и 20
№ 15 Математическая логика и теория алгоритмов
1. Требования, предъявляемые к алгоритмам. Свойства, типы и составляющие алгоритмов.
2. Пооперационный временной анализ. Задача умножения двух комплексных чисел. Алгоритм А2.
3. Система обозначений в анализе алгоритмов.
4. Решить задачи 15 и 21
№ 16 Математическая логика и теория алгоритмов
1. Алгоритмические машины. Основные особенности и принципы функционирования.
2. Переход к временным оценкам. Пооперационный анализ.
3. Классификация алгоритмов по виду функции трудоёмкости.
4. Решить задачи 16 и 22.
№ 17 Математическая логика и теория алгоритмов
1. Функции вычислимые алгоритмом. Рекурсивные и базисные функции.
2. Количество информации. Шенновские модели криптосистемы.
3. Составить формальную и алгоритмическую модели решения задачи 9
4. Решить задачи 17 и 23.
№ 18 Математическая логика и теория алгоритмов
1. Исчисления. Основные особенности и принципы. Примеры исчислений в IT.
2. Переход к временным оценкам Метод Гиббсона.
3. Асимптотический анализ функций. Оценка Q (тетта).
4. Решить задачи 1 и 18.
№ 19 Математическая логика и теория алгоритмов
1. Машина Поста. Основные понятия и операции. Финитный 1 – процесс.
2. Введение в анализ алгоритмов. Сравнительные оценки алгоритмов.
3. Асимптотический анализ функций. Оценка О (О большое).
4. Решить задачи 2 и 19.
№ 20 Математическая логика и теория алгоритмов
1. Машина Поста. Пример программы. Причины останова машины при выполнении программы.
2. Переход к временным оценкам Метод прямого определения среднего времени.
3. Асимптотический анализ функций. Оценка W (Омега).
4. Решить задачи 3 и 20.
№ 21 Математическая логика и теория алгоритмов
1. Машина Поста. Система записи чисел, принципы, положенные в основу функционирования.
2. Теория сложности вычислений. Теоретический предел трудоемкости задачи.
3. Примеры функций, не связанных асимптотическими обозначениями.
4. Решить задачи 4 и 21.
№ 22 Математическая логика и теория алгоритмов
1. Машина Тьюринга. Формальное описание и состав. Способ задания решаемой проблемы.
2. Теория сложности вычислений. Сложностные классы задач. Класс P.
3. Трудоемкость алгоритмов и временные оценки. Элементарные операции в языке записи алгоритмов.
4. Решить задачи 5 и 22.
№ 23 Математическая логика и теория алгоритмов
1. Машина Тьюринга. Математическое описание.
2. Теория сложности вычислений. Сложностные классы задач. Класс NP.
3. Анализ простых алгоритмов. Задача суммирования элементов квадратной матрицы.
4. Решить задачи 6 и 23.
№ 24 Математическая логика и теория алгоритмов
1. Машина Тьюринга. Функция переходов и проблема останова.
2. Теория сложности вычислений. Сложностные классы задач. Проблема P = NP.
3. Анализ простых алгоритмов. Задача поиска максимума в массиве. Худший случай.
4. Решить задачи 7 и 15.
№ 25 Математическая логика и теория алгоритмов
1. Машина Тьюринга. Функция переходов и проблема останова.
2. Теория сложности вычислений. Сложностные классы задач. Класс NPC.
3. Анализ простых алгоритмов. Задача поиска максимума в массиве. Лучший случай.
4. Решить задачи 8 и 16.
№ 26 Математическая логика и теория алгоритмов
1. Классификация алгоритмов по виду функции трудоёмкости.
2. Система обозначений в анализе алгоритмов.
3. Переход к временным оценкам. Метод прямого определения среднего времени.
4. Решить задачи 9 и 17.
№ 27 Математическая логика и теория алгоритмов
1. Трудоемкость алгоритмов. Элементарные операции в языке записи алгоритмов.
2. Унифицированная форма записи формальной постановки задачи разработки алгоритма.
3. Анализ простых алгоритмов. Задача поиска максимума в массиве. Средний случай.
4. Решить задачи 10 и 18
№ 28 Математическая логика и теория алгоритмов
1. Рекурсивные функции и алгоритмы.
2. Машина Поста. Программы, добавляющая к числу метку справа, слева.
3. Задача перехода от функции трудоемкости к оценке времени работы алгоритма на конкретном процессоре.
4. Решить задачи 11 и 19.
№ 29 Математическая логика и теория алгоритмов
1. Реализация линейных, разветвляющихся и циклических алгоритмов.
2. Машина Поста. "Блок поиска числа".
3. Переход к временным оценкам. Пооперационный анализ.
4. Решить задачи 12 и 20.
№ 30 Математическая логика и теория алгоритмов
1. Рекурсивная реализация алгоритмов. Дерево рекурсивных вызовов.
2. Примеры функций, не связанных асимптотическими обозначениями.
3. Переход к временным оценкам. Метод Гиббсона.
4. Решить задачи 15 и 21.
Типовые задачи практического задания
1. Составить алгоритм для нахождения НОД двух натуральных чисел.
2. Является ли алгоритмически разрешимой следующая задача: Вычислить п— ое совершенное число
13. Выполнить формальную постановку задачи. Определить мощность, потребляемую в приведенной ниже электрической цепи (Примечание: любое из сопротивлений может быть равным нулю).
14. Выполнить формальную постановку задачи. Определить мощность, потребляемую в приведенной ниже электрической цепи (Примечание: проводимость любой из ветвей может быть равна бесконечности).
15. Составить формальную и алгоритмическую модели решения задачи. В книжном магазине вы желаете купить три книги. У вас имеется небольшая сумма наличных денег и пластиковая карта, на счету которой большая сумма денег. Вам бы не хотелось сегодня пользоваться пластиковой картой, так как Вы в дальнейшем запланировали крупную покупку. Определите способ покупки.
16. Составить формальную и алгоритмическую модели решения задачи. Определите вариант пути от дома до места учебы, в зависимости от времени выхода из дома и времени начала учебных занятий.
17. Составить формальную и алгоритмическую модели решения задачи. В избирательной компании в органы власти участвуют две партии: зеленых и прозрачных. Какая информация будет опубликована в СМИ по итогам голосования?
18. Составить формальную и алгоритмическую модели решения задачи. Для двух чисел Х, Y определить, являются ли они корнями уравнения А*Р4+D*P2+C=0.
19. Составить алгоритм для ответов на вопросы, возникающие на этапе формального решения задачи.
20. Составить алгоритм вычисления корней уравнения X2+B*X+C=0. Оценить сложность алгоритма
21. Составить алгоритм вычисления корней уравнения А*X2+B*X+C=0. Оценить сложность алгоритма
22. Составить алгоритм для нахождения НОД двух натуральных чисел.
23. Является ли алгоритмически разрешимой следующая задача: Вычислить п — ое совершенное число
Вопросы к экзамену
Логика высказываний
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. Понятие финитного 1-процесса в машине Поста;
32. Способы задания проблем и формулировка 1;
33. Гипотеза Поста;
34. Формальное описание машины Тьюринга;
35. Функция переходов в машине Тьюринга;
36. Понятие об алгоритмически неразрешимых проблемах
37. Проблема позиционирования в машине Поста;
38. Проблема соответствий Поста над алфавитом S;
39. Проблема останова в машине Тьюринга;
40. Проблема эквивалентности и тотальности;
41. Формальная система языка высокого уровня;
42. Понятие трудоемкости алгоритма в формальном базисе;
43. Обобщенный критерий оценки качества алгоритма,
44. Обозначения в анализе алгоритмов: худший, лучший и средний случаи;
45. Классификация алгоритмов по виду функции трудоемкости;
46. Примеры количественных и параметрически–зависимых алгоритмов;
47. Обозначения в асимптотическом анализе функций;
48. Примеры функций, не связанных асимптотическими обозначениями;
49. Элементарные операции в псевдоязыке высокого уровня;
50. Анализ трудоемкости основных алгоритмических конструкций;
51. Построение функции трудоемкости для задачи суммирования матрицы;
52. Построение функции трудоемкости для поиска максимума в массиве;
53. Проблемы при переходе от трудоемкости к временным оценкам;
54. Методики перехода от функции трудоемкости к временным оценкам;
55. Возможности пооперационного анализа алгоритмов на примере задачи умножения комплексных чисел;
56. Теоретический предел трудоемкости задачи;
57. Основные задачи теории сложности вычислений
58. Понятие сложностных классов задач, класс Р;
59. Сложностной класс NP, понятие сертификата;
60. Проблема P=NP, и ее современное состояние;
61. Сводимость языков и определение класса NPC;
62. Примеры NP – полных задач;
63. Задача о клике и ее особенности;
64. Формулировка задачи о сумме;
65. Асимптотическая оценка сложности алгоритма для прямого перебора;
66. Алгоритм решения задачи о сумме;
67. Подалгоритм увеличения на единицу двоичного счетчика;
68. Оценки трудоемкости для лучшего и худшего случая;
69. Функция трудоемкости алгоритма для решения задачи о сумме;
70. Понятие индукции и рекурсии;
71. Примеры рекурсивного задания функций;
72. Рекурсивная реализация алгоритмов
73. Трудоемкость механизма вызова функции в языке высокого уровня;
74. Рекурсивное дерево, рекурсивные вызовы и возвраты;
75. Трудоемкость рекурсивного алгоритма вычисления факториала;
76. Анализ рекурсивных соотношений методом итераций;
77. Анализ рекурсивных соотношений методом подстановки;
78. Общий вид функции трудоемкости при решении задач методом декомпозиции;
79. Основная теорема о рекуррентных соотношениях;
80. Примеры решения рекуррентных соотношений на основе теоремы Бентли – Хакен – Сакса;
81. Рекурсивный алгоритм сортировки слиянием
82. Процедура слияния двух отсортированных массивов
83. Оценка трудоемкости процедуры слияния;
84. Подсчет вершин в дереве рекурсивных вызовов для алгоритма сортировки слиянием;
85. Анализ алгоритма рекурсивной сортировки методом прямого подсчета вершин рекурсивного дерева;
86. Функции подсчета количества битов и количества единиц в двоичном представлении числа и их свойства;
87. Алгоритм быстрого возведения в степень
88. Анализ трудоемкости алгоритма быстрого возведения в степень;
89. Понятие полугруппы, моноида и группы, примеры групп;
90. Сравнения и сведения из теории простых чисел;
91. Мультипликативная группа вычетов по модулю N и ее свойства;
92. Степени элементов группы и теорема Ферма-Эйлера;
93. Вероятностный тест Миллера-Рабина для поиска простых чисел;
94. Криптосистема RSA;
95. Применение теории алгоритмов к анализу криптостойкости RSA.
Рекомендуемая литература
Основная:
1. Ульянов М. В., Шептунов М. В. Математическая логика и теория алгоритмов, часть 2: Теория алгоритмов.– М.: МГАПИ, 2003.– 80 с.
2. Цыганов А. В. Введение в теорию алгоритмов (части 1, 2).– СПбГУ, 2008
3. Афанасьева Т. В. Алгоритмы и программы : учебное пособие / Т. В. Афанасьева, Ю. Е. Кувайскова, В. А. Фасхутдинова. – Ульяновск : УлГТУ, 2011. – 227 с. ISBN 978-5-9795-0857-3
4. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ. — М.: «Вильямс», 2006. с. 1296.
5. Дональд Кнут Искусство программирования, том 1. Основные алгоритмы — 3-е изд. — М.: «Вильямс», 2006. — С. 720. — ISBN 0-201-89683-4
6. А. К. Гуц, Математическая логика и теория алгоритмов, Либроком, 2009 г., 120 стр.
7. Павловская Т. А. С/С++. Программирование на языке высокого уровня. Учебник. – Спб.: «Питер», 2009.- 464 стр.: ил.
8. Полубенцева М. С/С++. Процедурное программирование. Издательство: БХВ-Петербург, 2008 г., 448 стр.
Дополнительная:
9. Киммел П. и др. Borland C++ 5: Пер. с англ. – Спб.: «БХВ — Петербург», 2001.- 976 стр.: ил.
10. Павловская Т. А., Щупак Ю. А. C/C++. Структурное и объектно-ориентированное программирование. Практикум– Спб.: «Питер», 2010.- 352 стр.
11. Юркин А. Г. Задачник по программированию. – Спб.: «Питер», 2002.- 192 стр.
12. Культин Н. С/С++ в задачах и примерах. Спб: «БХВ-Петербург», 2003., 288 стр.
13. Бройдо В. Л. Вычислительные системы, сети и коммуникации. Учебник для вузов. 2-е изд. СПб.: «Питер», 2006, 702 стр.
14. Орлов С..А. Технологии разработки программного обеспечения. Учебник для вузов — Спб.: «Питер», 2004.- 528 стр.: ил. 1. А. Н. Колмогоров, Теория информации и теория алгоритмов. — М.: Наука, 1987. — 304 с.
15. Клини С. К. Введение в метаматематику. — М.: ИЛ, 1957.
16. Джордж Пойа. Математическое открытие. М., Наука, 1976
17. Фридланд А. Я. Информатика: процессы, системы, ресурсы. М.: БИНОМ. Лаборатория знаний, 2003.
18. Шеннон Р. Имитационное моделирование систем – искусство и наука. М.: Мир, 1990.
19. Вольфенгаген В. Э. Методы и средства вычислений с объектами. Аппликативные вычислительные системы. — М.: АО «Центр ЮрИнфоР»,2004. — 78С
20. С. А. Абрамов Лекции о сложности алгоритмов, МЦНМО, 2009 г., 256 стр.
21. А. К. Гуц, Математическая логика и теория алгоритмов, Либроком, 2009 г., 120 стр.
22. Лекции В. М. Абрамова "Алгоритмы и алгоритмические языки”, МФТИ.
23. Лекции Л. Н. Столярова "Информатика и применение компьютеров в научных исследованиях”, МФТИ.
24. А. Н. Колмогоров, Теория информации и теория алгоритмов. — М.: Наука, 1987. — 304 с.
25. Марков А. А., Нагорный Н. М. Теория алгорифмов, изд. 2. — М.: ФАЗИС, 1996
26. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ. — М.: «Вильямс», 2006. с. 1296.
27. Дональд Кнут. Искусство программирования, том 1. Основные алгоритмы — 3-е изд. — М.:«Вильямс», 2006. — С. 720. — ISBN 0-201-89683-4
28. Н. К. Верещагин, А. Х. Шень, Основы теории вычислимых функций, курс INTUIT.
29. Н. К. Верещагин, А. Х. Шень, Языки и исчисления, курс INTUIT.
30. В. С. Рублев, Языки логического программирования, курс INTUIT
31. http://th-algoritmov. narod. ru/metodi. htm
32. http://www. fvn2009.narod. ru/Manuscripts/Algorithmization. htm
http://www. inf1.info/algorithmbasics
Скидка 30% по промокоду Diplom2020
Получи промокод на скидку 20%
