Пример готовой курсовой работы по предмету: Высшая математика
Содержание
Введение 3
Теоретическая часть 6
1. Булевы функции 6
2. Машина Тьюринга 8
Практическая часть 10
1. Разработка алгоритма 10
2. Реализация алгоритма на машине Тьюринга 13
3. Тестирование и определение параметров работы программы 25
Заключение 28
Список использованной литературы 29
Выдержка из текста
Логика образует такой пласт общечеловеческой культуры, без освоения которого в настоящее время не может состояться ни одна мыслящая личность. Основы логической культуры закладываются в школе и в первую очередь на уроках математики, ибо, как точно подметил еще Л.Н. Толстой, «математика имеет задачей не обучение исчислению, но обучение приемам человеческой мысли при исчислении».
Математическая логика – вершина развития логики, достигнутая ею в XX в. Органично соединив в себе традиционную логику, восходящую к Аристотелю, и методы современной математики, она получила глубокие результаты, которые легли в основу проектирования и создания электронно-вычислительных машин и программного обеспечения к ним, нашли широчайшее применение в областях информатики и систем искусственного интеллекта.
Теория булевых функций, возникшая из алгебры логики, лежит в фундаменте современной дискретной математики. Наряду с булевыми предикатами булевы функции являют собой самые простые объекты дискретной природы. Язык булевых функций хорошо приспособлен для описания подразделения целого на части и взаимосвязи этих частей. Поэтому он широко используется в самых разнообразных областях человеческого знания: будь то собственно математика или кибернетика (теория множеств и математическая логика, алгебра, теория графов и комбинаторика, теория информации, теория формальных языков и языков программирования, синтез управляющих систем и распознавание образов и т.д.), техника (анализ и построение различных устройств коммутации, управления и переработки информации, включая современные ЭВМ, тестирование сложных систем и построение надежных схем из ненадежных элементов), экономика, биология или социология.
Список областей, где могут применяться и с успехом применяются результаты и методы теории булевых функций, нетрудно продолжить и далее.
В вопросах приложений булевых функций наиболее часто встречаются две основные задачи: можно ли выразить заданную функцию или заданный класс функций булевыми функциями из имеющегося запаса булевых функций, и если это возможно, то каким образом и с какой сложностью? Это в свою очередь приводит к задаче описания замкнутых классов булевых функций и проверки функции на принадлежность к заданному классу.
Теория автоматов – раздел дискретной математики, изучающий абстрактные автоматы – вычислительные машины, представленные в виде математических моделей – и задачи, которые они могут решать. В 30-е гг. XX в., задолго до появления компьютеров, Алан Тьюринг исследовал абстрактную машину, которая, по крайней мере в области вычислений, обладала всеми возможностями современных вычислительных машин. Целью Тьюринга было точно описать границу между тем, что вычислительная машина может делать, и тем, чего она не может. Полученные им результаты применимы не только к абстрактным машинам Тьюринга, но и к реальным современным компьютерам.
Затем, в 60– 70-х гг. Стивен Кук развил результаты Тьюринга о вычислимости и невычислимости. Ему удалось разделить задачи на те, которые могут быть эффективно решены вычислительной машиной, и те, которые, в принципе, могут быть решены, но требуют для этого так много машинного времени, что компьютер оказывается практически бесполезным для решения почти всех экземпляров задачи, за исключением небольшого числа. Задачи последнего класса называют «трудно разрешимыми» или «NP-трудными». Даже при экспоненциальном росте быстродействия вычислительных машин («закон Мура») весьма маловероятно, что нам удастся достигнуть значительных успехов в решении задач этого класса на классических компьютерах.
Моделирование алгоритмов на машине Тьюринга помогает нам уяснить принципиальные возможности программного обеспечения. В частности, теория сложности вычислений позволяет определить, можем ли мы решить ту или иную задачу «в лоб» и написать соответствующую программу для ее решения (если эта задача не принадлежит классу «трудно разрешимых»), или же нам следует искать решение данной трудно разрешимой задачи в обход, используя приближенный, эвристический, или какой-либо другой метод, с помощью которого удастся ограничить время, затрачиваемое программой на ее решение.
Оценка времени проверки булевой функции на линейность на машине Тьюринга является примером одной из таких задач, имеющих как практическую, так и теоретическую ценность.
В данной работе будет рассмотрен класс линейных булевых функций и задача проверки произвольной булевой функции, заданной своим вектором значений, на принадлежность к этому классу c помощью машины Тьюринга.
Список использованной литературы
1. Игошин В.И. Математическая логика и теория алгоритмов: учеб. пособие для студ. высш. учеб. заведений / В.И. Игошин. – М.: Издательский центр «Академия», 2008. – 448 с.
2. Карпов Ю.Г. Теория автоматов / Ю.Г. Карпов. – СПб.: Питер, 2003. – 208 с.
3. Куприянов М. Эмулятор Машины Тьюринга [Электронный ресурс]
/ М. Куприянов. – Режим доступа: https://kouprianov.com/2011/11/turing-machine-emulator/
4. Марченков С.С. Замкнутые классы булевых функций / С.С. Марченков. – М.: ФИЗМАТЛИТ, 2000. – 128 с.
5. Пильщиков В.Н. Машина Тьюринга и алгоритмы Маркова. Решение задач / В.Н. Пильщиков, В.Г. Абрамов, А.А. Вылиток, И.В. Горячая. – М.: МГУ, 2006. – 47 с.
6. Поляков К.Ю. Тренажер для изучения универсального исполнителя «Машина Тьюринга» [Электронный ресурс]
/ К.Ю. Поляков. – Режим доступа: http://kpolyakov.spb.ru/prog/turing.htm
7. Яблонский С.В. Введение в дискретную математику: Учеб. пособие для вузов / С.В. Яблонский. – М.: Наука, 1986. – 384 с.
