Базовые алгоритмические структуры

1. Линейные алгоритмы — последовательность блоков, каждый из которых имеет по одному входу и одному выходу, и выполняется в программе один раз. (Рис.7.1)

Рис. 7.1. Алгоритм линейной структуры Рис.7.2. Алгоритм «Разветвления»

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

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

Рис.7.3. Алгоритм циклического вычислительного процесса

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

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

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

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

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

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

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

Классификация языков программирования

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

Языки программирования
Процедурные	Функциональные	Логические	Объектно-ориентированные

Ведущими разработчиками систем программирования в настоящее время являются фирмы Microsoft и Borland International.

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

Рассмотрим некоторые языки программирования в порядке увеличения их уровня.                                                    

Двоичный язык - в настоящее время программистами не применяется.

Шестнадцатеричный язык-упрощение за счет представления четырех двоичных цифр одной шестнадцатеричной. Используется в качестве дополнения к языкам высокого уровня для программирования критичных к времени выполнения фрагментов алгоритмов.

Язык Ассемблера - предназначен для представления в удобочитаемой символической форме программ, написанных на машинном языке.

Язык Макроассемблера - расширение языка Ассемблера. Позволяет определять и использовать новые, более мощные команды.

Язык программирования C- разработан в начале 70-х. Сочетает достоинства современных высокоуровневых языков (в части структур данных и управляющих структур) и возможность доступа  к аппаратным средствам машины на уровне языка Ассемблера. Однако синтаксис языка таков, что затрудняет программирование и понимание составленных программ.

Язык Basic (Beginner’s All-purpose Symbolic Instruction Code-многоцелевой язык символических инструкций для начинающих). Разработан в 1964 г. для использования новичками. Первоначально работа велась только в режиме интерактивной (диалоговой) интерпретации. В смысле строгости и стройности является антиподом языка Pascal. Несмотря на это, Basic очень популярен, в особенности на ПК. Существует множество его диалектов, несовместимых между собой. Современные диалекты Basic’а весьма развиты и мало чем напоминают  своего предка.

Язык Fortran (Formula Translator) разработан в 1956 г. Считается “рабочей лошадью” научных работников за счет своей “приспособленности” к ведению сложных вычислений и широко используется до настоящего времени, несмотря на свою ограниченность и ”корявость”.

Язык Pascal разработан в 1970 г. Норбертом Винером, назван в честь французского математика Блеза Паскаля. В Паскале полностью реализована концепция структурного программирования не только путем упорядочения связей между фрагментами программы, но и за счет структуризации данных. Один из наиболее популярных языков программирования.

 Язык  Modula-2 создан в 1979 г. также Норбертом Винером. По существу - развитие Паскаля. Его особенности состоят в высокой модульности программ и наличии средств описания параллельных процессов.

Язык Ada разработан в 1979 г. по заказу Министерства обороны США для использования во встроенных системах с управляющими ЭВМ, что требует режима поддержки режима реального времени. Назван в честь Августы Ады Лавлейс (дочери Байрона), которая была ассистентом Чарльза Бэббиджа и по праву считается первым в мире программистом. Рассматривается как универсальный язык программирования. Данный язык вводит строгую дисциплину программирования, что препятствует написанию “плохих программ”. Несмотря на достоинства, программистов отталкивает его громоздкость.

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

Тесты к теме

1.Алгоритм, при использование которого порядок следования команд определяется

в зависимости от результатов проверки некоторых условий, называют:

1. Разветвляющимся

2. Линейным

3. Циклическим

4. Векторным

5. Рекурсивным

2. В состав основных функций операционной системы входят:

A) Диалог с пользователем, управления ресурсами компьютера, запуск программы.

B) Диалог с пользователем, создание программы для ЭВМ.

C) Печать информации принтером.

D) Управление ресурсами компьютера, выполнение программ для ЭВМ.

Е) Копирование информации со сканера в компьютера, запуск программы.

3. Автором программы признается:

А)Физическое лицо, которое в результате своей творческой и интеллектуальной деятельности разработало программное обеспечение.

B)Физическое лицо, оказывающее помощь в получении патента.

C)Физическое лицо, создавшего условия для разработки.

D)Физическое лицо, оказывающее материальную помощь для разработки.

E) Физическое лицо, которое осуществляло руководство разработкой / программного обеспечения.

4. Как называется конструкция блок-схемы, изображенная на рисунке?

А) начало-конец алгоритма.

B)выполнение операций.

C) цикла с предусловием.

D)ввод/вывод данных.

Е) вызов вспомогательного алгоритма.

5. Книга, дискета, жесткие диски служат для:

A) хранение информации.

B)обработки информации.

C)создания информации.

D) передачи информации.

Е) сбора информации.

6. Комплекс прикладных программ, с помощью которых на рабочем месте

выполняются конкретные задачи:

А) Пакет прикладных программ

B) Система программирования

С) Системные утилиты.

Д) Операционная система.

Е) СУБД

7.Язык программирования - это:

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

диска.

B.Язык персонального компьютера.

C. Аналитическая модель языка.

D.Язык, предназначенный для записи алгоритма.

E. Язык, предназначенный для укрепления связи между людьми.

8.Тип алгоритма, который обеспечивает получение результата путём однократного

выполнение последовательности действий:

А) Линейный

B) Комбинированный.

С) Рекурсивным. Д) Циклический.

Е) Разветвляющиеся.

9.Под обменом информацией понимается:

A. Перемещение её из одного накопителя в другой.

B. Её прием или передача.

C. Перевод её на машинный язык.

D. Перемещение из внешней памяти во внутреннюю.

E. Кодирование информации.

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

программой, называется:

A.Транслятором.

B. Утилитой.

C. Интерфейсом.

D. Драйвером.

E. Интерпрет атором.

Тема 8. Основные вычислительные машины

8.1.Основные вычислительные алгоритмы: Конечные автоматы

В вычислительной технике используются схемы двух классов: комбинационные схемы и цифровые автоматы. Отличительной особенностью КС является наличие функциональной зависимости между входными и выходным сигналами: y(t) = f(x(t)). Причем при отсутствии входных сигналов выходные сигналы также отсутствуют, поскольку такие схемы не имеют памяти. В отличии КС схемы второго класса содержат в своем составе элементы памяти (запоминающие элементы). Эти схемы называются цифровыми автоматами (ЦА) или просто автоматами. В ЦА выходные сигналы в данный момент времени зависят не только от значения входных сигналов в тот же момент времени, но и от состояния схемы, которое, в свою очередь, определяется значениями входных сигналов, поступивших в предшествующие моменты времени. Введем основные понятия и определения.

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

8.2.Конечные автоматы. Кодирование информации

Информацию, поступающую на вход автомата, а так же выходную информацию, принято кодировать конечной совокупностью символов. Эту совокупность называют алфавитом, отдельные символы, образующие алфавит – буквами, а любые упорядоченные последовательности букв – словами в этом алфавите. Например: в алфавите X = (x₁, x₂), состоящем из двух букв, словами будут: x₁, x₂, x₁x₁, x₁x₂, x₂x₁, x₂x₂, x₁x₁x₁ и т.д.

Наряду со словами, состоящими не менее чем из одной буквы, введем слово, не содержащее ни одной буквы, которое будем обозначать символом е и называть пустым словом или пустой буквой.

Математической моделью реального КА является абстрактный автомат, который имеет один входной канал и один выходной канал (рис. 4.1):

X(x1, …, xF)

--->

A(a0, ..., aM)

--->

Y(y1, …, yG).

Рис. 4.1. Абстрактный автомат

Автомат функционирует в дискретные моменты времени, интервал между которыми Т называется тактом. При этом в каждый дискретный момент времени на вход автомата поступает одна буква входного алфавита, автомат переходит из одного состояния в другое и выдается одна буква выходного алфавита. В зависимости от того, как задается длительность такта Т, различают автоматы синхронного действия (T = const) и асинхронного действия (T≠const). Мы будем рассматривать, в основном, синхронные автоматы, функционирующие в дискретные моменты времени, которые можно обозначить целыми неотрицательными натуральными числами t = 0, 1, 2, 3, … , имеющими смысл номера такта.

Для задания любого КА S необходимо задавать совокупность из пяти объектов : S{A, X, Y, d, l}, где A = {a₀, a₁, a₂, ..., a_m, ..., a_M} – множество состояний автомата, X = {x₁, x₂, …, x_f ,…, x_F} – множество входных сигналов или входной алфавит, Y = {y₁, y₂, …, y_g,…, y_G} – множество выходных сигналов или выходной алфавит, d – функция переходов, определяющая состояние автомата в момент времени (t + 1) в зависимости от состояния автомата и входного сигнала в момент времени t, т.е. a(t + 1) = d [a(t), x(t)], 1 – функция выходов, определяющая значение выходного сигнала в зависимости от состояния автомата и входного сигнала в тот же момент времени, т.е. y(t) = l[a(t), x(t)]. Если множества А, Х и У конечны, то автомат называется конечным. Автомат работает следующим образом. В каждый момент времени t он находится в определенном состоянии a(t) из множества А возможных состояний, причем в начальный момент времени t = 0 он находится в состоянии a₀. Автомат воспринимает входной сигнал x(t), выдает выходной сигнал y(t) = l[a(t), x(t)] и переходит в состояние a(t + 1) = d[a(t), x(t)]. Другими словами, абстрактный автомат каждой паре символов a(t) и x(t) ставит в однозначное соответствие пару символов a(t + 1) и y(t). Такие автоматы называют детерминированными.

8.3.Машина Тьюринга. Машина Поста

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

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

Машина Поста

Машина Поста (МП) - абстрактная вычислительная машина, предложенная Эмилем Л. Постом (Emil L. Post), которая отличается от машины Тьюринга большей простотой. Обе машины эквивалентны и были созданы для уточнения понятия алгоритм.

Принцип работы

МП состоит из каретки (или считывающей и записывающей головки) и разбитой на секции бесконечной в обе стороны ленты (см. пример ниже). Каждая секция ленты может быть либо пустой - 0, либо помеченной меткой 1. За один шаг каретка может сдвинуться на одну позицию влево или вправо, считать, поставить или уничтожить символ в том месте, где она стоит. Работа МП определяется программой, состоящей из конечного числа строк. Всего команд шесть:

	N.   →   J	сдвиг вправо
	N.   ←   J	сдвиг влево
	N.   1     J	запись метки
	N.   0     J	удаление метки
	N.   ?   J1, J0	условный переход по метке
	N.   Stop	останов

где N. - номер строки, J - строка на которую переходит управление далее.

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

работа может закончиться невыполнимой командой (стирание несуществующей метки или запись в помеченное поле);

работа может закончиться командой Stop;

работа никогда не закончится.

1. 0 // cycle P 22. → // renew Q 2. ← 23. 1 3. ? 5,4 24. → 4. Stop 25. ? 26,23 5. → 26. ← 6. ? 7,5 27. 0 7. → 28. ← 8. ? 7,9 29. ? 28,30 9. ← 30. ← 10. 0 // cycle Q 31. ? 1,30 11. ← 12. ? 13,22 13. → 14. ? 15,13 15. → 16. ? 15,17 17. 1 18. ← 19. ? 18,20 20. ← 21. ? 10,20

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

Тесты к теме

1.Лицензионное програмное обеспечение защищенно:

1. Физическим лицом создавшим данное програмное обеспечение:

2. Частным

3. в килобайтах

4. в мегагерцах

5. в мегабайта

2.Тип документа – это:

1. Объем документа

2. Месторасположение документа на жестком диске

3. Картинка, которая представляет собой какой-либо файл в Windows

4. Название документа

5. Расширение имени файла-документа

3. Информатика — это:

A) Наука, изучающая структуру и общие свойства информации и

информационные процессы в природе, обществе, технике.

B) Совокупность Аппаратных и программных средств вычислительной техники.

C) Обрабатываемые компьютером данные.

D) Совокупность средств вычислительной техники.

Е) Программное обеспечение компьютеров.

4. Какой раздел информацики разрабатывает общие принципы построения вычислительных систем?

А) Вычислительная техника

B) прграммирование

С) системы проектирования

Д) экспертные системы

Е) искусственный интеллект.