![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Операция минимизации
Операция минимизации Оператор минимизации может превратить всюду определенную функцию в частичную. Множество функций, получаемых применением к базовому набору Примеры определения функций при помощи этих трех операций: 1)
3)
5) В математической логике и теории алгоритмов под разрешимостью подразумевают свойство формальной теории обладать алгоритмом, определяющим по данной формуле, выводима она из множества аксиом данной теории или нет. Теория называется разрешимой, если такой алгоритм существует, и неразрешимой, в противном случае. Вопрос о выводимости в формальной теории является частным, но вместе с тем, важнейшим случаем более общей проблемы разрешимости.
Факт алгорифмической неразрешимости доказал в 1970 году российский математик Ю.В. Матиясевич.
Задачи, для которых не существует алгоритма, решающего ее, называют алгорифмически неразрешимыми. но аглорифмическая неразрешимость некоторой общей задачи не означает, что не могут быть созданы алгоритмы, решающие частные случаи задачи.
В теории вычислимости алгоритмически неразрешимой задачей называется задача, имеющая ответ да или нет для каждого объекта из некоторого множества входных данных, для которой (принципиально) не существует алгоритма, который бы, получив любой возможный в качестве входных данных объект, останавливался и давал правильный ответ после конечного числа шагов.
Проблема умирающей матрицы: для данного конечного множества квадратных матриц n × n определить, существует ли произведение всех или некоторых из этих матриц (возможно, с повторениями) в каком-либо порядке, дающее нулевую матрицу. Проблема неразрешима даже для n=3 (разрешимость для n=2 является открытым вопросом[2])
6) Ключевым подходом в алгоритмизации является сведение задачи к подзадачам, а способ такого сведения определяет метод разработки алгоритмов.
1. Суперпозиция – самый простой метод. Состоит в том, что решение сложной задачи представляется как последовательное решение более простых задач, при этом результат решения предыдущей задачи используется в качестве входных данных для решения следующей задачи. Разбивать задачу на подзадачи, можно: 1) разбивать исходные и выходные данные на части и упрощать их; под разбиением понимаем разделение структуры данных на части, например, разделение вектора из десяти компонент на два по пять компонент или разделение текста на предложения; под упрощением понимаем такие ситуации, когда, например X – число и его нельзя разбить на части, но его можно разложить в сумму X=X1+X2, так, что результаты f(X1) и f(X2), отыскиваются проще, чем f(X). 2) производить декомпозицию функции f, т.е превращать ее в суперпозицию более простых, f(X)=g(h(s(X))) или f(X)=g(X, h(X), s(X)) На практике используется совмещение этих методов. 2. Итерация – частный случай предыдущего метода. f(X)=g(g(g(g(X))) или f(X)=g(X, s(X), s(X), s(X)) Однородность подзадач позволяет значительно сократить длину текста алгоритма за счет применения операторов повторения (циклов). 3. Метод последовательного приближения Частный случай итерации. Сначала каким-либо образом угадывается значение 4. Метод обратной функции Иногда обратная задача решается значительно более просто, чем исходная. Тогда имеющийся алгоритм решения обратной задачи, можно использовать для решения прямой задачи.
5. Рекурсия При использовании рекурсии решение задачи сводится к решению той же самой задачи, но на более простом входном наборе данных. При этом появляется необходимость в дополнительных вычислениях, связанных со сведением одного набора данных к другому. При вычислении рекурсивной функции всегда выделяется рекурсивная и не рекурсивная части.
6. Метод полного перебора Метод полного перебора применим в тех случаях, когда решение принадлежит некоторой конечной области и может быть найдена простая функция для проверки выбранного решения. Сложность заключается в том, что при увеличении количества исходных данных быстро увеличивается необходимое число проверок.
7)
Качество (программных средств) можно определить как совокупную характеристику исследуемого ПО с учётом следующих составляющих: · Надёжность · Сопровождаемость - процесс улучшения, оптимизации и устранения дефектов программного обеспечения (ПО) после передачи в эксплуатацию · Практичность · Эффективность · Мобильность · Функциональность
8) Алгоритм 1. хотя бы один шаг этого алгоритма представляет собой обращение 2. хотя бы один шаг этого алгоритма представляет собой обращение
|