31

Министерство образования и науки Украины Одесский технический колледж Комиссия ЭВТ

Заместитель директора ОТК по учебной работе

_____________ В.И.Уманская

____ _____________ 2007 г.

Методические указания по выполнению практических работ студентам

специальности 091504 “Обслуживание компьютерных и интеллектуальных систем и сетей” по предмету «Теория алгоритмов»

Рассмотрено на заседании

цикловой комиссии Протокол № _____ от ____ _________ 2007г.

Председатель _________ Гаджиев М.М.

2007г.

Аннотация Теория алгоритмов и практика их построения и анализа занимают важное

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

Разработала: преподаватель комиссии ЭВТ Иванова Л.В.

Содержание

1. Практическая работа №1 «Организация разветвлений в схемах алгоритмов»

2. Практическая работа №2 «Циклические алгоритмы»

3. Практическая работа №3 «Изучение алгоритмов покрытия»

4. Практическая работа №4 «Изучение алгоритмов покрытия (продолжение)»

5.Практическая работа №5 «Конечный автомат»

6.Практическая работа №6 «Машина Тьюринга»

7.Практическая работа №7 «Структуры данных»

8.Практическая работа №8

«Структуры данных (продолжение)» 9. Практическая работа №9

«Теория графов и алгоритмы по графам» 10.Практическая работа №10

«Компоненты связности графов» 11.Практическая работа №11

«Сортировка» 12.Практическая работа №12

«Сортировка (продолжение)»

Практическая работа №1.
Тема: Организация разветвлений в схемах алгоритмов.
Цель: Изучить основные формы представления и организацию	линейных,
условных и циклических алгоритмов.
Линейные алгоритмы.

Линейным называется алгоритм, в котором связи между вершинами имеют одно направление и отсутствуют разветвления.

Пример 1.1. Составить СА для вычисления следующей функции:

y	= s i n ( α ) c o s ( β ) + e − x 0		c o s ( α )	(1.1)
при заданных значениях α ,		β , x 0 .
Вычислительный процесс для данной функции может быть организован в
виде	последовательности	шагов, на	каждом из которых	производятся
следующие вычисления:

1)А1=Sin (α);

2)A2=Cos (α);

3)A3=Exp (-х);

4)A4=Cos (β);

5)B1=A1*A4;

6)B2=A3*A2;

7)C=B1+B2=y.

СА, реализующая данный вычислительный процесс с учетом ввода исходных данных и вывода вычисленного значения y, является линейной (рис. 1.1).

Отметим особенности вычислительного процесса в нашем случае: операторные вершины 2-5 можно располагать в произвольном порядке; то же относится и к вершинам 6 и 7.

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

Для вычисления функций Sin, Cos и Exp используются стандартные подпрограммы (ПП), основанные, как правило, на представлении этих функций в виде многочленов (разложение в ряд Тейлора); существуют и другие представления [2]. Однако этим ПП соответствуют свои СА, которые не являются линейными.

Таким образом, линейность - понятие относительное, и зависит от степени подробности представления СА; в сколь-нибудь сложной СА линейными могут быть только её фрагменты.

Рис. 1.1. Пример линейной СА: а)последовательная реализация б) параллельная реализация.

Схемы алгоритмов с разветвлениями.

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

Пример 1.3. Составить СА нахождения корней квадратного уравнения

au2+bu+c=0	(1.7)
Предварительно запишем приведенное	квадратное уравнение с целью

уменьшения числа параметров, определяющих решения исходного уравнения:

				u2+pu+q=0	(1.8)
	здесь p=b/a (a≠0!),q=c/a.				(1.9)
	Известно, что корни приведенного квадратного уравнения определяются
	по формуле
	u1,2 = − p	±		d ,	(1.10)
	2
	где d =		p2	− q .	(1.11)
		4

Взависимости от значений d возможны 3 случая :

*d>0. Решение содержит два вещественных корня

u1	= − p	+	d , u2	= − p	−	d .	(1.12)
	2			2

*d<0. Решение содержит два мнимых корня ( i = −1 ; u=x+iy)

u1	= − p	+i	d	, u2	= − p	+	d .	(1.13)
	2				2

• d=0. Решение содержит один корень кратности (два слившихся корня) u1 = u2 = − 2p

Рис. 1.2. Расположение корней на комплексной плоскости (p>0; r = d )

Проанализируем поведение корней при изменении величины и знака дискриминанта d (рис.1.3):

1)d>0 - корни перемещаются по вертикали (мнимая ось);

2)d<0 - корни перемещаются по горизонтали (реальная ось);

3) d=0 - граничная точка x=-p/2 при переходе с вертикали на горизонталь. Анализ такого рода необходим при построении контрольного примера для

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

Составляем СА (рис. 1.3), исходя из следующей последовательности шагов: вводим исходные данные и вычисляем параметры приведенного квадратного уравнения; формируем вычисления корней в соответствии с тремя возможными альтернативами, используя условные вершины; выводим результаты на экран (принтер).

На рис. 1.3а пунктиром выделен блок выбора по условию, составленный из двух условных вершин, этот блок позволяет представить разветвление СА по трем альтернативным направлениям в зависимости от значения дискриминанта. Он может быть преобразован в эквивалентный блок (рис. 1.3 б); анализ этого блока показывает, что проверку условия d=0 можно исключить из алгоритма, поскольку в случае d=0 равные значения корней получаются автоматически.

Рис.1.3. СА с ветвлением: а - основная схема; б - вариант блока выбора.

Организация выбора альтернатив в СА.

Рассмотрим вопрос организации выбора направления в СА с ветвлением подробнее. На рис. 1.4 приведены условные операторы и их конфигурации в виде фрагментов СА, а именно (S - оператор общего вида):

а) if (условие) then S;

б) if (условие) then S1 else S2;

в) case N of 1: S1; 2: S2; … k:Sk end;

Рис. 1.4. Фрагменты СА для условных операторов типа: а,б – if; в – case .. of. Для простых случаев выбора достаточно использовать условные

операторы if (рис. 1.4 а и б ). В более сложных случаях Pascal представляет мощное средство - оператор-переключатель case .. of (рис. 1.4 в).

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

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

б) альтернативы – две, но выбор осуществляется по сложному условию. На СА выбор реализуется двоичным деревом (полным либо неполным), в

каждой условной вершине которого простейший выбор кодируется логическим 0, если условие не выполняется (false), и логической 1, если условие выполняется (true).

Если составить позиционный код на выходе из блока выбора по каждому направлению в соответствии с результатом прохождения через условные вершины СА сверху вниз, то мы получим двоичный код десятичного числа, уменьшенного на 1. Пpоpанжиpуем сверху вниз условные вершины, тогда количество альтернатив n, предоставляемых полным двоичным деревом, определяется рангом r: n=2r.

возвращаясь к pис.1.4, отметим, что в данном случае мы имеем двухpанговое неполное дерево выбора (r = ] log2 3 [ = 2).

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

Пусть необходимо организовать выбор из четырёх альтернатив, причем на втором ранге условия одинаковы. В этом случае достаточно двух условий В1 и В2 (В1 и В2-булевы переменные), если каждому из значений false (0) и true (1) этих условий сопоставить свою альтернативу Ni – см. Табл. 1.1. Этой таблице соответствует фрагмент СА, показанный на pис.1.5; здесь рядом с номерами альтернатив указаны их коды.

Таблица 1.1

		B1			B2		C
		0			0		N1
		0			1		N2
		1			0		N3
		1			1		N4

Рис. 1.5. Организация выбора из четырех альтернатив.

Пример 1.4. Пусть задан условный оператор вида С=В1 В2, где В1 и В2 - логические условия (В1,В2 є { 0,1 }) и - операция логического сложения по mod2. Заполним таблицу истинности для функции С (табл. 1.2 ); здесь в колонке для С проставлены ее логические значения F(false) и T(true), определяющие выбор из двух путей (альтернатив), по которым разветвляется схема данного оператора. На pис.1.6 приведен фрагмент схемы , построенный в соответствии с таблицей 1.2, причем все пути, имеющие одинаковое логическое значение, объединены.

Таблица 1.2

		B1			B2		C
		0			0		F
		0			1		T
		1			0		T
		1			1		F

Рис. 1.6 пример СА выбора при неполном дереве выбора Аналогично заполняется таблица истинности (если она не задана) и по

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

Если в какой-либо ветви построенной схемы имеется изображенный на рис. 1.7 а фрагмент, то данная булева переменная Вi склеивается, т. е. BiVBi дает логическую константу 1; это означает, что условная вершина на участке a- b не нужна и ее можно заменить отрезком прямой (рис 1.7. б).

Рис.1.7 Частный случай выбора: а – исходный фрагмент БВ; б – упрощение фрагмента.

Покажем способ построения схем выбора при			r>2 на частном примере
реализации логической функции C = B1VB2&		, где B1, B2, B3 – некоторые
	B3
условия (булевы переменные).					.
Введем в исходную функцию промежуточную			переменную Z = B2&
				B3

Тогда С=B1&Z, и эта функция реализуется в соответствии с приведенными выше положениями в виде схемы pис.1.8а. Аналогично реализуется фрагмент схемы для переменной Z (pис.1.8 б). Далее произведем «сборку» общей схемы, вставляя в вершину Z (pис.1.8 а) соответствующий ей фрагмент из pис.1.8б, и упростим начертание результирующей схемы (pис.1.8 в).

Рис. 1.8 построение схемы выбора по условию C = B1VB2& B3
Пример 1.5. Пусть для выбора существует 3 альтернативы	N1..N3,

определяемые тремя простыми условиями В1..В3 (В1..В3 – булевы переменные) в соответствии с табл. 1.3. Требуется синтезировать СА для бло-А выбора.

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

– что не реализуется. Тогда Ni (i=1,3) можно считать выходными переменными блока выбора , а саму таблицу можно рассматривать как таблицу истинности для системы трех функций от трех булевых переменных. Далее можно использовать известный подход […] для минимизации такой системы и синтеза соответствующей СА.