Элементарные алгоритмические структуры

Отчетность

I семестр Программы на 20 баллов Контрольная Коллоквиум (?) Зачет

II семестр Программы на 10 баллов (до 1 апреля) Контрольная Курсовая работы Экзамен

Содержание курса

I семестр	лек. 1- 7 лек. 8-12 лек.13-17	Основы алгоритмизации, структурное программирование. Технологии программирования, реализация на ТР Модули, стандартные модули.
II семестр	лек.1-7 лек. 8- 14 лек. 15-17	Абстрактные Структуры Данных (АСД), реализация на ТР. Технологии программирования, реализация на языке Fortran Общие вопросы программирования

Дальнейшее обучение программированию (по семестрам)

	Экзамен	Зачет
Основы информатики (процедурное программирование)		1
Основы информатики (структуры данных)	2
Методы разработки программного обеспечения (ООП)	3
Языки и методы программирования (Прикладное программное обеспечение)	3	4
Машинно-ориентированные языки		4
Компьютерные технологии обучения		4
Ассемблер	5
Компьютерная графика	6	5
Архитектура компьютеров		6
Базы данных		7
Операционные системы	7
Проектирование трансляторов	7

 

 

Рекомендуемая литература

· Йенсен К., Вирт Н. Паскаль: руководство для пользователя. – М.: Финансы и статистика, 1989.

· Фаронов В.В. Турбо-Паскаль 7.0. Начальный курс. Учебное пособие. М. 1997.

· Ван Тассел Д. Стиль, разработка, эффективность и испытания программ. -М.: Мир. 1985.

· Дал У., Дейкстра Э., Хоар К. Структурное программирование. - М.: Мир, 1975.

· Горелик А.М., Ушакова В.Л., Шура-Бура М.Р. Мобильность программ на Фортране. "Ф и С", 1984.

· Боровин Г.К., Комаров М.М., Ярошевский В.С. Ошибки-ловушки при программировании на Фортране. Статистика, 1989.

· Вирт Н. Алгоритмы и структуры данных. – С-П, 2001.

· Дал У., Дейкстра Э., Хоар К. Структурное программирование. - М.: Мир, 1975.

· Программирование на языке Паскаль. Задачник. Под ред. О.Ф.Кусковой. Питер, 2002.

I семестр

Лекция 1

Алгоритм. Понятие алгоритма

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

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

Алгоритмические языки

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

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

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

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

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

Здесь этап 1 – творческие усилия составителя алгоритма, этап 2 – формализованный перевод алгоритма в текст на алгоритмическом языке, этап 3 – трансляция текста с алгоритмического языка в коды машины.

Запись алгоритма

Условимся записывать алгоритм с помощью следующих обозначений:

a). Элементарная операция присваивания. В прямоугольнике записывается сама операция.

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

c). Элементарная операция вывода. В параллелограмме записывается список переменных и констант, значения которых должны быть выведены. В данном случае выводится значение единственной переменной Y.

Будем считать, если это не оговорено особо, что ввод данных осуществляется с клавиатуры, а вывод – на экран монитора.

d). Подалгоритм, требующий дальнейшей детализации. В прямоугольнике с двойными боковыми ребрами записывается имя подалгоритма. В данном случае имя подалгоритма «Ф».

e). Решение. С помощь этой конструкции можно осуществлять ветвление алгоритма в зависимости от значения логического выражения Усл внутри ромбика. Если значение логического выражения «истина», то осуществляется переход по стрелке «да», в противном случае по стрелке «нет». Условимся всегда стрелку «да» рисовать влево, стрелку «нет» - вправо.

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

Элементарные алгоритмические структуры

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

Структура a) – линейная. Действия выполняются последовательно – сначала выполняется фрагмент Ф1, затем фрагмент Ф2. Структура b) – выбор. В зависимости от истинностного значения логического выражения Усл выполняется либо фрагмент Ф1, либо фрагмент Ф2. Структура с) – цикл. Многократно повторяется фрагмент Ф1 – тело цикла, перед каждым последующим выполнением тела цикла выполняется фрагмент Ф2 – модификатор. Логическое выражение Усл является условием выхода из цикла.

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

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

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