Операция минимизации

Операция минимизации имеет один операнд, . Значения функции на заданном наборе аргументов получаются следующим образом. Сначала с помощью функции формируется уравнение , а затем отыскивается его решение . Если таких решений несколько, то берется минимальное из них; оно и считается значением функции на данном наборе аргументов. Может случится, что уравнение не имеет ни одного решения. В этом случае считается, что функция не определена на заданном наборе аргументов.

Оператор минимизации может превратить всюду определенную функцию в частичную.

Множество функций, получаемых применением к базовому набору конечного числа операций типа суперпозиции, примитивной рекурсии и минимизации называется множеством частично-рекурсивных функций и обозначается .

Примеры определения функций при помощи этих трех операций:

1)

2)

3)

5) Проблема алгоритмической разрешимости. Примеры неразрешимых алгоритмических проблем.

В математической логике и теории алгоритмов под разрешимостью подразумевают свойство формальной теории обладать алгоритмом, определяющим по данной формуле, выводима она из множества аксиом данной теории или нет. Теория называется разрешимой, если такой алгоритм существует, и неразрешимой, в противном случае. Вопрос о выводимости в формальной теории является частным, но вместе с тем, важнейшим случаем более общей проблемы разрешимости.

Факт алгорифмической неразрешимости доказал в 1970 году российский математик Ю.В. Матиясевич.

Задачи, для которых не существует алгоритма, решающего ее, называют алгорифмически неразрешимыми. но аглорифмическая неразрешимость некоторой общей задачи не означает, что не могут быть созданы алгоритмы, решающие частные случаи задачи.

В теории вычислимости алгоритмически неразрешимой задачей называется задача, имеющая ответ да или нет для каждого объекта из некоторого множества входных данных, для которой (принципиально) не существует алгоритма, который бы, получив любой возможный в качестве входных данных объект, останавливался и давал правильный ответ после конечного числа шагов.

Проблема умирающей матрицы: для данного конечного множества квадратных матриц n × n определить, существует ли произведение всех или некоторых из этих матриц (возможно, с повторениями) в каком-либо порядке, дающее нулевую матрицу. Проблема неразрешима даже для n=3 (разрешимость для n=2 является открытым вопросом^[2])

6) Методы разработки алгоритмов. Суперпозиция, итерация, рекурсия.

Ключевым подходом в алгоритмизации является сведение задачи к подзадачам, а способ такого сведения определяет метод разработки алгоритмов.

1. Суперпозиция – самый простой метод. Состоит в том, что решение сложной задачи представляется как последовательное решение более простых задач, при этом результат решения предыдущей задачи используется в качестве входных данных для решения следующей задачи.

Разбивать задачу на подзадачи, можно:

1) разбивать исходные и выходные данные на части и упрощать их; под разбиением понимаем разделение структуры данных на части, например, разделение вектора из десяти компонент на два по пять компонент или разделение текста на предложения; под упрощением понимаем такие ситуации, когда, например X – число и его нельзя разбить на части, но его можно разложить в сумму X=X₁+X₂, так, что результаты f(X₁) и f(X₂), отыскиваются проще, чем 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) Технологии разработки программ. Технологии и методы тестирования программ.

1. Постановка задачи - составление точного и понятного словесного описания того, как должна работать будущая программа, что должен делать пользователь в процессе ее работы.
2. Разработка интерфейса (интерфейс - способ общения) - создание экранной формы (окна программы).
3. Составление алгоритма.
4. Программирование - создание программного кода на языке программирования.
5. Отладка программы - устранение ошибок.
6. Тестирование программы - проверка правильности ее работы.
7. Создание документации, помощи.

Качество (программных средств) можно определить как совокупную характеристику исследуемого ПО с учётом следующих составляющих:

· Надёжность

· Сопровождаемость - процесс улучшения, оптимизации и устранения дефектов программного обеспечения (ПО) после передачи в эксплуатацию

· Практичность

· Эффективность

· Мобильность

· Функциональность

8) Рекурсивные алгоритмы: определение и виды рекурсии. Реализация рекурсии и использование стека. Рекурсия и итерация. Примеры, сравнение.

Алгоритм называется рекурсивным, если:

1. хотя бы один шаг этого алгоритма представляет собой обращение к себе. Под обращением будем понимать передачу управления или вызов. В этом случае речь идет о прямой рекурсии.

2. хотя бы один шаг этого алгоритма представляет собой обращение к , который в свою очередь вызывает . Такая рекурсия называется косвенной.