Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Алгоритматизация - файл 1.docx


Алгоритматизация
скачать (621.4 kb.)

Доступные файлы (1):

1.docx622kb.08.12.2011 22:19скачать

содержание

1.docx

Содержание.


  1. Понятия и свойства алгоритма……………………….2

  2. Язык блок схем……………….…………………….....3

  3. Основные (базовые) структуры алгоритма………...4

  4. Внешний синтаксис………… ……………………….6

  5. Рекурсивные алгоритмы…………………………..…9

  6. Алгоритмы поиска……………………………… …..10

  7. Алгоритмы сортировки……………………………...11









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

Алгоритм - формальное описание последовательности действий, которое необходимо выполнить для решения задачи. Термин «алгоритм» обязан своим происхождением великому ученому средневекового Востока, чье имя – Мухаммед ибн Муса ал Хорезми. Он жил приблизительно с 783 по 850 гг.


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

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

Определенность (детерминированность). Каждое правило алгоритма должно быть четким и однозначным. Отсюда выполнение алгоритма носит механический характер.

Результативность (финитность, конечность). Алгоритм должен приводить к решению задачи за конечное число шагов.

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




Язык блок-схем.

Язык блок-схем - способ формального описания алгоритмов. Схема наглядно демонстрирует все связи между элементами. Хорошо различаются элементы, в которых записаны условия ветвления (ромбы), элементы, в которых записаны указания о работе над числами (прямоугольники), а также элементы ввода информации и её вывода (параллелограммы).

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

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

Обработка данных

(вычисление, пересылка и т.п.) Вызов процедуры


Проверка условия

Соединительные линии и их объединение Ввод-вывод данных

Точки связи или соединители Начало, завершение программы или подпрограммы

Комментарий
^ Основные (базовые) структуры алгоритмов

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

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

Простая программа - алгоритм, для которого:

  • Существует единственный вход и единственный выход.

  • Для каждого элемента алгоритма существует путь от входа к выходу через этот элемент (т.е. алгоритм не содержит бесконечных циклов и не содержит бесполезных (недостижимых) фрагментов).

Примеры простой и непростых программ:

Простая программа


Бесконечный цикл

Недостижимый фрагмент

Основные (базовые) структуры алгоритмов и их производные:

Следование последовательное Цикл «До» (с постусловием) - тело цикла

выполнение действий (блоков). (блок 2) выполняется до тех пор, пока

условие (блок 3) не станет истинным.

Цикл «Пока» (с предусловием) - пока не будет нарушено условие (блок 3), осуществляется повторение тела цикла (блок 2).
Разветвление - применяется, когда в зависимости от условия требуется выполнить либо одно действие, либо другое.
Обход - частный случай разветвления, когда одна ветвь не содержит ни каких действий.


Множественный выбор - обобщение разветвления, когда в зависимости от значения переменной I выполняется одно из нескольких действий.
^ Внешний синтаксис

Внешний синтаксис - альтернативный способ описания логики программы на этапе проектирования – использование псевдокода (или языка проектирования программ PDL – Process Design Language). Он занимает промежуточное положение между естественным языком и языком программирования и состоит из внешнего синтаксиса и внутреннего синтаксиса.

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

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

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

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

Операторы внешнего синтаксиса псевдокода следующие:

- Следование. Записываются последовательно операции одна под другой. Для отделения части последовательности операторов используются операторы – do…end-do.



  • Индексная последовательность (цикл по счетчику). Цикл с заранее определенным числом шагов (среднее между обычными последовательностью и классическим циклом).



  • Цикл-До. Операции структуры, включая модификацию until-теста, выполняются один или более раз до тех пор, пока until-тест не примет значение истина




  • Цикл-Пока. Do-часть выполняется пока while-тест имеет значение истина. Do-часть модифицирует условие while-теста для того, чтобы окончить вычисления.




  • Разветвление. Если…то…иначе



  • Множественный выбор



Алгоритмы вычисления суммы квадратов первых N целых чисел с использованием псевдокода и языка блок-схем

Ввести Число слагаемых

Сумма = 0

Номер = 1

do

Сумма = Сумма + Номер2

Увеличить Номер на единицу

Until

Номер > Число слагаемых

end-do

Напечатать Сумму




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

«Программа – это конкретное, основанное на некотором реальном представлении и строении данных, воплощение абстрактного алгоритма». (Н. Вирт).


^ Рекурсивные алгоритмы.

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



Функция F является рекурсивной, если

^ 1. F(N)=G(N,F(N-1)) - , где G известная функция;

2. F(1)–известно (базисное утверждение).
Алгоритм вычисления факториала N с использованием рекурсивной функции представляется в следующем виде:

^

Алгоритмы поиска.

Поиск - обнаружение нужного элемента в некотором наборе (структуре) данных. Элемент данных - это запись, состоящая из ключа (целое положительное число) и тела, содержащего некоторую информацию. Задача состоит в том, чтобы обнаружить запись с нужным ключом.


Линейный поиск. Элементы проверяются последовательно, по одному, до тех пор, пока нужный элемент не будет найден. Для массива из N элементов требуется, в среднем, (N+1)/2 сравнений (вычислительная сложность Оср(N)). Легко программируется, подходит для коротких массивов.

Двоичный (бинарный) поиск. Применим, если массив заранее отсортирован (по возрастанию ключей). Ключ поиска сравнивается с ключом среднего элемента в массиве. Если значение ключа поиска больше, то та же самая операция повторяется для второй половины массива, если меньше - то для первой. Операция повторяется до нахождения нужного элемента. На каждом шаге диапазон элементов в поиске уменьшается вдвое. Требуется, в среднем, (log2N+1)/2 сравнений (вычислительная сложность Оср(log2N)). Применяется для поиска (многократного) в больших массивах.
^



Алгоритмы сортировки.

Сортировка (упорядочение) - переразмещение элементов данных в возрастающем или убывающем порядке. При выборе метода сортировки необходимо учитывать число сортируемых элементов (N) и до какой степени элементы уже отсортированы.


Критерии оценки метода сортировки:

  • количество необходимых операций сравнения в зависимости от числа элементов N, вычислительная сложность алгоритма характеризуется с помощью О-функции, аргументом которой является другая функция от N;

  • эффективность использования памяти



где S(N) - объем памяти, занимаемый элементами данных до сортировки, S(N) - объем дополнительной памяти, требуемой в процессе сортировки.

Сортировка методом выборки. Принцип: Из массива выбирается наименьший элемент и помещается на место первого элемента массива, затем выбирается наименьший элемент из оставшихся и помещается во второй элемент массива и т.д.
С использование псевдокода это можно записать как:

Ввести массив A(1..N)

for J = 1,N-1,1

do

Мин.Эл. = А(J)

Индекс Мин.Эл. = J

for I = J+1,N,1

do

if A(I) < Мин.Эл.



then

Мин.Эл. = A(I)

Индекс Мин.Эл. = I

end-if

end-do

A(Индекс Мин.Эл.) = A(J)

A(J) = Мин.Эл.

end-do

Вывести A(1..N)

Требуется, в среднем, N(N+1)/2 сравнений (вычислительная сложность O(N2), не зависит от начальной упорядоченности). Дополнительная память не нужна.

Сортировка включением. Принцип: Элементы выбираются по очереди и помещаются в нужное место.
С помощью псевдокода это запишется следующим образом:

Ввести массив A(1..N)

for I = 2,N,1

do

Temp = А(I)

A(0) = Temp

J = I-1

while A(J) > Temp

do

A(J+1) = A(J)

J = J-1

end-do



A(J+1) = Temp

end-do

Вывести A(1..N)

Требуется, в среднем, (N-1)(N/2+1)/2 сравнений (вычислительная сложность Оср(N2)).{ Осравнения } Скорость данного метода зависит от начальной упорядоченности массива. Не требуется дополнительной памяти.

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

Ввести массив A(1..N)

K = 1, I = 1

while K <> 0

do

K = 0

for J = 1,N-I,1

do

if A(J) > A(J+1)

then

T = A(J),

A(J) = A(J+1),

A(J+1) = T, K = K+1

end-if

end-do

I = I +1

end-do



Вычислительная сложность данного метода сильно зависит от исходного расположения элементов. Минимальное значение числа сравнений – N-1 в полностью отсортированном массиве, максимальное – (N2-N)/2 при начальной сортировке в обратном порядке. Средняя вычислительная сложность Оср(N2). Дополнительная память не требуется.

Сортировка распределением (метод корзин). Принцип: Элементы массива рассматриваются как совокупность цифр (символов), первый шаг - сортировка по значению старшей цифры, затем полученные подмножества (группы) сортируются по значению следующей цифры и т.д.

Каждый элемент массива А (1..N) - совокупность цифр С1С2С3…Сm, где m - количество цифр максимального элемента (если какой-то элемент содержит меньше цифр, то он слева дополняется нулями).
Средняя вычислительная сложность Оср(N log2N) и лучше, если m (число цифр) мало. Требуется дополнительный массив размером N, и еще массив размером 10, в котором подсчитывается число элементов с выделяемой цифрой 0,1,…9.

Быстрая сортировка. Принцип: Определенным образом выделяется пороговый элемент. На первом этапе элементы обмениваются так, что новый массив оказывается разделенным пороговым элементом на две части: в левой все элементы меньше порогового, а в правой – больше или равны пороговому. Затем подобный способ используется для разделения каждого из новых массивов на две части и т.д. Алгоритм 

процедуры разбиения массива А(1..N) пороговым элементом, находящимся сначала на месте А(1).

С помощью псевдокода это запишется следующим образом:

{Процедура разбиения массива A(1..N) пороговым элементом V}

V = A(1), K = 2, J = N

while K < J

do

if A(K) < V

then

K = K + 1

Else

if A(J) < V

then

Temp = A(K), A(K) = A(J)

A(J) = Temp

end-if

J = J – 1

end-if

end-do

if A(K) >= V

then

K = K – 1

end-if

Temp=A(1),A(1)=A(K),A(K)=Temp


Средняя вычислительная сложность - Оср(N log2N).

Важное значение имеет выбор значения порогового элемента. В частности, если исходный массив близок к отсортированному, то при выборе пороговым элементом первого элемента (как в примере) вычислительная сложность алгоритма будет О(N2). Желательно, чтобы пороговый элемент в конечном итоге разделил массив приблизительно на две равные части.

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

Алгоритм слияния отсортированных массивов B(1..M) и C(1..L) в массив A(1..M+L) заключается в следующем. В качестве А(1) выбираем наименьший из В(1) и С(1). Если это В(1), то в качестве А(2) - наименьший из В(2) и С(1) и т.д.
С помощью псевдокода это запишется следующим образом:

Ввести массивы B(1..M),С(1..L)

I = 1, J = 1

for K = 1,M+L,1

do

if I > M

then

A(K) = C(J), J = J + 1

else

if J > L

then

A(K) = B(I), I = I + 1

else

if B(I) < C(J)

then

A(K) = B(I),I = I + 1

else

A(K) = C(J),J = J + 1

end-if

end-if

end-if

end-do



Если имеется один неотсортированный массив А(1..N), то его можно рассматривать как совокупность N отсортированных массивов, каждый из которых состоит из одного элемента. Первый шаг - слияние массивов попарно, затем объединение пар в четверки и т.д.

Средняя вычислительная сложность алгоритма - Оср(N log2N). Требуется дополнительный массив, содержащий N элементов.




Список использованной литературы.


  1. Себеста Р.У. Основные концепции языков программирования, Изд. Дом «Вильямс», 2001.

  2. Вирт Н. Алгоритмы и структуры данных, Мир, 1989.

  3. Н.А. Криницкий. Алгоритмы вокруг нас.- М.: Наука,1977. - 224 с.

  4. Касаткин В. Н. Информация, Алгоритмы ЭВМ, - М.: Просвещение, 1991.- 192 с.



Скачать файл (621.4 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации