Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Что подразумевается под термином Алгоритм. Основные требования для
создания алгоритма.
алгоритм – это однозначно трактуемая процедура, осуществляемая черным ящиком для получения выхода из входа. Чтобы создать алгоритм необходимо знать:
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-полной задачи.