| [Оглавление] | [<< страница] | [>>страница] |
Решение задачи с помощью ЭВМ — это процесс автоматического преобразования исходной информации (исходных данных) в искомый результат в соответствии с заданной последовательностью действий, называемой алгоритмом.
Алгоритм — одно из основных понятий математики, которое невозможно строго определить, а можно лишь пояснить с помощью других слов. Можно сказать, что алгоритм — это точное предписание, которое задает вычислительный процесс, начинающийся из некоторой совокупности возможных для этого алгоритма исходных данных и направленный на получение полностью определяемого этими исходными данными результата.
Алгоритмы должны обладать следующими свойствами:
Основными этапами подготовки задачи к решению на ЭВМ, которые связаны с построением алгоритма, являются:Постановка задачи. Она позволяет точно сформулировать и понять задачу. В первую очередь необходимо установить, имеет ли исходная задача решение. Далее следует выяснить, нельзя ли данную задачу решить посредством готовых прикладных программ (приложений), таких, как электронные таблицы, системы управления базами данных и т.п.
На этапе постановки задачи мы должны получить ответ на следующие вопросы: что дано? достаточно ли исходных данных? нет ли избыточных? какие результаты должны быть получены? какие сделаны допущения? Поскольку решаемая задача относится к некоторой области реального мира (предметной области), мы должны выделить эту область, игнорируя некоторые ее свойства и характеристики, не свойственные с точки зрения рассматриваемой задачи. Так мы получаем абстракцию некоторого фрагмента реального мира, т.е. упрощаем факты до такой степени, что обработка абстрактных данных позволит получить желаемый ответ (результаты) по рассматриваемой проблеме.
На этом этапе предметную область мы видим глазами пользователя, специалиста по данной предметной области, естественно, и данные представляются в понятиях и обозначениях этой области. Это внешний уровень представления данных. Для решения же задачи на ЭВМ эти данные должны быть представлены в машинном виде, на физическом уровне.
Каждая модель ЭВМ имеет свою систему команд и ограниченный состав базовых данных, а также форматы их представления. В качестве базовых данных обычно используются двоичные и десятичные числа с фиксированной запятой, числа с плавающей запятой, символы и т.д. Формат данных определяет, какой размер памяти занимают отдельные данные, как трактуются отдельные части и данные в целом. Различают форматы данных фиксированной длины (один или несколько байтов) и переменной длины, в любом случае данные размещаются в одной или нескольких смежных ячейках (байтах). Система команд определяет состав операций, выполняемых в ЭВМ над данными. Нас не интересует, на каком уровне — аппаратном или микропрограммном они выполняются. Каждая команда также имеет свой формат длиной в один или несколько байтов.
В ячейках памяти размещаются либо данные, либо команды (коды программы). Таким образом, каждая ячейка имеет свой адрес и некоторое содержимое. По содержимому ячейки невозможно определить, что там хранится: данные, команда или их части. Например, содержимое байта '0011000 Г может трактоваться как символ Т, десятичное число 31, двоичное число, равное 49, и т.д. Из вышеизложенного следует, что в модели ЭВМ на машинном уровне определены только базовые типы данных, которые, естественно, в большинстве случаев не совпадают с типами данных, полученными при абстрагировании. Следовательно, существует разрыв между двумя уровнями представления данных. Этот разрыв постепенно устраняется на последующих этапах подготовки к решению задачи.
Построение модели задачи. После того как получена четкая постановка задачи, нужно подобрать или разработать формальную модель задачи, привлекая достижения современных наук. Выбранная модель существенно влияет на все последующие этапы. Выбор модели в высокой степени зависит от подготовленности, знаний, эрудиции, опыта разработчиков. Здесь нужно установить, какие структуры данных больше всего подходят нашей задаче с точки зрения удобства представления и простоты решения. Под структурой данных понимаем организованную некоторым образом информацию, которая может быть описана, создана и обработана в программах. Теперь на данные решаемой задачи начинаем смотреть с учетом их обработки на машине. Следовательно, в разработке формальной модели задачи при активном взаимодействии должны участвовать специалисты по предметной области и программисты в широком смысле этого слова.
Имеется большое число абстрактных структур, разработанных и детально изученных поколениями ученых. Рассмотрены способы их представления, области рационального применения, основные операции над ними и предложены всевозможные алгоритмы выполнения этих операций. Абстрактные данные, полученные на этапе постановки задачи, теперь конкретизируются и представляются с использованием подходящих структур.
Разработка алгоритма. Методы и алгоритмы решения задачи ищутся и разрабатываются в рамках построенной формаль¬ной модели задачи. При этом необходимо выяснить, существуют ли решения аналогичных или похожих задач, т.е. руководствоваться накопленным опытом, что позволяет значительно сократить сроки разработки и уменьшить требуемые расходы.
На этом этапе выделяются так называемые абстрактные типы данных (АТД), которые определяют организацию (структуру) и область значений конкретных данных задачи и операции над этими данными. АТД позволяют сосредоточиться на идеализированных моделях данных и операциях над ними и отвлечься от программной реализации. В то время как над базовыми типами данных, представленными на машинном уровне, выполняются простые машинные операции, операции над АТД являются достаточно сложными и, как правило, реализуются отдельными процедурами (функциями). Разработка алгоритмов таких процедур облегчается, если АТД представлены с использованием абстрактных структур, упомянутых выше.
Реализация алгоритма в виде программы. Это довольно трудный этап: сначала нужно выбрать язык или языки программирования. При этом необходимо учесть, что каждый язык поддерживает одну или несколько парадигм программирования.
Парадигмы программирования — это модели разработки и реализации программ. Разные модели приводят к разным приемам программирования, они обычно не противоречат друг другу, а являются взаимодополняющими. Общим для всех моделей является то, что разработка программы базируется на абстракциях, соответствующих элементам решаемой задачи, а реализация представляет собой совокупность модулей. Различие моделей состоит в том, как формировать абстракции и что содержит модуль.
Язык процедурного программирования базируется на модели построения программы как совокупности функций, а абстракция данных базируется на структурах данных. Объектно- ориентированное программирование базируется на модели построения программ как набора объектов абстрактного типа данных. В каждом языке программирования имеются средства представления данных различных ти-пов. Тип данных определяет, какие значения могут принимать данные этого типа и допустимые операции над ними; Абстрактные типы данных, определенные на этапах разработки модели и алгоритма, представляются теперь средствами языка программирования в виде синтаксических конструкций, т.е. получают программную реализацию. Это промежуточный уровень представления данных. Затем в результате трансляции программы данные представляются в виде последовательностей битов — это физический уровень представления данных. Таким образом, в процессе последовательных преобразований структуры данных из одного вида представления переводятся в другие (рис. 1.):
Рис.1.Уровни представления данных
Окончательная структура данных определяется программистами на промежуточном уровне, поскольку данные, представленные в программе, однозначно переводятся транслятором в двоичные коды и образуют структуры хранения данных.
Проверка правильности алгоритма. Она выполняется на различных этапах. На этапе разработки алгоритма доказывается правильность каждого шага алгоритма, затем доказывается конечность алгоритма, проверяются допустимые входные данные и полученные по ним выходные данные. На этапе программной реализации алгоритма необходимо следить за тем, чтобы в процессе преобразования правильного алгоритма получить правильную программу.
Правильностью (корректностью) программы называют свойство программы, характеризующее отсутствие в ней ошибок по отношению к целям разработки [35]. Каждая программа определяется правилами ее представления (синтаксисом языка программирования) и правилами интерпретации ее содержательного значения (семантикой). Корректная программа может быть создана только при строгом соотношении этих правил. Задача определения синтаксической правильности решается транслятором автоматически в ходе трансляции программы. Проблема доказательства семантической правильности оказывается значительно сложнее, так как процедура доказательства существенно зависит от решаемой задачи и исходных данных. Формализованное описание постановки задачи называют спецификацией задачи. Область науки об информатике, занимающаяся доказательством соответствия между программной реализацией и спецификацией задачи, получила название верификации программ. Цель верификации программ — демонстрация корректности программ. Определенные успехи, достигнутые в автоматизации верификации программ, пока не дошли до широкого практического применения.
Семантическая правильность программы традиционно проверяется путем ее тестирования. Тестирование — это процесс выполнения программы с целью нахождения ошибок. Однако выполнить всестороннее тестирование сложной программы во всех диапазонах исходных данных и при всех их сочетаниях практически невозможно.
Анализ сложности алгоритма. Алгоритму решения задачи предъявляются два противоречивых требования:
Несмотря на то, что объемы памяти и быстродействие ЭВМ выросли колоссально, такой подход к оценке эффективности продолжает оставаться справедливым.
Какому из этих требований отдать предпочтение, определяется характером решаемой задачи. Если программа выполняется несколько раз, а время выполнения для пользователя несущественно, то разумнее отдать предпочтение первому требованию, так как стоимость создания программы намного дороже стоимости машинного времени, затрачиваемого на решение задачи.
Если же задача для своего решения требует значительных вычислительных ресурсов, выполняется многократно либо время решения ограничено внешними событиями как в системах реального времени, то требование эффективности становится более важным. Обычно эффективные алгоритмы реализуются более сложными программами, поэтому желательно, чтобы такие программы по возможности были простыми в сопровождении. С одной стороны, целью анализа алгоритма является получение оценок (границ) для объема памяти или времени работы, которое потребуется алгоритму для обработки конкретных данных. С другой стороны, для решения одной и той же задачи могут быть использованы различные по эффективности алгоритмы. Тогда по результатам анализа выбирается наиболее эффективный из них.
При анализе с задачей связывается некоторое число, называемое размером задачи, которое выражает меру количества (объема) исходных данных. В качестве размера могут выступать размеры массивов, число вершин или дуг графа, число записей в файле и т.п. Время выполнения программы Т(п) зависит от размера п, единица измерения Т(п) не определена. Традиционно определяют время выполнения Т(п) в наихудшем случае как меру сложности алгоритма.
Время, затрачиваемое алгоритмом на его выполнение как функция размера задачи, называется временной сложностью этого алгоритма. Поведение этой сложности в пределе при увеличении размера задачи и называется асимптотической временной сложностью. Аналогично определяются емкостная сложность и асимптотическая емкостная сложность. Асимптотическая сложность алгоритма в конечноц счете и определяет размер задач, которые можно решить с помощью этого алгоритма.
Если алгоритм Л имеет время выполнения ТА(п) = сп1, а алгоритм В — Т(п) = kdn, где с, d,k — константы, то в зависимости от их соотношения может оказаться, что для малых п более эффективным является алгоритм В, в то же время очевидно, что для больших я более эффективным будет алгоритм А. Это связано с тем, что функций ТА(П) и ТB(п) имеют различные скорости роста.
Для описания скорости роста функций используется 0-символика. Так, Т(п) = О(пА) означает, что время выполнения программы Т(п) имеет порядок О(п ) и подразумевается, что существуют положительные константы с и n0 такие, что для всех n, больших или равных n0, выполняется неравенство T(п)≤ сп2. Аналогично T(п) имеет порядок O(f(n)), если существуют константы с и n0, такие, что для всех п = n0 выполняется неравенство Т(п)≤cf(n), тогда f(n) определяет степень роста. Говорят, что f(n) является верхней границей сложности задачи. Если мы пытаемся улучшить алгоритм с целью снизить время выполнения задачи, то возникает вопрос, где необходимо остановиться, так как дальнейшее улучшение невозможно, т,е. найти нижнюю границусложности алгоритма. Определение нижней границы вызывает существенные затруднения и потому редко выполняется.
Определим сложность алгоритма сортировки методом пузырька массива А с п элементами. Основу алгоритма составляет двойной цикл.
for (i=0; i<n-1; i++)
for(j=n-1;j<i;j--)
If (А[j]<А[j-1])
<перестановка элементов A[j] и А[j-1]>
Перестановка элементов требует фиксированного времени. Для каждого i, устанавливаемого внешним циклом поi, внутренний цикл по j выполняется (n-i) раз, общее количество шагов определяется суммой
Следовательно, в худшем случае количество перестановок равно этому же значению. Таким образом, алгоритм метода пузырька имеет временную сложность О(п2), если даже в некоторых шагах (или даже всех) перестановок элементов не будет.
Если при некотором i не будет ни одной перестановки, то это означает, что массив уже отсортирован и процесс сортировки можно прекратить. Для этого достаточно ввести управляющий переключатель р, который устанавливается в нуль" в начале внешнего цикла. Если во внутреннем цикле перестановок не было, его значение не изменяется, и по этому признаку осуществляется выход из внешнего цикла. Очевидно, что временная сложность будет равна 0(l), если исходный массив был отсортирован, и О(n2)— в худшем случае, когда массив был отсортирован в обратном порядке.
При вычислениях времени выполнения программ с применением О - символики пользуются правилами сумм и произведений.Правило сумм заключается в следующем. Пусть время выполнения двух фрагментов программы Т1(п) и Т2(п) имеет порядок O(f11(n)) и O(f2(n)) соответственно. Время последовательного выполнения этих фрагментов вычисляется как Т1(п) + Т2(п) = O(f1(n)) + О(f2(n)) и имеет порядок 0(max(f1(n), f2(n))) По правилу произведений: Т1(п) • Т2(п) = O(f1(n)*f2(n)). Тогда с применением этих правил можно определить время выполнения операторов базовых структур программ.
При анализе сложности алгоритмов вводится понятие детерминированных и недетерминированных алгоритмов. В каждый момент времени выполнения алгоритм находится в некотором определенном состоянии. Состояние определяется совокупностью значений обрабатываемых данных и выполняемым действием. Свойство детерминированности означает, что для каждого имеющегося в данный момент состояния либо существует в точности одно следующее состояние, либо не существует никакого следующего — это заключительное состояние.
Пусть теперь для любого состояния алгоритма возможно иметь более одного следующего. Когда детерминированный алгоритм доходит до того места, где требуется выбрать одну из альтернатив, он исследует их последовательно друг за другом и выбирает одинединственный. Недетерминированный алгоритм просматривает все альтернативы не последовательно, а все их одновременно, копируя самого себя. Эти копии, в свою очередь, могут порождать новые копии и т.д. Все копии продолжают выполняться все вместе до тех пор, пока одна или несколько из них не найдут решения, после этого останавливаются все копии.
Все задачи, которые могут быть решены с помощью детерминированного алгоритма за полиномиальное время, образуют, один класс, класс Р - задач, и считаются легко разрешимыми. Задача, сложность которой не менее fn (где f — константа, или полином от n), считается экспоненциальной и относится к классу Е. При небольших значениях п экспоненциальный алгоритм, как отмечалось выше, может быть более «быстрым», чем полиномиальный. Но различие между этими алгоритмами при больших значениях п проявляется всегда.
Есть задачи, которые не попадают ни в класс Р, ни в класс Е. В настоящее время для этих задач не найдено полиномиального алгоритма. Доказано, что они являются взаимно эквивалентными. Это означает, что если бы для одной из них удалось найти полиномиальное решение, то все они также получили бы полиномиальное решение.
Задачи, которые могут быть решены с помощью недетерминированного алгоритма за полиномиальное время, относятся к классу NP-задач. Очевидно, что P?NP, т.е. каждая задача, разрешимая по детерминированному алгоритму за полиномиальное время, также разрешима за полиномиальное время по недетерминированному алгоритму. Истинность обратного утверждения не доказана. Она является одним из неразрешенных вопросов современной математики и информатики.
А теперь, кратко рассмотрим вопросы, относящиеся к NP-задачам.
Определение 1. Задача Q сводится к задаче R тогда и только тогда, когда для всякого решения s задачи R существует функция g(s), которую можно вычислить полиномиально и которая является решением задачи Q (Q—>R). Это означает, что если мы умеем решать задачу R, то мы умеем решать и задачу Q.
Определение 2. Если одновременно Q->R и R->Q, то говорят, что Q и R эквивалентны.
(Определение 3. Задача называется NP-сложной (NP-трудной) тогда и только тогда, когда к ней сводима любая задача из класса NP. Сама NP-сложная задача может принадлежать как к классу Р, так и к классу NP.
Определение 4. Задача называется NP-полной в том и только в том случае, если она является NP-сложной и попадает в класс NP. Задача разрешимости логического выражения заключается в следующем. Пусть дано выражение Е, которое включает логические операторы ИЛИ, И, НЕ и логические переменные q1, q2,,…qn. Нужно найти такие значения переменных qi чтобы при этих значениях выражение E(q1,q2,..., qn) было истинным. Эта задача попадает в класс NP.
В 1971 г. Куком была доказана теорема: задача разрешимости логического выражения является NP-сложной.
Так как задача разрешимости принадлежит к классу NP, то она является NP-полной.
Данная теорема утверждает, что решение любой задачи из класса NP может быть получено из решения задачи разрешимости путем некоторой трансформации, которая тоже полиномиальна. Иначе, для решения произвольной задачи класса NP достаточно уметь решать задачу разрешимости. Трудность заключается в том, что мы не умеем как следует решать задачу разрешимости.
В настоящее время доказано, что большинство действительно сложных классических задач принадлежит к классу NP-сложных, и, более того, они являются NP-полными. В этом смысле все они эквивалентны. Поэтому если бы мы умели решать одну из них за полиномиальное время, то мы смогли бы решать все задачи этого класса также за полиномиальное время.
Относительно NP-полных задач можно сказать, что, во-первых, мы не знаем, являются ли они не полиномиальными и, во-вторых, не знаем детерминированного полиномиального алгоритма для их решения. Но в конкретных случаях можно использовать принципы моделирования и преобразования условий. Даже если некоторая общая задача Q принадлежит к классу NP-полных задач, то любая конкретная задача с уточненными данными может быть все-таки решена, возможно, даже за полиномиальное время. Единственное, что вытекает из теории, это то, что для общего случая не существует единого полиномиального алгоритма.
| [Оглавление] | [<<страница] | [>>страница] | [В начало ] |