Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
![](images/emoji__ok.png)
Предоплата всего
![](images/emoji__signature.png)
Подписываем
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Что подразумевается под термином Алгоритм. Основные требования для
создания алгоритма.
алгоритм это однозначно трактуемая процедура, осуществляемая черным ящиком для получения выхода из входа. Чтобы создать алгоритм необходимо знать:
1. какую работу должен выполнять алгоритм.
2. какими должны быть входные данные.
3. какими должны быть выходные данные.
Основные принципы построения алгоритмов. Блок - схема алгоритма.
Связи между шагами можно изобразить в виде графа:
Такой граф, в котором вершинам соответствуют шаги, а ребрам переходы между шагами, называется блок-схемой алгоритма. Его вершины могут быть двух видов:
1) из которой выходит одно ребро операторы;
2) из которой выходит два ребра логические условия или предикаты.
.. Представление данных.
При разработке программ стоит задача представления, моделирования и использования самых разных видов информации.
Информацией называют абстрактное содержание какого-либо высказывания, описания, указания, сообщения или известия. Внешнюю форму информации называют представлением. Представление интерпретируется, чтобы получить информацию.
Алгебра высказываний.
Отрицанием высказывания А называется высказывание А, которое истинно тогда и только тогда, когда высказывание А ложно. Конъюнкцией двух высказываний А и B называется высказывание А&B, истинное тогда и только тогда, когда истинны оба высказывания А и B Дизъюнкцией двух высказываний А и B называется высказывание АVB, ложное тогда и только тогда, когда ложны оба высказывания А и B. Импликацией двух высказываний А и B называется высказывание А B, ложное тогда и только тогда, когда А истинно, а B ложно.
Формулы алгебры высказываний
1. Любая высказывательная переменная, а также константы И, Л есть формула.
2. Если A и B формулы, то А, AVB, A&B, АB, АB есть формулы.
3. Ничто, кроме указанного в пунктах 1 2, не есть формула.
Как называется сложное высказывание.
Если имеется несколько высказываний, то при помощи логических операций можно образовывать различные новые высказывания. При этом исходные высказывания принято называть простыми, а вновь образованные высказывания сложными.
Кванторы. Предикаты.
Предикатом P(x1, x2, ... , xn) называется функция, аргументы которой определены на некотором множестве М, x1, x2, ... , xn M, а сама она принимает два значения: И (истина) и Л (ложь).
Формулы логики предиката.
1. Любая формула логики высказываний есть формула логики предикатов.
К новым формулам логики предикатов относятся следующие выражения:
2. Предметные переменные x, y, z, ... есть формулы.
3. Предикаты P(x), Q(x, y), ... , а также выражения с кванторами xP(x), xR(x), xyQ(x, y),... есть формулы.
4. Если A и B формулы, то A, AVB, A&B, AB, AB есть формулы, в которых свободные переменные формул A и B остаются свободными, а связанные переменные формул A и B остаются связанными.
.. Интерпретация формулы логики предикатов в виде суждения
Формула есть перевод содержательного рассуждения в формальное рассуждение. Формула имеет смысл только тогда, когда имеется какая-нибудь интерпретация входящих в нее символов. Каждая интерпретация состоит в указании множества М изменения предметных переменных и задании отношения между переменными с помощью предикатов.
Для данной интерпретации формула представляет собой высказывание, если переменные связаны кванторами, а если есть свободные переменные, то формула есть предикат, который может быть истинным для одних значений переменных из области интерпретации и ложным для других.
Исчисления высказываний.
В соответствии с общими принципами построения формальных систем (исчислений) исчисление высказываний определяется следующим образом.
1 Символы исчисления высказываний включают в себя: а) знаки логических операций , б) буквы Xi с целыми положительными индексами i; в) скобки и запятую ( , ).
Исчисление предикатов
1. Символы исчисления предикатов включают в себя: а) символы предметных переменных x1, x2,…, xn, …; б) символы предметных констант a1, a2,…, an, …; в) символы или имена предикатов A, A,…A, …;символы или имена функций f, f,…f, …; д) знаки логических операций , е) символы кванторов , ; ж) скобки и запятую ( , ) ,.
Нечеткие множества.
Нечетким множеством на множестве X назовем пару (X, mA), где mA(x) функция, каждое значение которой mA(x) [0, 1] интерпретируется как степень принадлежности точки xX множеству. Функция mA называется функцией принадлежности множества .
Операции с нечеткими множествами.
Операции |
Лингвистический смысл |
Формула для mC(x) |
Пересечение = Объединение = Дополнение Концентрация Размывание |
и или не очень не очень |
min(mA(x), mB(x)) max(mA(x), mB(x)). 1 mA(x) [mA(x)]2 [mA(x)]1/2 |
Нечеткие высказывания, нечеткие предикаты.
Нечетким высказыванием называется высказывание , степень истинности которого () можно оценить числом из интервала [0, 1], () [0, 1]. Если () = 0,5, то высказывание называется индиффирентным.
Алфавит. Алгоритмы в алфавите.
Алфавитом называется всякое непустое множество символов, а сами символы алфавита называются буквами.
Примером алфавита может служить конечное множество символов или, например, русский алфавит.
Словом в данном алфавите А называется всякая конечная последовательность букв алфавита А.
Распространение нормального алгоритма по Маркову.
Пусть задан алфавит А, не содержащий в качестве букв символов "•" и "→", и пусть Р и Q слова в алфавите А. Тогда выражения Р→Q, P→•Q называются формулами подстановки в алфавите А.
Формула подстановки Р→Q называется простой подстановкой и означает, что вместо Р нужно подставить слово Q и перейти к следующей подстановке.
Формула подстановки Р→•Q называется заключительной подстановкой и означает, что вместо Р нужно подставить Q и закончить процесс преобразования.
Основные свойства операций над нормальным алгоритмом.
Композиция алгоритмов. Пусть A и B два алгоритма в алфавите А. Композицией алгоритмов A и B в алфавите А называют алгоритм C такой, что
Машина Тьюринга.
Машина Тьюринга абстрактная машина. Это математическая модель идеализированного вычислительного устройства.
Машина Тьюринга состоит из ленты и управляющего устройства со считывающей и записывающей головки
Ламбда-исчисление
Прежде чем ввести лямбда-исчисление укажем возможную область её использования в вычислительных моделях.
Различают следующие вычислительные модели:
императивную (процедурную) логические вычислительные модели, основанные на вычислениях с помощью логики предикатов. Примеры таких языков Пролог, Дейталог, Параллельный Пролог;
функциональные вычислительные модели, в которых программа рассматривается как множество определений функций.
Примитивно рекурсивность некоторых функций. Частично - рекурсивные
функции
Сложность вычислений с помощью алгоритма
Сложность исходных данных понимается как длина (размер) их записи. Что такое размер входа? Всё зависит от того, что является входом. Размером входа, в общем случае, считают число символов, с помощью которых записан вход.
Пусть входом является целое число. Считаем, что число представлено в системе счисления с некоторым фиксированным основанием. В этих системах число символов, необходимых для представления целого числа n равно ]logAn[, где основание системы, а ]х[ обозначает наименьшее целое q, такое, что . Известно, что , здесь log2B является константой при фиксированном В. Таким образом, число символов, необходимых для представления целого числа n есть 0(log2n).
Временная сложность вычислений (алгоритма)
Временная сложность вычислений (алгоритма) характеризует число операций для решения задачи заданного размера.
При решении однотипных задач с одинаковым размером входа может потребоваться различное число итераций для решения отдельных задач (этого типа), следовательно, и различное число операций
Полиномиальные алгоритмы и задачи
Считается, что алгоритм полиномиальный или имеет полиномиальную временную сложность, если существует полином p(x) такой, что на любом входном слове длины n алгоритм завершает вычисления после выполнения не более чем p(n) операций.
Не детерминированные машины Тьюринга, отличительные свойства от
детерменированных.
Свойства полных задач класса NP.
Класс NP- полных задач обладает следующими свойствами.
1. Никакую NP-полную задачу нельзя решить никаким известным полиномиальным алгоритмом, несмотря на настойчивые усилия многих блестящих исследователей.
2. Если бы удалось построить полиномиальный алгоритм для какой-нибудь NP-полной задачи, то это бы означало полиномиальную разрешимость каждой NP-полной задачи.