Файл: Основные структуры алгоритмов: сравнительный анализ и примеры их использования (Блок-схема алгоритма).pdf

ВВЕДЕНИЕ

Немного о языке Python

Python это универсальный современный язык программирования высокого уровня, к преимуществам которого относят высокую производительность программных решений и структурированный, хорошо читаемый код. Синтаксис Питона максимально облегчен, что позволяет выучить его за сравнительно короткое время. Ядро имеет очень удобную структуру, а широкий перечень встроенных библиотек позволяет применять внушительный набор полезных функций и возможностей. ЯП может использоваться для написания прикладных приложений, а также разработки WEB-сервисов. 
Python может поддерживать широкий перечень стилей разработки приложений, в том числе, очень удобен для работы с ООП функционального программирования. 
Один из самых популярных интерпретаторов языка – CPython, написанный на Си. Распространяется эта среда разработки бесплатно по свободной лицензии. Интерпретатор поддерживает большинство популярных платформ. 
Питон активно развивается. Примерно раз в 2 года выходят обновления. Важной особенностью языка является отсутствие таких стандартов кодировки как ANSI, ISO и некоторых других, они работают благодаря интерпретатору.

Реализация алгоритмов на Python

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

Эффективный алгоритм обработки ассоциативных массивов (поиска значений, добавления и удаления значений и ключей, сортировки и пр.) в значительной степени зависит от используемого языка программирования и определённых в этом языке типов и структур данных. Так, в языке программирования Basic ассоциативный массив образуется из нескольких согласованных одномерных массивов. В языке программирования Pascal для представления ассоциативных массивов используется структура данных «запись» (record). В Python для ассоциативных массивов определена специальная структура данных — словарь, но мы рассмотрим работу с ассоциативными массивами с помощью списков и функций работы со списками

Машина Тьюринга

Устройство машины Тьюринга

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

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

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

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

      Машина Тьюринга называется детерминированной, если каждой комбинации состояния и ленточного символа в таблице соответствует не более одного правила. Если существует пара «ленточный символ — состояние», для которой существует 2 и более команд, такая машина Тьюринга называется недетерминированной.

Описание машины Тьюринга

      Конкретная машина Тьюринга задаётся перечислением элементов множества букв алфавита A, множества состояний Q и набором правил, по которым работает машина. Они имеют вид: qiaj→qi1aj1dk (если головка находится в состоянии qi, а в обозреваемой ячейке записана буква aj, то головка переходит в состояние qi1, в ячейку вместо aj записывается aj1, головка делает движение dk, которое имеет три варианта: на ячейку влево (L), на ячейку вправо (R), остаться на месте (S)). Для каждой возможной конфигурации имеется ровно одно правило. Правил нет только для заключительного состояния, попав в которое машина останавливается. Кроме того, необходимо указать конечное и начальное состояния, начальную конфигурацию на ленте и расположение головки машины.

Алгоритмы и их понятия
Один из крупнейших специалистов по системному программированию Дональд Э. Кнут начинает серию своих книг «Искусство программирования для ЭВМ» с определения понятия алгоритма: «Понятие алгоритма является основным при составлении любого вида программ для ЭВМ… Помимо того, что алгоритм – не просто свод конечного числа правил, задающих последовательность выполнения операций при решении той или иной специфической задачи, он имеет еще и пять важных особенностей:

1) Конечность (финитность). Алгоритм всегда должен заканчиваться после конечного числа шагов.

2) Определенность. Каждый шаг алгоритма должен быть точно определен. Действия, которые необходимо произвести, должны быть строго и недвусмысленно определены в каждом возможном случае.
3) Ввод. Алгоритм имеет некоторое (быть может, равное нулю) число. входных данных, т.е. величин, заданных ему до начала работы. Эти данные берутся из некоего конкретного множества объектов.

4) Вывод. Алгоритм имеет одну или несколько выходных величин, т.е. величин, имеющих вполне определенные отношения ко входным данным.

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

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

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

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

В данной курсовой работе я рассматриваю основные структуры алгоритмов.

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

      Для каждой задачи может существовать множество алгоритмов, приводящих к цели. Увеличение эффективности алгоритмов составляет одну из задач современной информатики. В 50-х гг. XX века появилась даже отдельная её область — быстрые алгоритмы. В частности, в известной всем с детства задаче об умножении десятичных чисел обнаружился ряд алгоритмов, позволяющих существенно ускорить нахождение произведения.

Глава I

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

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

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

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

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

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

1) ввод исходных данных;

2) вычисление искомых величин по формулам;

3) вывод результатов из памяти на информационный носитель.

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

Пример 1. Составить алгоритм вычисления площади круга по формуле

Python 3.6.3 (v3.6.3:2c5fed8, Oct 3 2017, 18:11:49) [MSC v.1900 64 bit (AMD64)]on win32
Type "copyright", "credits" or "license()" for more inform
>>>Pi=3.14 #инициализация числа

>>>R=3.0 #задаем значение R

>>>S=Pi*R**2 #формула для вычисления площади круга

>>>S #вывод

28.259999999999998 #результат

>>>

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

1) такие описания не строго формализованы;

2) страдают многословностью записей;

3) допускают неоднозначность толкования отдельных предписаний.

Сначала с помощью функции (метода) numpy.zeros() создаётся двумерный массив (матрица), заполненный нулями, а потом вместо нулей подставляются реальные значения. Индексы элементов, так же как в строках, кортежах и списках, начинаются с 0 (первый — верхний левый — элемент матрицы в Python имеет индекс [0,0]). Оператор print выводит индексы очередного элемента матрицы, который нужно ввести.

Задача 1. Выполнить обработку элементов прямоугольной матрицы A, имеющей N строк и M столбцов. Найти среднее арифметическое элементов массива.

Постановка задачи:

Дано:

n — количество строк в массиве;

m — количество столбцов в массиве;

A[i,j] — элемент массива;

i,j — индексы элемента массива.

Найти:

S — сумма элементов массива (сумма всех A[i,j] при всех i и j)

K — количество элементов в массиве (K = m∗n)

C — среднее арифметическое элементов массива (C = S/K)

Блок-схема алгоритма

Структурная (блок-, граф-) схема алгоритма – графическое изображение алгоритма в виде схемы связанных между собой с помощью стрелок (линий перехода) блоков – графических символов, каждый из которых соответствует одному шагу алгоритма. Внутри блока дается описание соответствующего действия. Графическое изображение алгоритма широко используется перед программированием задачи вследствие его наглядности, т.к. зрительное восприятие обычно облегчает процесс написания программы, ее корректировки при возможных ошибках, осмысливание процесса обработки информации. Можно встретить даже такое утверждение: «Внешне алгоритм представляет собой схему – набор прямоугольников и других символов, внутри которых записывается, что вычисляется, что вводится в машину и что выдается на печать и другие средства отображения информации». Здесь форма представления алгоритма смешивается с самим алгоритмом. Принцип программирования «сверху вниз» требует, чтобы блок-схема поэтапно конкретизировалась и каждый блок «расписывался» до элементарных операций. Но такой подход можно осуществить при решении несложных задач. При решении сколько-нибудь серьезной задачи блок-схема «расползется» до такой степени, что ее невозможно будет охватить одним взглядом. Блок-схемы алгоритмов удобно использовать для объяснения работы уже готового алгоритма, при этом в качестве блоков берутся действительно блоки алгоритма, работа которых не требует пояснений. Блок-схема алгоритма должна служить для упрощения изображения алгоритма, а не для усложнения.

Вспомним основные условные обозначения графического алгоритма: