«Теория алгоритмов и математические основы представления знаний»
На 2015-2016 уч. год
На баллы от 10 до 11
Вариант 27.
Тема: «Исследование алгоритма поиска простого пути на графе».
Задание: Реализовать алгоритм поиска простого пути на неориентированном графе. Граф представить в виде матрицы смежности. Показать трассировку рекурсивных вызовов (и пропущенные вершины) когда алгоритм поиска простого пути производит поиск пути из вершины 0 в вершину 5 на графе: 3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4. Провести эксперименты с целью определения эмпирическим путем вероятности того, что данный алгоритм найдет путь между двумя наудачу выбранными вершинами в различных графах и вычислить среднюю длину пути, найденного для различных графов.
Вариант 28.
Тема: «Исследование алгоритма поиска Гамильтонового пути на графе».
Задание: Реализовать алгоритм поиска Гамильтонового пути на неориентированном графе. Граф представить в виде матрицы смежности. Показать трассировку рекурсивных вызовов (и пропущенные вершины) когда алгоритм находит гамильтонов цикл на графе: 3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4. Рассмотреть графы, заданные следующими четырьмя наборами ребер:
0-1 0-2 0-3 1-3 1-4 2-5 2-9 3-6 4-7 4-8 5-8 5-9 6-7 6-9 7-8
0-1 0-2 0-3 1-3 0-3 2-5 5-6 3-6 4-7 4-8 5-8 5-9 6-7 6-9 8-8
0-1 1-2 1-3 0-3 0-4 2-5 2-9 3-6 4-7 4-8 5-8 5-9 6-7 6-9 7-8
4-1 7-9 6-2 7-3 5-0 0-2 0-8 1-6 3-9 6-3 2-8 1-5 9-8 4-5 4-7
Какие из этих графов содержат Гамильтоновы циклы? Либо показать, что такого не существует.
Вариант 29.
Тема: «Исследование алгоритма поиска Эйлерова пути на графе».
Задание: Реализовать алгоритм поиска Эйлерового пути на неориентированном графе. Граф представить в виде матрицы смежности. Рассмотреть графы, заданные следующими четырьмя наборами ребер:
0-1 0-2 0-3 1-3 1-4 2-5 2-9 3-6 4-7 4-8 5-8 5-9 6-7 6-9 7-8
0-1 0-2 0-3 1-3 0-3 2-5 5-6 3-6 4-7 4-8 5-8 5-9 6-7 6-9 8-8
0-1 1-2 1-3 0-3 0-4 2-5 2-9 3-6 4-7 4-8 5-8 5-9 6-7 6-9 7-8
4-1 7-9 6-2 7-3 5-0 0-2 0-8 1-6 3-9 6-3 2-8 1-5 9-8 4-5 4-7
Какие из этих графов содержат Эйлеровы циклы? Либо показать, что такого не существует. Найти число графов с V вершинами, которые содержат эйлеров цикл, для максимального числа V, для которого возможно выполнить реальные вычисления.
Вариант 30.
Тема: «Исследование алгоритма поиска в глубину на графе».
Задание: Реализовать алгоритм поиска в глубину на неориентированном графе. Граф представить в виде списка смежных вершин. Программа должна позволять возвращать размер связной компоненты. Представить трассировку вызовов рекурсивной функции поиска DFS для графа 0-2 0-5 1-2 3-4 4-5 3-5. Сделать чертеж дерева рекурсивных вызовов, соответствующего DFS.
Вариант 31.
Тема: «Исследование свойств алгоритма поиска в глубину на графе».
Задание: Реализовать алгоритм поиска в глубину на неориентированном графе. Граф представить в виде матрицы смежности. Программа должна выполнять трассировку поиска в глубину, которая будет производить классификацию каждого из двух представлений любого ребра графа на соответствие древесной связи, родительской связи, связи назад или связи вниз в дереве DFS. Представить трассировку поиска DFS для графа 0-2 0-5 1-2 3-4 4-5 3-5с классификацией связей.
Вариант 32.
Тема: «Исследование алгоритма раскраски графов».
Задание: Реализовать алгоритм для раскраски неориентированного графа в два цвета. Граф представить в виде списка смежных вершин. Программа должна определять, является ли исследуемый граф двудольным. Провести раскраску и определить является ли граф двудольным 0-1 0-2 0-3 1-3 1-4 2-5 2-9 3-6 4-7 4-8 5-8 5-9 6-7 6-9 7-8.
Вариант 33.
Тема: «Исследование алгоритма поиска мостов на графах».
Задание: Реализовать алгоритм определения реберной связности и поиска мостов на неориентированных графах. Граф представить в виде списка смежных вершин. Рассмотреть граф 3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4. Начертить дерево стандартного DFS, которое использовать для поиска мостов и реберно-связных компонент.
Вариант 34.
Тема: «Исследование алгоритма поиска в ширину на графах».
Задание: Реализовать алгоритм поиска в ширину на неориентированных графах. Программа должна предусматривать вывод кратчайшего пути из любой вершины графа во все другие вершины. Построить матрицы всех кратчайших путей для графа: 3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4.
Вариант 35.
Тема: «Исследование алгоритма рандомизированного поиска на графе».
Задание: Реализовать алгоритм рандомизированного поиска на неориентированных графах, который выбирает из накопителя то или иное ребро с равной вероятностью. Предложить три различных порядка обхода при рандомизированном поиске на графе 3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4. Может ли рандомизированный поиск наносить визиты вершинам данного графа в порядке следования их индексов? Доказать правильность ответа.
Вариант 36.
Тема: «Исследование свойств алгоритма поиска в глубину на орграфе».
Задание: Реализовать алгоритм поиска в глубину на ориентированном графе. Граф представить в виде списка смежных вершин. Программа должна выполнять классификацию каждого ребра графа на соответствие древесной связи, родительской связи, связи назад или связи вниз в дереве DFS. Начертить лес DFS, который получается при применении поиска в глубину к орграфу 3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4.
Вариант 37.
Тема: «Исследование алгоритма Уоршалла для построения транзитивного замыкания».
Задание: Реализовать алгоритм Уоршалла для построения транзитивного замыкания. Сколько ребер будет содержать транзитивное замыкание орграфа, который состоит только из простого ориентированного пути с V вершинами? Построить транзитивное замыкание для орграфа 3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4. Провести эмпирические исследования с целью определить число ребер в транзитивном замыкании различных типов графов.
Вариант 38.
Тема: «Исследование алгоритма топологической сортировки орграфа».
Задание: Реализовать алгоритм топологической сортировки орграфа. Сколько и каких различных топологических сортировок возможно на графе DAG орграфа 3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4 4-3 2-3?
Вариант 39.
Тема: «Исследование алгоритма обратной топологической сортировки орграфа».
Задание: Реализовать алгоритм обратной топологической сортировки орграфа. Сколько и каких различных обратных топологических сортировок возможно на графе DAG орграфа 3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4 4-3 2-3?
Вариант 40.
Тема: «Исследование алгоритма топологической сортировки орграфа, основанной на очереди истоков».
Задание: Реализовать алгоритм топологической сортировки орграфа, основанный на очереди истоков. Покажите процесс топологической сортировки графа DAG 3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4 4-3 2-3 с помощью алгоритма, использующего очередь истоков.
Вариант 41.
Тема: «Исследование алгоритма Косарайю для определения сильных компонент».
Задание: Реализовать алгоритм Косарайю для определения сильных компонент на орграфе. Описать, что произойдет и привести пример, когда данный алгоритм будет применен для: а) нахождения сильных компонент графа DAG; б) для нахождения сильных компонент орграфа, который состоит из одного цикла. Показать леса DFS и содержимое вспомогательных векторов, индексированных именами вершин, которые получаются для вычисления сильных компонент орграфа 3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4.
Вариант 42.
Тема: «Исследование алгоритма Тарьяна для определения сильных компонент».
Задание: Реализовать алгоритм Тарьяна для определения сильных компонент на орграфе. Описать, что произойдет и привести пример, когда данный алгоритм будет применен для: а) нахождения сильных компонент графа DAG; б) для нахождения сильных компонент орграфа, который состоит из одного цикла. Показать леса DFS и содержимое стека во время выполнения алгоритма и окончательное содержимое векторов, индексированных именами вершин, которые получаются для вычисления сильных компонент орграфа 3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4.
Вариант 43.
Тема: «Исследование алгоритма Габова для определения сильных компонент».
Задание: Реализовать алгоритм Габова для определения сильных компонент на орграфе. Описать, что произойдет и привести пример, когда данный алгоритм будет применен для: а) нахождения сильных компонент графа DAG; б) для нахождения сильных компонент орграфа, который состоит из одного цикла. Показать леса DFS и содержимое стека во время выполнения алгоритма и окончательное содержимое векторов, индексированных именами вершин, которые получаются для вычисления сильных компонент орграфа 3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4.
Вариант 44.
Тема: «Исследование алгоритма Прима для построения дерева MST».
Задание: Реализовать алгоритм Прима для построения дерева MST. Представить результаты построения дерева MST с помощью данного алгоритма для сети 1-0(3) 3-5(6) 5-2(2) 3-4(8) 5-1(1) 0-3(7) 0-4(6) 4-2(1) 2-3(5).
Вариант 45.
Тема: «Исследование алгоритма Крускала для построения дерева MST».
Задание: Реализовать алгоритм Крускала для построения дерева MST. Представить результаты построения дерева MST с помощью данного алгоритма для сети 1-0(3) 3-5(6) 5-2(2) 3-4(8) 5-1(1) 0-3(7) 0-4(6) 4-2(1) 2-3(5).
Вариант 46.
Тема: «Исследование алгоритма Борувки для построения дерева MST».
Задание: Реализовать алгоритм Борувки для построения дерева MST. Представить результаты построения дерева MST с помощью данного алгоритма для сети 1-0(3) 3-5(6) 5-2(2) 3-4(8) 5-1(1) 0-3(7) 0-4(6) 4-2(1) 2-3(5).
Вариант 47.
Тема: «Исследование алгоритма Дейкстры для поиска кратчайших путей».
Задание: Реализовать алгоритм Дейкстры для поиска кратчайших рутей на сети. Представить результаты поиска кратчайших путей для данного алгоритма для сети 1-0(3) 3-5(6) 5-2(2) 3-4(8) 5-1(1) 0-3(7) 0-4(6) 4-2(1) 2-3(5).
megaobuchalka.ru
по дисциплине «Математическая логика и теория алгоритмов»
(из сборника тем курсовых работ по математике / В.А. Молчанов, В.Е. Новиков, Т.М. Отрыванкина, П.Н. Пронин, В.Е. Фирстов. – Оренбург: ГОУ ОГУ, 2004. – 68 с. )
Номер варианта = номер по списку
Тема 1. Методы решения логических задач.
В курсовой работе предлагается осветить символический и графический методы решения логических задач. Рекомендуется следующий план работы.
Рассмотреть основные понятия алгебры высказываний и логики предикатов (/1/, с.10-35, 122-134).
Изучить приложение алгебры высказываний и логики предикатов к логико-математической практике (/1/, с. 64-88, 195-221).
Изучить кванторные операции над предикатами (/1/, с. 157-165).
Рассмотреть решение "логических" задач на языке символов (/3/, с.60-65).
Разобрать графический способ решения задач подобного рода (/2/, с.9-56).
Разобрать решения всех задач из цитированных выше разделов указанных литературных источников и решить задачи 3.58-3.61 из книги /3/. Выполнить 5 заданий из упражнений 1-91 на с. 57-60 книги /2/.
Литература, рекомендуемая для изучения темы
Игошин В.И. Математическая логика и теория алгоритмов. – М.: Изд-во «Академия», 2004. – 448 с.
Кэрролл Л. Логическая игра: Пер. с англ. Ю.А. Данилова. - М.: Наука, 1991. (М.: "Квант"; Вып. 73).
Игошин В.И. Задачник-практикум по математической логике: Учеб. пособие для студентов-заочников физ.-мат. фак-в пед. ин-тов. - М.: Просвещение, 1986.
Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов. - М.: Изд-во «Академия», 2006. – 304 с.
Тема 2. Неразрешимость логики первого порядка.
Одним из принципиально важных результатов математической логики является доказательство неразрешимости в логике первого порядка проблем распознавания как общезначимости, так и выполнимости ее предложений. В курсовой работе необходимо изучить доказательства неразрешимости логики первого порядка. Рекомендуется следующий план работы.
Изучить основные понятия логики первого порядка (/1/, с. 130-151).
Рассмотреть понятие машины Тьюринга и доказать неразрешимость проблемы остановки (/1/, с. 36-54).
Вывести неразрешимость логики первого порядка из неразрешимости проблемы остановки (/1/, с. 152-160).
Разобрать доказательство неразрешимости логики первого порядка методом Геделя (/1/, с. 160-166).
Литература, рекомендуемая для изучения темы
Булос Дж., Джеффри Р. Вычислимость и логика. - М.: Мир, 1994.
Решить задачи 3.6, 3.10 из упражнения на стр. 46-48 и задачи 10.1, 10.3 из упражнения на стр. 164-165 в книге /1/.
Тема 3. Метод диагонализации в математической логике.
В математической логике, теории множеств и других разделах математики широко применяется метод диагонализации, в основе которого лежит возможность построения антидиагонального счетного множества для любой последовательности счетных множеств. В курсовой работе необходимо изучить метод диагонализации и с его помощью построить примеры невычислимых функций. Рекомендуется следующий план работы.
Рассмотреть понятие счетного множества и изучить метод диагонализации (/1/, с. 12-30).
Рассмотреть понятие машины Тьюринга и методом диагонализации построить пример невычислимой функции (/1/, с. 36-45, 66-74).
Рассмотреть проблему остановки машины Тьюринга и с помощью тезиса Черча доказать ее неразрешимость (/1/, с. 47-48, 74-76).
Рассмотреть понятие диагонализации выражения и доказать лемму о диагонализации и теорему Черча о неразрешимости (/1/, с. 228-235).
Разобрать решения всех примеров из цитированных разделов /1/ и решить задачи 3.9, 3.10 из упражнения на стр. 45-48 и задачи 5.1-5.4 из упражнения на стр. 76-77 в книге /1/.
Литература, рекомендуемая для изучения темы
Булос Дж., Джеффри Р. Вычислимость и логика. - М.: Мир, 1994.
Тема 4. Машины Тьюринга и невычислимые функции
Машина Тьюринга и вычислимость являются фундаментальными понятиями математической логики. В курсовой работе необходимо изучить основные свойства машины Тьюринга и с ее помощью построить невычислимую функцию. Рекомендуется следующий план работы.
Разобрать такие основополагающие понятия математической логики, как машина Тьюринга, вычислимая функция и тезис Черча (/1/, с. 36-54; /2/, с.228-229, 249-255).
Рассмотреть понятие продуктивности машины Тьюринга и доказать ее основные свойства (/1/, с. 46, 55-60; /2/, с. 12-25).
Доказать невычислимость функции продуктивность машины Тьюринга (/1/, с. 60-64).
Рассмотреть проблему остановки машины Тьюринга и доказать ее неразрешимость (/1/, с. 47-48, 53-54, 64-65).
Разобрать решения всех примеров из литературных источников /1/,/2/ и решить задачи 3.1-3.10 из упражнения на стр. 45-48 в книге /1/.
Литература, рекомендуемая для изучения темы
Булос Дж., Джеффри Р. Вычислимость и логика. - М.: Мир, 1994.
Мендельсон Э. Введение в математическую логику. - М.: Наука, 1971.
Тема 5. Вычислимость и рекурсивные функции.
Рекурсивная функция и вычислимость являются фундаментальными понятиями математической логики. В курсовой работе необходимо изучить вычислимость на абаке, вычислимость машиной Тьюринга и доказать их эквивалентность понятию рекурсивной функции. Рекомендуется следующий план работы.
Разобрать такие основополагающие понятия математической логики, как машина Тьюринга, рекурсивная функция и тезис Черча (/1/, с. 36-54).
Рассмотреть понятие «обычного» компьютера, введенное Иоахимом Ламбеком и названное им абаком, доказать, что вычислимость функции абаком сводится к вычислимости ее машиной Тьюринга (/1/, с. 78-95).
Доказать, что рекурсивные функции вычислимы на абаках (/1/, с. 100122).
Доказать, что вычислимые функции рекурсивны (/1/, с. 100-122).
Разобрать решения всех примеров из цитированных разделов книги /1/ и решить задачи 6.1-6.4 из упражнения на стр. 96 в книге /1/.
Тема 6. Отрицательные результаты математической логики.
Главными отрицательными результатами математической логики являются теорема Черча о неразрешимости логики, теорема Тарского о неопределимости истинности и первая теорема Геделя о неполноте систем арифметики. В курсовой работе необходимо изучить доказательства этих теорем с помощью представления рекурсивных функций в специальном расширении арифметики. Рекомендуется следующий план работы.
Разобрать такие основополагающие понятия математической логики, как язык арифметики и рекурсивная функция (/1/, с. 103-108, 141-145).
Рассмотреть понятие представимости функций в теории и доказать представимость рекурсивных функций в специальном непротиворечивом расширении Q арифметики (/1/, с. 212-226).
Рассмотреть понятие геделевой нумерации и доказать главные отрицательные результаты математической логики (/1/, с. 228-240).
Разобрать решения всех примеров из цитированных разделов книги /1/ и решить задачи 14.1-14.2 из упражнения на стр. 226-227 и задачи 15.1-15.4 из упражнения на стр. 240 в книге /1/.
Литература, рекомендуемая для изучения темы
Булос Дж., Джеффри Р. Вычислимость и логика. - М.: Мир, 1994.
Тема 7. Разрешимость арифметики сложения.
Проблема разрешимости теорий имеет принципиальное значение для элементарно аксиоматизируемых математических теорий и, в частности, для арифметики. В курсовой работе необходимо проанализировать эту проблему для арифметики с различными основными операциями. Рекомендуется следующий план работы.
Разобрать такие основополагающие понятия математической логики, как геделева нумерация и разрешимое множество (/1/, с. 228-233, /2/, с. 151152).
Доказать неразрешимость арифметики со сложением и умножением (/1/, с. 234-236).
Доказать разрешимость арифметики со сложением, без умножения (/1/, с. 290-299).
Разобрать решения всех примеров из цитированных разделов книг /1/,/2/ и решить задачи 1-3 из упражнения на стр. 152 в книге /2/.
^ Тема 8. Логика второго порядка.
Логика второго порядка существенно отличается от логики первого порядка и позволяет всесторонне исследовать такую фундаментальную проблему математической логики, как определимость арифметической истины. В курсовой работе необходимо изучить основные методы логики второго порядка и с их помощью проанализировать понятие определимости в арифметике. Рекомендуется следующий план работы.
Изучить основные понятия логики второго порядка и проанализировать ее главные отличия от логики первого порядка (/1/, с. 261273).
Рассмотреть понятие определимого в теории множества и исследовать проблему определимости множеств предложений первого порядка, истинных в стандартной модели арифметики (/1/, с. 273, 274-280).
Рассмотреть введенный П. Коэном метод вынуждения и доказать с его помощью теорему Дж. Аддисона о неопределимости в арифметике класса множеств, определимых в арифметике (/1/, с. 281-289).
Разобрать решения всех примеров из цитированных разделов книги /1/ и решить задачи 18.1-18.4 из упражнения на стр. 272-273 и задачи 20.1-20.10 из упражнения на стр. 289 в книге /1/.
Литература, рекомендуемая для изучения темы
Булос Дж., Джеффри Р. Вычислимость и логика. - М.: Мир, 1994.
Тема 9. Неполнота формальной арифметики.
Теорема Геделя о неполноте формальной арифметики по праву считается одним из наиболее замечательных достижений математической логики, поскольку в своей семантической формулировке устанавливает невозможность доказательства любого истинного утверждения этой формальной теории. В курсовой работе необходимо изучить основы формальной арифметики и разобрать доказательство семантической формулировки теоремы Геделя о ее неполноте. Рекомендуется следующий план работы.
Изучить постановку задачи о неполноте формальной арифметики (/1/,с. 7-11).
Рассмотреть начальные понятия теории алгоритмов и примеры их применения (/1/, с. 12-21).
Доказать простейшие критерии неполноты (/1/, с. 21-25).
Изучить основы формальной арифметики и доказать семантическую формулировку теоремы Геделя о ее неполноте (/1/, с. 25-42).
Разобрать примеры./1/.
Литература, рекомендуемая для изучения темы
1. Успенский В.А. Теорема Геделя о неполноте. - М.: Наука, 1982.
2. Игошин В.И. Математическая логика и теория алгоритмов. – М.: Изд-во «Академия», 2004. – 448 с.
Тема 10. Разрешимые и неразрешимые аксиоматические теории.
Проблема разрешимости теорий имеет принципиальное значение для элементарно аксиоматизируемых математических теорий. В курсовой работе необходимо изучить методы доказательства разрешимости и неразрешимости теорий, проиллюстрировав их применение на известных важных примерах. Рекомендуется следующий план работы.
Разобрать такие основополагающие понятия теории моделей, как язык узкого исчисления предикатов (УИП) и его интерпретация в моделях, рассмотреть известные конструкции над алгебраическими системами (/1/, с. 103-118; /2/, с. 12-25).
Изучить методы доказательства разрешимости и неразрешимости теорий (/2/, с. 265-275).
Рассмотреть известные примеры доказательства разрешимости и неразрешимости аксиоматических теорий (/2/, с. 275-292; /3/).
Разобрать решения всех примеров из литературных источников /1/, /2/.
Литература, рекомендуемая для изучения темы
1 Ершов Ю.Л., Палютин Е.А. Математическая логика. - М.: Наука,1979.
2 Ершов Ю. Л. Проблемы разрешимости и конструктивные модели. -М.: Наука, 1980.
Рабин М.О. Разрешимые теории. В кн.: Справочная книга по математической логике, ч.3. Теория рекурсии. - М.: Наука, 1982. - с. 77-111.
Ершов Ю.Л., Лавров И.А., Тайманов А.Д., Тайцлин М.А. Элементарные теории // УМН, 1965, 20, № 4, с. 37-108.
Игошин В.И. Математическая логика и теория алгоритмов. – М.: Изд-во «Академия», 2004. – 448 с.
Тема 11. Решение задач логики узкого исчисления предикатов.
Интерполяционная лемма Крейга дает положительное решение следующей важной задачи логики узкого исчисления предикатов (УИП): если из предложения A следует предложение C, то существует предложение B, которое следует из A, из которого следует C и которое содержит лишь нелогические символы, входящие как в A, так и в C. В курсовой работе необходимо изучить доказательство интерполяционной леммы Крейга и рассмотреть ее приложения к задаче о непротиворечивости объединения теорий и к задаче об определимости понятий теории. Рекомендуется следующий план работы.
1 Разобрать доказательство интерполяционной леммы Крейга (/1/, с.308-318).
Доказать теорему Робинсона о непротиворечивости объединения теорий (/1/, с. 319-322).
Доказать теорему Бета об определимости понятий теории (/1/, с. 25-32).
Выполнить упражнение на с. 327 в книге /1/.
Литература, рекомендуемая для изучения темы
1 Булос Дж., Джеффри Р. Вычислимость и логика. - М.: Мир, 1994.
Тема 12 Машины Тьюринга.
Дать определение машины Тьюринга.
Рассмотреть применения машины Тьюринга к словам. Конструирование машин Тьюринга. Вычислимые по Тьюрингу функции.
Разобрать примеры.
Литература, рекомендуемая для изучения темы
Игошин В.И. Математическая логика и теория алгоритмов. – М.: Изд-во «Академия», 2004. – 448 с.
Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов. - М.: Изд-во «Академия», 2006. – 304 с.
^ Тема 13. Существование и единственность модели формализации теории. В любой математической теории принципиально важным является вопрос о существовании и единственности модели формализации этой теории. В курсовой работе необходимо проанализировать этот вопрос для элементарной теории арифметики. Рекомендуется следующий план работы.
1 Рассмотреть язык логики узкого исчисления предикатов арифметики и его стандартную интерпретацию в алгебре натуральных чисел(/1/, с. 131-151; /2/, с. 115-131).
2 Доказать теорему о существовании нестандартных моделей элементарной теории арифметики (/1/, с. 252-260).
3 Изучить метод построения моделей элементарной теории арифметики с помощью принципов нестандартного анализа (/1/, с. 25-32; /3/, с. 57-79).
Разобрать все примеры из указанных выше литературных источников и решить задачи 17.1, 17.2 в /1/, а также задачи 1-3 на стр.131 в книге /2/.
Литература, рекомендуемая для изучения темы
1 Булос Дж., Джеффри Р. Вычислимость и логика. – М.: Мир, 1994.
2 Мендельсон Э. Введение в математическую логику. – М.: Наука, 1971.
^ Тема 14. Булевы алгебры. Понятие булевой алгебры играет важную роль в алгебре, математической логике и дискретной математике. В курсовой работе необходимо изучить характеристические свойства булевых алгебр, проанализировать взаимосвязь основных свойств таких алгебр, доказать теорему о представлении конечной булевой алгебры алгеброй множеств. Рекомендуется следующий план работы.
1 Изучить характеристические свойства булевых алгебр и проанализировать их взаимосвязь с булевыми кольцами (/1/, глава 1, § 2, /2/, глава 1, § 1.1).
2 Рассмотреть основные свойства булевых алгебр и теорему о представлении конечной булевой алгебры алгеброй множеств (/1/, глава 1, § 2, /2/, глава 1, § 1.1).
Разобрать все примеры из указанных выше литературных источников и решить задачи 2, 3, 4, 5 на стр. 42 в /1/.
Литература, рекомендуемая для изучения темы
1 Лидл Р., Пильц Г., Прикладная абстрактная алгебра. – Екатеринбург: Изд-во УрГУ, 1996.
2 Богомолов А.В., Салий В.Н. Алгебраические основы теории дискретных систем. – М.: Наука, 1997.
^ Тема 15. Минимизация булевых многочленов. Проблема минимизации булевых многочленов играет важную роль в булевой алгебре и ее приложениях. В курсовой работе необходимо изучить основные свойства булевых многочленов методы их минимизации. Рекомендуется следующий план работы.
1 Рассмотреть понятия булевой алгебры и булева кольца, доказать еих основные свойства (/1/, с. 31-43).
2 Рассмотреть понятия булева многочлена и булевой полиномиальной функции, доказать их основные свойства (/1/, с. 43-47, 53-56).
3 Изучить алгоритмы построения дизъюнктивной нормальной формы и конъюнктивной нормальной формы булева многочлена (/1/, с. 47-53).
4 Рассмотреть проблему минимизации булевых многочленов и изучить метод минимизации таких многочленов, разработанный Куайном-Мак-Класки (/1/, с. 60-70).
Разобрать решения всех примеров из указанного выше литературного источника и решить задачи 5-8, 15 из упражнения на стр. 59-60 и задачи 1-5 из упражнения на стр. 70 в /1/.
Литература, рекомендуемая для изучения темы
1 Лидл Р., Пильц Г., Прикладная абстрактная алгебра, Екатеринбург: Изд-во УрГУ, 1996.
2 Богомолов А.В., Салий В.Н. Алгебраические основы теории дискретных систем. – М.: Наука, 1997.
^ Тема 16. Приложения булевых алгебр к переключательным схемам. Одним из наиболее важных практических приложений алгебры является использование булевых многочленов для моделирования и упрощения переключательных схем. В курсовой работе необходимо изучить основные задачи алгебры переключательных схем и разобрать методы их решения с помощью булевых многочленов. Рекомендуется следующий план работы.
1 Рассмотреть понятия булевой алгебры и булева многочлена, доказать их основные свойства (/1/, с. 31-53).
2. Изучить основные понятия алгебры переключательных схем и разобрать способ представления переключательных функций с помощью диаграмм Карно (/1/, с. 74-86, 111-122).
3. Разобрать типичные примеры приложений переключательных схем (/1/, с. 89-104).
4. Разобрать приложение переключательных схем к сложению двоичных чисел с помощью полусумматоров и сумматоров (/1/, с. 105-111).
Разобрать решения всех примеров из указанного выше литературного источника /1/ и решить задачи 1-4, 9-11, 15, 19, 21 из упражнения на стр. 124-130 в /1/.
Литература, рекомендуемая для изучения темы
1 Лидл Р., Пильц Г., Прикладная абстрактная алгебра. – Екатеринбург: Изд-во УрГУ, 1996.
www.ronl.ru
1. История развития информатики.
2. Кибернетика - наука об управлении.
3. Информатика и управление социальными процессами.
4. Информационные системы.
5. Автоматизированные системы управления.
6. Автоматизированные системы научных исследований.
7. Построение интеллектуальных систем.
8. Компьютерная революция: социальные перспективы и последствия.
9. Информационные технологии в деятельности современного специалиста.
10. Правонарушения в сфере информационных технологий.
11. Защита информации.
12. Информационный бизнес.
1. Проблема информации в современной науке.
2. Передача информации.
3. Дискретизация непрерывных сообщений.
4. Субъективные свойства информации.
5. Непрерывная и дискретная информация.
6. Информация и энтропия.
7. Вероятность и информация.
8. Проблема измерения информации.
9. Ценностный подход к информации.
10. Семантическая информация.
11. Атрибутивная и функциональная концепции информации.
12. Информация и эволюция живой природы.
13. Информационные процессы в неживой природе.
14. Отражение и информация.
15. Материя, энергия и информация.
16. Синергетика и информация.
17. Познание, мышление и информация.
18. Свойства информационных ресурсов.
19. Информация и сознание.
1. Системы счисления древнего мира.
2. Римская систем счисления. Представление в ней чисел и решение арифметических задач.
3. История систем счисления (десятичной, двоичной, восьмеричной, шестнадцатеричной).
1. История кодирования информации.
2. Символы и алфавиты для кодирования информации.
3. Кодирование и шифрование.
4. Основные результаты теории кодирования.
5. Современные способы кодирования информации в вычислительной технике.
1. История теории графов.
2. Задачи, сводящиеся к графам.
3. Связность в графах.
4. Графы и отношения на множествах.
5. Теоремы о числах графов.
6. Устойчивость графов.
7. Расстояния и пути в графах.
1. История формирования понятия "алгоритм".
2. Известнейшие алгоритмы в истории математики.
3. Проблема существования алгоритмов в математике.
4. Средства и языки описания (представления) алгоритмов.
5. Методы разработки алгоритмов.
1. Проблема алгоритмической разрешимости в математике.
2. Основатели теории алгоритмов - Клини, Черч, Пост, Тьюринг.
3. Основные определения и теоремы теории рекурсивных функций.
4. Тезис Черча.
5. Проблемы вычислимости в математической логике.
6. Машина Поста.
7. Машина Тьюринга.
8. Нормальные алгоритмы Маркова и ассоциативные исчисления в исследованиях по искусственному интеллекту.
1. Жизненный цикл программных систем.
2. Методы управления проектами при разработке программных систем.
3. Методы проектирования программных систем.
4. Модульный подход к программированию.
5. Структурный подход к программированию.
6. Объектно-ориентированный подход к программированию.
7. Декларативный подход к программированию.
8. Параллельное программирование.
9. Case-технологии разработки программных систем.
10. Доказательное программирование.
11. Новинки средств управления проеками: UML.
sites.google.com
2. Сайт Кафедры «Прикладной математики» Физико-механического факультета Санкт-Петербургского государственного технического университета: http://amd.stu.neva.ru/education/prog71.htm
3. Сайт УГАТУ (рефераты и лекции):
www.twirpx.com/files/special/protection/
4. Электронный вариант книги Носова В.А. «Алгоритмы и оценки их сложности»:
rrc.dgu.ru/res/intsys.msu.ru/staff/vnosov/theoralg.htm
5. Электронный вариант книги Мальцева А.И. «Алгоритмы и рекурсивные функции»:
www.proklondike.com/contentview.php?content
9. Методические указания студентам| Виды учебной работы | Всего часов |
| Общая трудоемкость | 90 |
| Аудиторные занятия | 44 |
| Лекции | 24 |
| Практические занятия | 10 |
| Самостоятельная работа: | 46 |
| 1. Изучение программы курса | 24 |
| 1.1. Проработка материалов по конспекту лекций | 24*1/3 =8 |
| 1.2. Изучение материалов, изложенных в лекции, по учебникам и разбор самостоятельных доказательств, решение практических задач | 24*2/3 =16 |
| 2. Подготовка рефератов по теории алгоритмов | 12 |
| 3. Подготовка к аудиторной контрольной работе | 2*2 =4 |
| 4. Выполнение домашней индивидуальной работы | 2 |
| 5. Выполнение индивидуального проекта по теории графов (написание эссе, подготовка доклада, оформление презентации) / курсовой работы | 2 |
| 6. Вид итогового контроля – зачет | 2 |
2. Список тем индивидуальных проектов по теории алгоритмов для самостоятельной разработки (написание эссе, подготовка доклада, оформление презентации):
Установленный срок подготовки презентации и защиты проекта на научной конференции студенческой группы в конце семестра – 3 недели.
Студентам сообщаются следующие критерии оценки отчета о выполнении проекта:
Цель данной курсовой работы – исследовать причины возникновения тео-рии алгоритмов, ее необходимость для обоснования иных математических наук.
Рекомендуется следующий план изложения материала:
1. Проблемы отсутствия алгоритма для решения класса математических задач (проблема тождества для полугрупп и групп, нахождение общего способа решения диофантовых уравнений и др.)./1/, § 71.
2. Неразрешимые задачи в теории алгоритмов. /2/,с. 279-282.
Литература, рекомендуемая для изучения темы:
1. Клини С.К. Введение в математику.- М.: ИЛ, 1957.
2. Мендельсон Э. Введение в математическую логику.- М.: Наука, 1984.
2. Алгоритмы поиска.
Цель данной курсовой работы - рассмотреть основные алгоритмы на
графах, которые находят применение при сжатии информации, распознавании
образов и синтезе баз данных.
Рекомендуется следующий план изложения материала:
1. Необходимые понятия теории графов (/2/, с. 9-43, /1/, с. 57-64).
2. Бинарный поиск (/1/, с. 64-65).
3. Быстрая сортировка (/1/, с. 65-69).
4. Алгоритм Дикстры (/1/, с. 69-72).
Литература, рекомендуемая для изучения темы:
1. Гоппа В.Д. Введение в алгебраическую теорию информации. – М.:
Наука, 1995.
2. Уилсон Р. Введение в теорию графов. – М.: Мир, 1977.
3. Неразрешимость логики первого порядка.
Одним из принципиально важных результатов математической логики и теории алгоритмов является доказательство неразрешимости в логике первого порядка проблем распознавания как общезначимости, так и выполнимости ее предложений. Цель данной курсовой работы - изучить доказательства неразрешимости логики первого порядка.
Рекомендуется следующий план работы:
1. Изучить основные понятия логики первого порядка (/1/, с. 130-151).
2. Рассмотреть понятие машины Тьюринга и доказать неразрешимость проблемы остановки (/1/, с. 36-54).
3. Вывести неразрешимость логики первого порядка из неразрешимости
проблемы остановки (/1/, с. 152-160).
4. Разобрать доказательство неразрешимости логики первого порядка
методом Геделя (/1/, с. 160-166).
5. Решить задачи 3.6, 3.10 из упражнения на стр. 46-48 и задачи 10.1, 10.3
из упражнения на стр. 164-165 в книге /1/.
Литература, рекомендуемая для изучения темы:
1. Булос Дж., Джеффри Р. Вычислимость и логика. – М.: Мир, 1994.
4. Нестандартные модели арифметики.
В любой математической теории принципиально важным является вопрос о существовании и единственности модели формализации этой теории. Цель данной курсовой работы - проанализировать этот вопрос для элементарной теории арифметики.
Рекомендуется следующий план работы:
1. Рассмотреть язык логики узкого исчисления предикатов арифметики
и его стандартную интерпретацию в алгебре натуральных чисел(/1/, с. 131-151; /2/, с. 115-131).
2. Доказать теорему о существовании нестандартных моделей
элементарной теории арифметики (/1/, с. 252-260).
3. Изучить метод построения моделей элементарной теории арифметики с помощью принципов нестандартного анализа (/1/, с. 25-32; /3/, с. 57- 79).
4. Разобрать все примеры из указанных выше литературных источников и решить задачи 17.1, 17.2 в /1/, а также задачи 1-3 стр.131 в книге /2/.
Литература, рекомендуемая для изучения темы:
1. Булос Дж., Джеффри Р. Вычислимость и логика. – М.: Мир, 1994.
2. Мендельсон Э. Введение в математическую логику. – М.: Наука, 1971.
5. Метод диагонализации в математической логике.
В теории алгоритмов, математической логике, теории множеств и других разделах математики широко применяется метод диагонализации, в основе которого лежит возможность построения антидиагонального счетного множества для любой последовательности счетных множеств. Цель данной курсовой работы - изучить метод диагонализации и с его помощью построить примеры невычислимых функций. Рекомендуется следующий план работы:
1. Рассмотреть понятие счетного множества и изучить метод диагонализации (/1/, с. 12-30).
2. Рассмотреть понятие машины Тьюринга и методом диагонализации построить пример невычислимой функции (/1/, с. 36-45, 66-74).
3. Рассмотреть проблему остановки машины Тьюринга и с помощью тезиса Черча доказать ее неразрешимость (/1/, с. 47-48, 74-76).
4. Рассмотреть понятие диагонализации выражения и доказать лемму о диагонализации и теорему Черча о неразрешимости (/1/, с. 228-235).
5. Разобрать решения всех примеров из цитированных разделов /1/ и решить задачи 3.9, 3.10 из упражнения на стр. 45-48 и задачи 5.1-5.4 из упражнения на стр. 76-77 в книге /1/.
Литература, рекомендуемая для изучения темы:
1. Булос Дж., Джеффри Р. Вычислимость и логика. – М.: Мир, 1994.
6. Машины Тьюринга и невычислимые функции.
Машина Тьюринга и вычислимость являются фундаментальными понятиями теории алгоритмов. Цель данной курсовой работы - изучить основные свойства машины Тьюринга и с ее помощью построить невычислимую функцию.
Рекомендуется следующий план работы:
1. Разобрать такие основополагающие понятия теории алгоритмов,
как машина Тьюринга, вычислимая функция и тезис Черча (/1/, с. 36-54; /2/, с.228-229, 249-255).
2. Рассмотреть понятие продуктивности машины Тьюринга и доказать ее основные свойства (/1/, с. 46, 55-60; /2/, с. 12-25).
3.Доказать невычислимость функции - самоприменимость машины Тьюринга (/1/, с. 60-64).
4. Рассмотреть проблему останова машины Тьюринга и доказать ее неразрешимость (/1/, с. 47-48, 53-54, 64-65).
5. Разобрать решения всех примеров из литературных источников /1/,/2/ и решить задачи 3.1-3.10 из упражнения на стр. 45-48 в книге /1/.
Литература, рекомендуемая для изучения темы:
1. Булос Дж., Джеффри Р. Вычислимость и логика. – М.: Мир, 1994.
2. Мендельсон Э. Введение в математическую логику. – М.: Наука,1971.
7. Вычислимость на абаке и рекурсивные функции.
Рекурсивная функция и вычислимость являются фундаментальными понятиями теории алгоритмов. Цель данной курсовой работы - изучить вычислимость на абаке, вычислимость машиной Тьюринга и доказать их эквивалентность понятию рекурсивной функции.
Рекомендуется следующий план работы:
1. Разобрать такие основополагающие понятия теории алгоритмов, как мА шина Тьюринга, рекурсивная функция и тезис Черча (/1/, с. 36-54).
2. Рассмотреть понятие «обычного» компьютера, введенное Иоахимом Ламбеком и названное им абаком, доказать, что вычислимость функции абаком сводится к вычислимости ее машиной Тьюринга (/1/, с. 78-95).
3. Доказать, что рекурсивные функции вычислимы на абаках (/1/, с. 100-122).
4. Доказать, что вычислимые функции рекурсивны (/1/, с. 100-122).
5. Разобрать решения всех примеров из цитированных разделов книги /1/ и решить задачи 6.1-6.4 из упражнения на стр. 96 в книге /1/.
Литература, рекомендуемая для изучения темы:
1. Булос Дж., Джеффри Р. Вычислимость и логика. – М.: Мир, 1994.
8. Представимость рекурсивных функций и отрицательные результаты математической логики.
Главными отрицательными результатами теории алгоритмов являются теорема Черча о неразрешимости, теорема Тарского о неопределимости истинности и первая теорема Геделя о неполноте систем арифметики. Цель данной курсовой работы - изучить доказательства этих теорем с помощью представления рекурсивных функций в специальном расширении арифмети-ки.
Рекомендуется следующий план работы:
1. Разобрать такие основополагающие понятия теории алгоритмов,
как язык арифметики и рекурсивная функция (/1/, с. 103-108, 141-145).
2. Рассмотреть понятие представимости функций в теории и доказать
представимость рекурсивных функций в специальном непротиворечивом расширении Q арифметики (/1/, с. 212-226).
3. Рассмотреть понятие геделевой нумерации и доказать главные
отрицательные результаты теории алгоритмов (/1/, с. 228-240).
4. Разобрать решения всех примеров из цитированных разделов книги /1/ и решить задачи 14.1-14.2 из упражнения на стр. 226-227 и задачи 15.1-15.4 из упражнения на стр. 240 в книге /1/.
Литература, рекомендуемая для изучения темы:
1. Булос Дж., Джеффри Р. Вычислимость и логика. – М.: Мир, 1994.
10. Разрешимость арифметики сложения.
Проблема разрешимости теорий имеет принципиальное значение для элементарно аксиоматизируемых математических теорий и, в частности, для арифметики. Цель данной курсовой работы - проанализировать эту проблему для арифметики с различными основными операциями.
Рекомендуется следующий план работы:
1. Разобрать такие основополагающие понятия математической логики, как геделева нумерация и разрешимое множество (/1/, с. 228-233, /2/, с.151-152).
2. Доказать неразрешимость арифметики со сложением и умножением (/1/, с. 234-236).
3. Доказать разрешимость арифметики со сложением, без умножения (/1/, с. 290-299).
4. Разобрать решения всех примеров из цитированных разделов книг /1/,/2/ и решить задачи 1-3 из упражнения на стр. 152 в книге /2/.
Литература, рекомендуемая для изучения темы:
1. Булос Дж., Джеффри Р. Вычислимость и логика. – М.: Мир, 1994.
11. Теорема Геделя о неполноте формальной арифметики.
Теорема Геделя о неполноте формальной арифметики по праву считается одним из наиболее замечательных достижений математической логики и теории алгоритмов, поскольку в своей семантической формулировке устанавливает невозможность доказательства любого истинного утверждения этих формальной теории. Цель данной курсовой работы - изучить основы формальной арифметики и разобрать доказательство семантической формулировки теоремы Геделя о ее неполноте.
Рекомендуется следующий план работы:
1. Изучить постановку задачи о неполноте формальной арифметики (/1/,с. 7-11).
2. Рассмотреть начальные понятия теории алгоритмов и примеры их
применения (/1/, с. 12-21).
3. Доказать простейшие критерии неполноты (/1/, с. 21-25).
4. Изучить основы формальной арифметики и доказать семантическую формулировку теоремы Геделя о ее неполноте (/1/, с. 25-42).
5. Разобрать все примеры и восстановить все пропущенные доказательства в брошюре /1/.
Литература, рекомендуемая для изучения темы:
1. Успенский В.А. Теорема Геделя о неполноте. – М.: Наука, 1982.
12. Разрешимые и неразрешимые аксиоматические теории.
Проблема разрешимости теорий имеет принципиальное значение для элементарно аксиоматизируемых математических теорий. Цель данной курсовой работы - изучить методы доказательства разрешимости и неразрешимости теорий, проиллюстрировав их применение на известных важных примерах.
Рекомендуется следующий план работы:
1. Разобрать такие основополагающие понятия теории моделей, как
язык узкого исчисления предикатов (УИП) и его интерпретация в моделях, рассмотреть известные конструкции над алгебраическими системами (/1/, с.103-118; /2/, с. 12-25).
2. Изучить методы доказательства разрешимости и неразрешимости
теорий (/2/, с. 265-275).
3. Рассмотреть известные примеры доказательства разрешимости и
неразрешимости аксиоматических теорий (/2/, с. 275-292; /3/).
4. Разобрать решения всех примеров из литературных источников /1/, /2/.
Литература, рекомендуемая для изучения темы:
1. Ершов Ю.Л., Палютин Е.А. Математическая логика. – М.: Наука, 1979.
2. Ершов Ю.Л. Проблемы разрешимости и конструктивные модели. –
М.: Наука, 1980.
3. Рабин М.О. Разрешимые теории. В кн.: Справочная книга по
математической логике, ч.3. Теория рекурсии. – М.: Наука, 1982. – с. 77-111.
4. Ершов Ю.Л., Лавров И.А., Тайманов А.Д., Тайцлин М.А.
Элементарные теории // УМН, 1965, 20, № 4, с. 37-108.
II. Материалы, устанавливающие содержание и порядок проведения промежуточных и итоговых аттестаций
1. Вопросы для зачета
1. Интуитивное определение понятия «алгоритм». Свойства алгоритма2. Простейшие функции. Операция подстановки. Свойства операции подстановки. Операция примитивной рекурсии. Свойства операции примитивной рекурсии. Примитивно-рекурсивное описание функции.
3. Примитивно-рекурсивная функция. Свойства примитивно-рекурсивных функций. Примеры примитивно-рекурсивных функций. Относительная примитивная рекурсивность. Свойства относительной примитивной рекурсивности.
4. Примитивно-рекурсивные операции (операция введения фиктивных переменных, операция подстановки констант, операция произвольной подстановки). Операции конечного суммирования и конечного произведения. Пример использования операции конечного суммирования для доказательства примитивной рекурсивности функции [x/y].
5. Представляющая функция предиката. Примитивно-рекурсивный предикат. Примитивно-рекурсивный предикат относительно совокупности функций и предикатов. Логические операции. Операции навешивания ограниченных кванторов. Кусочное задание функции.
6. m-операция (операция минимизации). Частично рекурсивное описание функции. Частично рекурсивная функция. Примеры частично рекурсивных функций. Общерекурсивная функция. Примеры общерекурсивных функций.
Формальная система рекурсивных функций Эрбрана-Гёделя. Функция, вычислимая по Эрбрану-Гёделю.
7. Рекурсивно-перечислимое множество. Критерий рекурсивной перечислимости множества. Рекурсивные множество. Критерий рекурсивности множества (теорема Поста).
8. Нормальный алгоритм Маркова в алфавите и над алфавитом. Нормально-вычислимые функции.
9. Примеры нормальных алгоритмов (тождественный нормальный алгоритм, нормальный алгоритм левого присоединения, нормальный алгоритм правого присоединения, нормальный алгоритм удвоения, некоторые арифметические алгоритмы).
10. Машина Тьюринга. Операции над машинами Тьюринга (операция композиции, операция ветвления, операция зацикливания). Гёделева нумерация машин Тьюринга.
11. Функция, вычислимая по Тьюрингу. Доказательство существования функций, невычислимых по Тьюрингу. Пример невычислимой по Тьюрингу функции.
12. Примеры алгоритмически неразрешимых проблем (проблема распознавания самоприменимости, проблема применимости).
13. Машина Поста. Машина Поста-Успенского.
14. Машина с неограниченными регистрами (МНР).
gagago.ru
