![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
В предикатной логике, квантор существования (экзистенциальный квантификатор) — это предикат свойства или отношения для, по крайней мере, одного элемента области определения. Он обозначается как символ логического оператора ∃ (произносится как «существует» или «для некоторого»). Квантор существования отличается от квантора всеобщности, который утверждает, что свойство или отношение выполняется для всех элементов области.
Квантор всеобщности (обозначения: , ∀) — это условие, которое верно для всех обозначенных элементов, в отличие от квантора существования, где условие верно только для каких-то отдельных из указанных чисел. Формально говоря, это квантор, используемый для обозначения того, что множество целиком лежит в области истинности указанного предиката. Читается как: «для всех…», «для каждого…» или «каждый…», «любой…», «для любого…».
Эквивалентные отношения в логике предикатов см. тетрадь.
Понятие алгоритма. Неформальное (интуитивное) определение алгоритма. Примеры алгоритмов. Основные свойства алгоритмов. Роль алгоритмов в информатике. Алгоритмические проблемы. Машина Тьюринга - описание и примеры. Рекурсивные функции.
Алгори́тм — набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное число действий.
Рассмотрим пример алгоритма для нахождения середины отрезка при помощи циркуля и линейки.
Алгоритм деления отрезка АВ пополам:
1) поставить ножку циркуля в точку А;
2) установить раствор циркуля равным длине отрезка АВ;
3) провести окружность;
4) поставить ножку циркуля в точку В;
5) провести окружность;
6) через точки пересечения окружностей провести прямую;
7) отметить точку пересечения этой прямой с отрезком АВ.
Основными свойствами алгоритма являются:
1. детерминированность (определенность). Предполагает получение однозначного результата вычислительного процecca при заданных исходных данных. Благодаря этому свойству процесс выполнения алгоритма носит механический характер;
2. результативность. Указывает на наличие таких исходных данных, для которых реализуемый по заданному алгоритму вычислительный процесс должен через конечное число шагов остановиться и выдать искомый результат;
3. массовость. Это свойство предполагает, что алгоритм должен быть пригоден для решения всех задач данного типа;
4. дискретность. Означает расчлененность определяемого алгоритмом вычислительного процесса на отдельные этапы, возможность выполнения которых исполнителем (компьютером) не вызывает сомнений.
Понятие алгоритма — одно из основных в программировании и информатике. Это последовательность команд, предназначенная исполнителю, в результате выполнения которой он должен решить поставленную задачу. Алгоритм должен описываться на формальном языке, исключающем неоднозначность толкования. Запись алгоритма на формальном языке называется программой. Иногда само понятие алгоритма отождествляется с его записью, так что слова «алгоритм» и «программа» — почти синонимы. Небольшое различие заключается в том, что под алгоритмом, как правило, понимают основную идею его построения. Программа же всегда связана с записью алгоритма на конкретном формальном языке.
Перечислим некоторые важные алгоритмические проблемы.
1. Проблема самоприменимости. Существует ли алгоритм, позволяющий по произвольному натуральному числу x отвечать на вопрос: " сходится ли j x(x)?". Согласно тезису Чёрча-Клини эту проблему можно переформулировать в следующей эквивалентной форме: " существует ли общерекурсивная функция g0 такая, что g0«1, если jx(x) сходится и g0«0, если jx(x) расходится?".
2. Проблема остановки [Роджерс,1972,с.43]. Существует ли алгоритм, позволяющий по произвольной паре натуральных чисел (x,y) отвечать на вопрос: " Сходится ли jx(y)?". Согласно тезису Чёрча-Клини эту проблему можно переформулировать в следующей эквивалентной форме: " существует ли общерекурсивная функция g от двух переменных такая, что g(x,y)«1, если jx(y) расходится и g(x,y)«0, если jx(y) расходится?".
3. Проблема общерекурсивности [Роджерс,1972,с.45]. Существует ли алгоритм, позволяющий по произвольному натуральному числу x отвечать на вопрос: " Является ли n-местная функция jx общерекурсивной?". Согласно тезису Чёрча-Клини эту проблему можно переформулировать в следующей эквивалентной форме: " Существует ли общерекурсивная функция t(x) такая, что t(x)«1, если jx - n-местная общерекурсивная функция и t(x)«0 в противном случае?".
Машина Тьюринга:
Дата публикования: 2014-11-03; Прочитано: 2445 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!