Виды алгоритмов и их реализация

Содержание

	Цель работы ………………………………….……………………
	Средства обучения…………………………………………………
	Теоретические сведения и рекомендации ………………………
	Задание и алгоритм выполнения работы ………………………
	Рекомендации по оформлению отчета…………………………
	Контрольные вопросы…………………………………………
	Литература ……………………………………………………………
	Приложение А…………………………………………………………
	Приложение Б ........................................................................................

ПРАКТИЧЕСКАЯ РАБОТА 1

Составление блок схем

Цель работы

4. 1 Познакомиться с особенностями структурного подхода по разработке алгоритмов, изучить порядок разработки алго­ритмов.

4. 2 Овладеть практическими навыками разработки и программирования вычислительного процесса линейной, разветвляющейся и циклической структуры;

Средства обучения

4. 1 методические рекомендации;

4. 2 конспекты лекций;

4. 3 дополнительная литература.

Теоретические сведения и рекомендации

Принципы структурной алгоритмизации.

Обработка на персональных электронных вычислительных машинах (ПЭВМ) данных реального мира требует, чтобы их структура была определена и точно представлена в ПЭВМ. Структура данных определяет семантику данных, а также спосо­бы организации и управления данными. Информация, представ­ленная в виде последовательности символов и предназначенная для обработки на ПЭВМ, называется данными. При использова­нии компьютера для хранения и обработки данных необходимо хорошо знать тип и структуру данных, а также найти способ наиболее естественного их представления. Структуры данных и алгоритмы служат теми материалами, из которых строятся про­граммы.

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

Основные понятия структур данных

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

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

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

Независимо от содержания и сложности любые данные в па­мяти ЭВМ представляются последовательностью двоичных раз­рядов, или битов, а их значениями являются соответствующие двоичные числа. Данные, рассматриваемые в виде последова­тельности битов, имеют очень простую организацию или, други­ми слонами, слабо структурированы. Для человека описывать и исследовать сложные данные в терминах последовательностей битов весьма неудобно. Более крупные и содержательные, неже­ли бит, «строительные блоки» для организации произвольных данных получаются на основе понятия «структуры данных».

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

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

Интегрированными называются такие структуры данных, со­ставными частями которых являются другие структуры дан­ных — простые или в свою очередь интегрированные. Интегри­рованные структуры данных конструируются программистом с использованием средств интеграции данных, предоставляемых языками программирования.

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

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

3.2 Общие сведения об алгоритмах.

Алгоритмом называется система формальных правил, четко и однозначно определяющая процесс решения поставленной зада­чи в виде конечной последовательности действий или операций.

Алгоритм — это точное предписание, определяющее про­цесс перехода от исходных данных к результату.

Алгоритм — это конечная последовательность действий (команд) приводящая к определенному конкретному результату.

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

Свойства, которыми должен обладать алгоритм:

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

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

2. Определенность,(Однозначность) или детерминированность, алгоритма. Это свойство означает, что неоднозначность толкования записи ал­горитма недопустима.

Другими словами - однозначность — наличие единственного толкования пра­вил выполнения действий и порядка их выполнения;

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

Другими словами - результативность — получение при выполнении алго­ритма определенного результата;

4. Массовость алгоритма. Это означает, если правильный ре­зультат по алгоритму получен для одних исходных данных, то правильный результат по этому же алгоритму должен быть полу­чен и для других исходных данных, допустимых в данной задаче.

Другими словами - массовость — возможность применения алгоритма для решения целого класса задач (предполагается его пра­вильная работа при меняющихся в заданных пределах значениях исходных данных);

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

Другими словами - правильность — способность алгоритма давать правиль­ные результаты при решении поставленных задач.

Виды алгоритмов и их реализация

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

· механические,или детерминированные (жесткие);

· гибкие,или стохастические (вероятностные и эвристические).

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

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

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

В программировании алгоритмы подразделяются на три типа:

· линейный — набор команд (указаний), выполняемых последовательно друг за другом;

· разветвляющийся — алгоритм, содержащий хотя бы одну проверку условия, в результате которой обеспечивается переход на один Из возможных вариантов решения;

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

Вспомогательный (подчиненный) алгоритм — алгоритм, ра­нее разработанный и целиком используемый при алгоритмиза­ции конкретной задачи.