Условные обозначения блоков схем алгоритмов

Наименование	0бозначенне	Функции
Процесс		Выполнение операции или группы операции, в результате которых изменяется значение, форма представления или расположение данных.
Ввод-вывод		Преобразование данных в форму, пригодную для обработки (ввод) или отображения результатов обработки (вывод).
Решение		Выбор направления выполнения алгоритма в зависимости от некоторых переменных условии.
Предопределенный процесс		Использование ранее созданных и отдельно написанных программ (подпрограмм).
Документ		Вывод данных на бумажный носитель.
Магнитный диск		Ввод-вывод данных, носителем которых служит магнитный диск.
Пуск-останов		Начало, конец, прерывание процесса обработки данных.
Соединитель		Указание связи между прерванными линиями, соединяющими блоки.
Межстраничный соединитель		Указание связи между прерванными линиями, соединяющими блоки, расположенные на разных листах.
Комментарий		Связь между элементом схемы и пояснением.

Ход работы и задания:

Составить алгоритм решения следующих задач двумя способами: словесно-формульным и с помощью блок-схемы:

1. Дана длина ребра куба. Составить алгоритм нахождения площади грани, площади полной поверхности и объема этого куба.

2. Составьте алгоритм для нахождения расстояния между пешеходами, идущими навстречу друг другу, начавшими путь одновременно.

L₀ - начальное расстояние,

V₁ - скорость первого пешехода,

V₂ - скорость второго пешехода,

T - время движения,

L₁ - текущее расстояние.

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

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

5. Составьте алгоритм нахождения площади треугольников, заданных сторонами a, b, (c+k), где k=1,2,...,15.

6. Составьте алгоритм вычисления S=m(m+1)(m+2)...(m+n), где m, n- заданные натуральные числа.

Контрольные вопросы и задания:

1) Перечислите способы составления алгоритмов.

2) Алгоритмы какой структуры вы знаете?

3) Какую структуру имеет алгоритм, составленный с помощью словесного способа?

4) Какую структуру имеет линейный алгоритм, составленный с помощью блок-схемы?

5) Какую структуру имеет алгоритм ветвления, составленный с помощью блок-схемы?

Рекомендуемая литература: 1.3, 1.4, 1.5.

Практическое занятие №2 "Арифметизация машин Тьюринга и частичная рекурсивность функций, вычислимых по Тьюрингу. Нормальные алгоритмы. Нумерация алгоритмов различными методами"

Цель: Закрепить знания применения арифметизации машин Тьюринга и частичной рекурсивности функций, вычисляемых по Тьюрингу.

Вид работы: фронтальный.

Время выполнения: 6 часов.

Теоретический материал:

Машина Тьюринга состоит из следующих частей:

1. Информационной ленты, представляющей бесконечную память машины. Это бесконечная лента, разделенная на ячейки. В каждой ячейке можно поместить лишь один символ из возможного их множества S={S₁,S₂,….,S_m},которое составляет внешний алфавит МТ. В этом алфавите один из символов (пусть это будет S₁) соответствует пустому символу.

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

3. Управляющего устройства (УУ), которое в каждый момент времени находится в некотором состоянии. Число состояний конечно. Обозначим множество состояний как {q₁,q₂,…,q_n}. Среди состояний одно соответствует заключительному, при котором МТ останавливается. УУ связано со считывающей головкой.

Кроме того, УУ вырабатывает три команды на перемещение ленты: П, Л, Н, где

П – переместиться на соседнюю справа ячейку;

Л – переместиться соседнюю слева ячейку;

Н – продолжать обозревать ту же ячейку.

Совокупность символов {q₁,q₂,…,q_n} и {П,Л,Н} образуют внутренний алфавит МТ.

Работа машины происходит в дискретном времени. В начальный момент времени в ограниченный участок ленты записано слово в алфавите S, представляющее исходное условие задачи. В остальных ячейках предполагается записанным пустой символ. Управляющее устройство находится в начальном состоянии q₁. На каждом шаге работы МТ обозревает на ленте символ S_k и в зависимости от него и от состояния q_i, переходит в состояние q_j, заменяет S_k на символ S_l и передвигает ленту (либо нет) на одну ячейку.

Каждая элементарная операция имеет вид

q_iS_k ® q_jS_l П(Л,Н).

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

Считывающая головка и управляющее устройство образуют логический блок, который представляет собой (2,3)-полюсник.

Структура МТ имеет следующий вид:

S1

S2

…

Sk

…

Sm

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

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

Если остановка и сигнал об остановке никогда не поступают, то говорят, что МТ не применима к последовательности U.

Рассмотрим функционирование МТ на примере сложения двух чисел, которые будем изображать в виде набора единиц.

Внешний алфавит будет состоять из символов: {1, +, Ù}, где Ù – пустой символ.

Внутренний алфавит будет состоять из четырех символов {q₁, q₂, q₃, !}, где символ q₁ означает начальное состояние, а ! – заключительное состояние.

Пусть на ленте записана начальная информация:

						+

МТ должна ее переработать в результирующую информацию:

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

1q1 →Ùq3П 1q3→1q3П +q3→+q3П

Ùq3→1q2H +q2 →+q2Л 1q2→1q2Л Ùq2 →Ùq1П +q1 →Ù!Н

Начальное состояние УУ=q1, состояние ленты имеет вид:

					+

После первого шага состояние YY=q3, состояние ленты как на рис.

					+

					+

После пятого шага YY перейдёт в состояние q2. Состояние ленты показано на рис.

После десятого шага YY в состоянии q1 (рис. )

				1	+

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

	q1	q2	q3
	Ùq3П	1q2Л	1q3П
Ù	Ùq1П	Ùq1П	1q2H
+	Ù!Н	+q2Л	+q3П

Задания:

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

A	B
0110011101	1010101010

1. Машина Тьюринга с внешним алфавитом A = {a₀, 1} и алфавитом внешних состояний Q = {q₀, q₁, ... , q₁₃} определяется следующей функциональной схемой:

Q	A
a0	1
q1	q2a0L	q01
q2	q5a0	q3 a0
q3	q4a0L	q01
q4	q51	q41L
q5	q0a0	q61L
q6	q0a0	q7a0
q7	q8a0R	q01
q8	q91	q81R
q9	q0a0	q101L
q10	q0a0	q11a0
q11	q12a0L	q01
q12	q131	q121L
q13	q0a0	q01

Изображая на каждом такте работы машины получающуюся конфигурацию, определите, в какое слово перерабатывает машина следующие слова (в начальный момент времени машина находится в состоянии q₁ и обозревает крайнюю правую ячейку, в которой записан пустой символ a₀ , в следующей слева ячейке уже записан символ a₀1 a₀111 a₀.

Примеры решения Машины Тьюринга:

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

A	B
1011101111	1100111001

Решение:

Программа машины Тьюринга:

1. 1q₁ ®1q₁П
2. 0q₁ ®1q₂П
3. 1q₂ ®0q₂П
4. 1q₃ ®0q₄П
5. 1q₄ ®0q₄П
6. 0q₄ ®1q₅П
7. 1q₅ ®1q₆П
8. 1q₆ ®0q₇П
9. 1q₇ ®0q₈П
10. 1q₈ ®1q₀Н

Проверка работы машины:

q₁1011101111®1q₁011101111®11q₂11101111®110q₃1101111®1100q₄101111

®11001q₄01111®110011q₅1111®1100111q₆111®11001110q₇11®

110011100q₈1®1100111001q₀

2. Машина Тьюринга с внешним алфавитом A = {a₀, 1} и алфавитом внешних состояний Q = {q₀, q₁, ... , q₁₃} определяется следующей функциональной схемой:

Q	A
a0	1
q1	q2a0L	q01
q2	q5a0	q3 a0
q3	q4a0L	q01
q4	q51	q41L
q5	q0a0	q61L
q6	q0a0	q7a0
q7	q8a0R	q01
q8	q91	q81R
q9	q0a0	q101L
q10	q0a0	q11a0
q11	q12a0L	q01
q12	q131	q121L
q13	q0a0	q01

Изображая на каждом такте работы машины получающуюся конфигурацию, определите, в какое слово перерабатывает машина следующие слова (в начальный момент времени машина находится в состоянии q₁ и обозревает крайнюю правую ячейку, в которой записан пустой символ a₀ , в следующей слева ячейке уже записан символ a₀11 a₀1111 a₀.

Решение:

a₀11 a₀1111 a₀

a₀11 a₀1111 a₀ q₁® a₀11 a₀1111 q₂ a₀ ® a₀11 a₀111 a₀ q₃ a₀ ® a₀11 a₀111 q₄ a₀a₀ ® a₀11 a₀11 q₄ 1a₀a₀ ® a₀11 a₀1 q₄ 11a₀a₀ ® a₀11 a₀ q₄ 111a₀a₀ ®

a₀11 1 q₅ 111a₀a₀ ® a₀11 q₆ 1111a₀a₀ ® a₀1 a₀ q₇ 1111a₀a₀ ® a₀1 a₀ 1 q₈111a₀a₀ ® a₀1 a₀ 11q₈11a₀a₀ ® a₀1 a₀ 111q₈1a₀a₀ ® a₀1 a₀ 1111q₈a₀a₀ ®

a₀1 a₀ 1111a₀q₈a₀ ® a₀1 a₀ 11111q₉a₀ ® a₀1 a₀ 1111q₁₀1a₀ ® a₀1 a₀ 111 a₀q₁₁1a₀ ® a₀1 a₀ 111 q₁₂ a₀1a₀ ® a₀1 a₀ 11 q₁₂ 1a₀1a₀ ® a₀1 a₀ 1 q₁₂ 11a₀1a₀ ®

a₀1 a₀ q₁₂ 111a₀1a₀ ® a₀1 1 q₁₃ 111a₀1a₀ ® a₀1 1 q₀ 111a₀1a₀

Получаем слово: a₀1 1 q₀ 111a₀1a₀

Контрольные вопросы и задания:

1) Из каких частей состоит Машина Тьюринга?

2) Что представляет собой информационная лента?

3) Как работает управляющее устройство?

4) Как выглядит элементарная операция Машины Тьюринга?

Рекомендуемая литература: 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.8, 2.3, 2.4, 2.5.

Практическое занятие №3 "Построение алгоритмов различными методами"

Цель:Закрепить навыки разработки алгоритмов для конкретных задач различными методами.

Вид работы: фронтальный.

Время выполнения: 4 часа.

Теоретический материал:

К основным способам описания алгоритмов можно отнести следующие:

- словесно-формульный (на естественном языке);

- структурный или блок-схемный;

- с использованием специальных алгоритмических языков;

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

- с помощью сетей Петри.

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

Словесно-формульный способ.

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

Пусть, например, необходимо найти значение следующего выражения:
у=2а-(х+6).

Словесно-формульным способом алгоритм решения этой задачи может быть записан в следующем виде:

1.Ввести значения а и х.

2.Сложить х и 6.

3.Умножить а на 2.

4.Вычесть из 2а сумму (х+6).

5.Вывести у как результат вычисления выражения.

Блок-схемы.

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

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

Оформление программ должно соответствовать определенным требованиям. В настоящее время действует единая система программной документации (ЕСПД), которая устанавливает правила разработки, оформления программ и программной документации. В ЕСПД определены и правила оформления блок-схем алгоритмов (ГОСТ 10.002-80 ЕСПД, ГОСТ 10.003-80 ЕСПД).

Операции обработки данных и носители информации изображаются на схеме соответствующимиблоками. Большая часть блоков по построению условно вписана в прямоугольник со сторонами а и b. Минимальное значение а равно 10 мм, увеличение а производится на число, кратное 5 мм. Размер b=1,5 мм. Для отдельных блоков допускается соотношение между а и b, равное 1:2. В пределах одной схемы рекомендуется изображать блоки одинаковых размеров. Все блоки нумеруются. Виды и назначение основных блоков приведены в таблице.

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

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

Если при обрыве линии продолжение схемы находится на этом же листе, то на одном и другом конце линии изображается специальный символ соединитель — окружность диаметром 0,5 мм. Внутри парных окружностей указывается один и тот же идентификатор. В качестве идентификатора, как правило, используется порядковый номер блока, к которому направлена соединительная линия. Если схема занимает более одного листа, то в случае разрыва линии вместо окружности используется межстраничный соединитель. Внутри каждого соединителя указывается адрес — откуда и куда направлена соединительная линия. Адрес записывается в две строки: в первой указывается номер листа, во второй — порядковый номер блока.

Блок-схема должна содержать все разветвления, циклы и обращения к подпрограммам, содержащиеся в программе.