Сдам Сам

ПОЛЕЗНОЕ


КАТЕГОРИИ







Понятие алгоритма. Свойства алгоритмов





Понятие алгоритма. Свойства алгоритмов

Алгоритм, алгоритмизация, алгоритмический язык............................................................................ 1

Свойства алгоритмов......................................................................................................................................................... 5

Управляющие структуры и основные конструкции алгоритмов........................................................................ 6

Неформальные описания алгоритмов............................................................................................................... 9

Сортировка методом простого выбора............................................................................................................................ 9

Сортировка в интегрированных пакетах....................................................................................................... 10

Сортировка в приложении Word....................................................................................................................................... 10

Сортировка в приложении Excel....................................................................................................................................... 11

Алгоритмы генерации случайных чисел...................................................................................................... 12

Сложность алгоритмов.................................................................................................................................................. 13

Технологии (парадигмы) программирования............................................................................................ 18

Процедурное программирование...................................................................................................................................... 18

Функциональное программирование............................................................................................................................. 19

Логическое программирование......................................................................................................................................... 19

Объектно-ориентированное программирование....................................................................................................... 19

Визуальное программирование........................................................................................................................................ 20

Языки программирования баз данных.............................................................................................................. 20

Языки программирования для компьютерных сетей........................................................................ 21

Инженерия программного обеспечения........................................................................................................ 21

Принцип программного управления.................................................................................................................. 21

 

Свойства алгоритмов

Алгоритм должен удовлетворять следующим свойствам:

- массовость;

- применимость;

- детерминированность;

- результативность;

- оптимальность.

Массовость алгоритма означает, что алгоритм устанавливает порядок решения не только одной частной задачи, а целого класса однотипных задач при различных начальных условиях.

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

Детерминированность алгоритма означает, что результат алгоритма определен однозначно, т.е. детерминированность означает возможность многократного получения одного и того же результата по одному и тому же алгоритму и при одних и тех же исходных данных.

Результативность означает, что алгоритм должен завершаться за конечное число шагов.

Оптимальность определяется по времени и по памяти.

Неформальные описания алгоритмов

В качестве примеров даётся ряд неформальных описаний алгоритмов.

Пример. Методы сортировки.

Рассмотрим задачу сортировки на частном примере. Пусть имеет N чисел. Требуется отсортировать, т.е. упорядочить эти числа таким образом, чтобы они образовывали монотонную (возрастающую или убывающую) последовательность.

Рассмотрим следующие алгоритмы сортировки:

- сортировка пузырьком;

- сортировка методом простого выбора;

- сортировка слиянием.

Сортировка методом простого выбора

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

Алгоритм S.

Обозначим исходную последовательность чисел K1, K2, …, Kn, а результирующую последовательность R1, R2, …, Rn.

S1. [Цикл по j]. Выполнить шаги S2 и S3 при j=N, N-1, …, 2.

S2. [Найти max[K1, …, Kj]. Найти наибольшее из Kj, Kj-1, …,K1. Пусть это будет Ki.

S3. [Присвоить Rj]. Значение Ki присвоить Rj.

 
 

 


K             R        
j=N=5                     N=5
j=4                      
j=3                      
j=2                      
j=1                      
                       

 

Блок-схема алгоритма сортировки методом простого выбора

 

 

Запишем алгоритм S на псевдокоде

procedure (K1, K2, …, Kn: integer, R1, R2, …, Rn: integer)

begin

for j=N to 2

R[j]:=max(K1, K2, …, Kj); max – является наибольшим числом

R[1]:=K[1]

end;

 

Сортировка в интегрированных пакетах

Поскольку нас интересуют практические аспекты информатики, то необходимо знать, как решить задачу сортировки в пределах имеющейся компетенции. Решение задачи сортировки предлагают в пакете Microsoft Office приложения Word и Excel.

Сортировка в приложении Word

  1. Выделить фрагмент документа.
  2. Меню Таблица, пункт Сортировка.
  3. Задать параметры сортировки в окне, появляющегося по действию в предыдущем пункте, указав, в частности элемент сортировки (например, абзац)

Сортировку надо выполнять, когда необходимо, например, расположить по алфавиту список слов.

Сложность алгоритмов

Когда мы считаем, что алгоритм обеспечивает удовлетворительное решение проблемы? Во-первых, он должен всегда давать правильный ответ. Во-вторых, он должен быть эффективным. Каким образом может быть проанализирована эффективность. Первой мерой эффективности является время, используемое компьютером для решения проблемы при использовании данного алгоритма когда входные данные являются определённого размера. Второй мерой эффективности является количество компьютерной памяти для применения алгоритма для входных данных определённого размера. Подобные вопросы образуют вычислительную сложность алгоритма. Различают два вида сложности алгоритмов: сложность по времени или временная сложность и сложность по памяти.

Временная сложность является показателем быстродействия работы алгоритма.

Сложность по памяти показывает потребности в оперативной памяти при работе алгоритма.

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

Рассмотрение сложности по памяти связано с конкретными структурами данных применяемых в алгоритме. Поскольку структуры данных детально рассматриваться не будут, то не будут и рассматриваться вопросы сложности по памяти. Поэтому мы ограничимся временной сложности.

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

Каковы единицы измерения времени выполнения алгоритма? Для этого можно просто вос­пользоваться — секундой, милли­секундой и т.д. и с их помощью оценить время выполнения программы, реализующей рассматриваемый алгоритм. Однако у такого подхода существуют явные недостатки -определение единиц измерения времени выполнения алгоритма через единицы измерения времени имеет недостатки, поскольку результаты измерений будут зависеть от:

- быстродействия конкретного компьютера;

- тщательности реализации алгоритма в виде программы;

- типа компилятора, использованного для генерации машинного кода;

- точности хронометрирования реального времени выполнения про­
граммы.

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

Один из возможных способов решения этой проблемы состоит в подсчете то­го, сколько раз выполняется КАЖДАЯ операция алгоритма. Однако подобный подход слишком сложен и, как мы увидим в дальнейшем, чаще всего не нужен. Поэтому мы должны составить список наиболее важных операций, выполняемых в ал­горитме, называемых основными, или базовыми операциями (basic operation), определить, какие из них вносят наибольший вклад в общее время выполнения алгоритма, и вычислить, сколько раз эти операции выполняются.

Как правило, составить список основных операций алгоритма совсем нетруд­но. Обычно в него включают наиболее длительные по времени операции, выпол­няемые во внутреннем цикле алгоритма. Например, в большинстве алгоритмов сортировки используется метод сравнения двух элементов (ключей) списка, ко­торый сортируется. Для подобного типа алгоритмов основной является операция сравнения ключей. В качестве еще одного примера рассмотрим алгоритмы пере­множения матриц и вычисления значения многочлена. В них используются две основные операции: умножение и сложение. На большинстве компьютеров коман­да умножения двух целых чисел выполняется намного дольше, чем сложение. Поэтому она является безусловным кандидатом на включение в список основных операций.

Таким образом, временная сложность алгоритмов определяется количеством основных операций, при работе алгоритма с входными данными размерности n.

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

Далее заметим, что при малых размерах входных данных невозможно заметить разницу во времени выполнения между эффективным и неэффективным алгоритмом. Для описания временной сложности алгоритмов используют три условных обозначения: О (прописная «О»), W (прописная греческая «омега») и Q (прописная греческая «тета»).

Пусть t(n) и g(n) ‑ неотрицательные функции, определенные на множестве натуральных чисел. Обозначим через t(n) время выполнения алгоритма, выраженное в виде числа основных операций алгоритма, а через g(n) некоторую функцию, с которой будет сравниваться t(n).

Говоря нестрого, обозначение О(g(n)) — это множество всех функций t(n), порядок роста которых при достаточно больших п не превышает (т.е. меньше или равен) некоторую константу, умноженную на значение функции g (n). Графически:

Например:


Принято выделять следующие классы временной сложности алгоритмов

Класс Название
О (1) константа
О (log n) логарифмическая
О (n) линейная
О (nlog n) n-логарифмическая
О (nm) Степенная
О (2n) Экспоненциальная
О (n!) Факториальная

 

Так, например, алгоритм, выполняющий только операции чтения данных и занесения их в оперативную память, имеет линейную сложность O(n). Алгоритм сортировки методом прямого выбора имеет квадратичную сложность O(n2), так как при сортировке любого массива этот алгоритм будет выполнять (n 2- n)/2 операций сравнений (при этом операций перестановок вообще может не быть, например, на упорядоченном массиве). А сложность алгоритма умножения матриц (таблиц) размера n x n будет уже кубической O(n3), т.к. для вычисления каждого элемента результирующей матрицы требуется n умножений и n-1 сложений, а всего этих элементов n 2.

Второе обозначение, W(g (n)) — это множество всех функций, порядок роста которых при достаточно больших n не меньше (т.е. больше или равен) некоторой константы, умноженной на значение функции g (n).

 

Например:

Наконец, обозначение Q (g (n)) это множество функций, порядок роста которых при достаточно больших п равен некоторой константе, умноженной на значение функции g (n). Таким образом, любая квадратичная функция an2 + bn +c при а > 0 принадлежит множеству Q(n 2).

 

 

Пример 1. Анализ временной сложности алгоритма сортировки методом простого выбора.

Число сравнений не зависит от начального порядка элементов и равно (n2-n)/2.
Число перестановок: минимальное - 3(n-1), среднее - n(ln n + 0,57),
максимальное - (n2/4+3(n-1)).

Таким образом, алгоритм сортировки методом прямого выбора имеет сложность O(n2).

Пример 2. Анализ временной сложности алгоритма нахождения максимума конечной последовательности целых чисел.

Алгоритм S2.

S1. Установить временный максимум равный первому числу в последовательности.

S2. Сравнить следующее число в последовательности с временным максимумом, и если оно больше, чем временный максимум, установить временный максимум равный этому числу.

S3. Повторить предыдущий шаг, если есть ещё числа в последовательности.

S4. Остановиться, если в последовательности нет больше чисел. Текущий временный максимум является максимумом исходной последовательности.

Запишем алгоритм на псевдокоде

Алгоритм S2.

procedure (a1, a2,…, an:integer)

max:= a1

for i:=2 to an

if max<<ai then max:=ai

{max является наибольшим элементом}

 

Решение.

Количество сравнений будет использоваться как временная сложность, поскольку сравнение является основной операцией.

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

Поскольку для сравнения используются для каждого элемента со второго до n-ого. И одно сравнение используется для выхода из цикла при i=n+1, то при использовании данного алгоритма выполняется 2 (n-1) +1 =2n – 1 сравнений. Следовательно, алгоритм нахождения максимума последовательности чисел имеет временную сложность O(n), измеренную в количестве использованных сравнений.

Логическое программирование

Логическое программирование основано на результатах, полученных в области исчисления предикатов. Центральным понятием в логическом программировании является отношение. Программа представляет собой совокупность определений, отношений между объектами и цели, а процесс ее выполнения состоит в установлении значимости логической формулы, построенной из программы по определенным правилам.

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

Основным из языков логического программирования является язык Пролог Prolog, фр. Programmation en Logique- программирование в логике), созданный в 1973 г. Автором Пролога является Alain Colmerauer. Программа на языке Пролог строится из последовательности фактов и правил, затем формулируется утверждение.

Визуальное программирование

С середины 90-х г.г. многие объектно–ориентированные языки реализуются как системы визуального проектирования, в которых программный продукт создается в диалоговом режиме, практически без написания программных операторов. К объектно–ориентированным системам визуального проектирования относятся Visual Basic, Delphi, C++ Builder, Visual C++.

Типичным представителем систем визуального программирования является среда программирования Visual Basic, которая используется в качестве встроенного языка макроопределений во всех приложениях пакета Microsoft Office для Windows.

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

Экранная форма - графическое представление окна Windows-приложения вместе с содержанием этого окна. Содержание включает в себя:

¾ перечень свойств окна с их значениями;

¾ перечень объектов, находящихся в этом окне;

¾ перечни свойств этих объектов также с их значениями.

Экранная форма Visual Basic хранится в отдельном файле, имя которого имеет расширение frm.

Программный модуль - хранящийся в отдельном файле программный код. Он может использоваться при решении не одной, а нескольких задач. Как правило, программный код относится к отдельно взятой экранной форме.

Понятие алгоритма. Свойства алгоритмов

Алгоритм, алгоритмизация, алгоритмический язык............................................................................ 1

Свойства алгоритмов......................................................................................................................................................... 5

Управляющие структуры и основные конструкции алгоритмов........................................................................ 6

Неформальные описания алгоритмов............................................................................................................... 9

Сортировка методом простого выбора............................................................................................................................ 9

Сортировка в интегрированных пакетах....................................................................................................... 10

Сортировка в приложении Word....................................................................................................................................... 10

Сортировка в приложении Excel....................................................................................................................................... 11

Алгоритмы генерации случайных чисел...................................................................................................... 12

Сложность алгоритмов.................................................................................................................................................. 13

Технологии (парадигмы) программирования............................................................................................ 18

Процедурное программирование...................................................................................................................................... 18

Функциональное программирование............................................................................................................................. 19

Логическое программирование......................................................................................................................................... 19

Объектно-ориентированное программирование....................................................................................................... 19

Визуальное программирование........................................................................................................................................ 20

Языки программирования баз данных.............................................................................................................. 20

Языки программирования для компьютерных сетей........................................................................ 21

Инженерия программного обеспечения........................................................................................................ 21

Принцип программного управления.................................................................................................................. 21

 







ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...

Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...

Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)...

ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования...





Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:


©2015- 2024 zdamsam.ru Размещенные материалы защищены законодательством РФ.