Контрольные по математике | Математическая логика и теория алгоритмов | Matematiku5
Вузы по математике Готовые работы по математике Как писать работы по математике Примеры решения задач по математике Решить задачу по математике 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

А ты боишься COVID-19?

 Пройди опрос и получи промокод