Алгоритмы сложной структуры

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

Существуют правила соединения управляющих структур. Они лежат в основе современных методов решения сложных задач. В этих методах сначала разрабатывают решение задачи в общих чертах (без общих деталей), а затем шаг за шагом уточняют детали алгоритма до общего решения. Такой подход называют пошаговой детализацией алгоритма. Он относится к методу разработки “проектирование сверху - вниз”. В этом методе тоже сначала определяют общее решение, а затем производят детализацию до нахождения полного решения.

Методы программирования

Программа - это набор машинных команд, которые следует выполнить компьютеру для реализации определенного алгоритма.

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

Первоначально программисты были вынуждены писать программы в машинных кодах. Критериями оценки разработанных программ становились скорость и малый требуемый объем памяти. Сейчас эти критерии уже не столь важны. Процесс написания программ в машинных кодах был весьма трудоемким. Необходимо было создание программ сделать технологическим процессом. Для этого разработали языки программирования и специальные программы - трансляторы, предназначенные для перевода программы с языка программирования в машинный код.

Ниже приведена одна из возможных классификаций наиболее распространенных языков программирования.

Машинно-ориентированные языки программирования включают в себя собственно машинные коды и язык ассемблер. Каждая команда на языке ассемблера представляет одну машинную команду. Этот язык очень эффективен, так как приближен к машинным кодам. Программирование на этом языке называется “программирование на низком уровне” и требует высокой квалификации программиста. Решение сложных прикладных задач на таких языках очень трудоемко и нецелесообразно. Чаще всего эти языки используются для написания операционных систем (ОС) и программ- оболочек для ОС. Другая группа языков представляет собой проблемно-ориентированные языки. Они разрабатывались специально для программирования прикладных задач, имеющих сложный алгоритм решения. Условно их называют языками высокого уровня. Каждой команде в языке высокого уровня соответствует несколько машинных команд. Текст программы, написанный на языке высокого уровня, называется исходным модулем. Язык высокого уровня “не понятен” машине, поэтому существуют специальные программы-трансляторы, переводящие операторы языка высокого уровня в машинные коды. Существуют два типа программ-трансляторов: компилятор и интерпретатор.

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

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

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

нисходящее проектирование;

модульное проектирование;

структурное программирование;

структурный контроль.

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

Иерархическая модель строится по следующим правилам:

каждый модуль может быть связан только с одним модулем верхнего уровня и с несколькими модулями нижнего уровня;

для каждого модуля нижнего уровня имеется выход в модуль верхнего уровня;

связи между модулями организуются сверху вниз;

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

Модульное программирование предполагает независимое программирование каждого модуля, начиная с верхнего уровня иерархии. При осуществлении тестирования модулей верхнего уровня на модули нижнего уровня ставится "заглушка", чаще всего оператор печати.

Модули добавляются по одному. После окончания разработки каждого модуля тестируется весь комплекс программ в целом.

Модульное программирование позволяет существенно сократить время, необходимое на отладку программ.

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

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

между этими структурами производится передача управления только вперед - от более высокого уровня иерархии к более низкому;

запрещается использовать команду переходов "GOTO".

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

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

АЛГОРИТМИЧЕСКИЕ ЯЗЫКИ

Работы над созданием алгоритмических языков высокого уровня начались еще в 50-х годах. Задачи того времени были связаны с математическими вычислениями и поэтому понятно, что первым алгоритмическим языком оказался FORTRAN (Фортран)— FORmula TRANslator (переводчик формул), разработанный в 1954 г. на фирме IBM под руководством Джона Бэкуса для решения на компьютере задач математического моделирования, математических расчетов, т.е. решения инженерных задач. Этот язык оказал значительное влияние на разработку других языков, он имеет несколько модификаций.

Вскоре в противовес Фортрану был разработан язык ALGOL (Алгол)— Algorithmic Language— алгоритмический язык, предназначенный для решения численных задач. Для его разработки был создан даже международный комитет из видных программистов, желающих противопоставить Фортрану язык, свободный от монополии IBM. Алгол отличается удобством, элементарностью и обозримостью вычислительных программ и алгоритмов. Фундаментальные идеи Алгола стали основополагающими для многих языков высокого уровня, которые разрабатывались одновременно с Фортраном и Алголом.

Фортран позволяет решать очень широкий круг задач, но значительно усложняет решение простых задач, с которыми чаще всего сталкивается основная масса пользователей. Именно поэтому на базе Фортрана был создан более простой язык программирования BASIC (Бейсик)— Beginner's All-purpose Symbolic Instruction Code— универсальный символический код для начинающих, ставший самым популярным языком программирования. Он был разработан в 1965 г. американскими математиками Джоном Кемени и Томасом Курцем для обучения студентов Дортмутского колледжа работе с компьютером. Можно предположить, что название языка позаимствовано авторами у языка «бейсик», который был разработан в прошлом веке англичанами для туземного населения колоний Великобритании. Язык содержал около 300 слов и позволял объясняться практически на любую тему.

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

На языке Бейсик каждая строка программы идентифицируется номером, а управление ходом программы основывается на указании номеров строк. Цикл определяется командами FOR и NEXT между ними.

Вот запись программы для решения задачи: найти сумму нечетных чисел в массиве чисел Т.

100 DIM T (100) - размер массива,

200 READ N - читай N,

300 FOR I = 1 TO N - начиная с I =1 проходить N,

400 READ T (I) - читать весь массив T (I),

500 NEXT I - переход к следующему I,

600 GOSUB 1100 - переход к

700 PRINT S

800 GOTO 2000

900 DATA 4

1000 DATA 23, 34, 7, 9

1100 REM S = сумме нечетных элементов в массиве Т(1...N)

1200 LET S = 0

1300 FOR I = 1 TO N

1400 IF NOT ODD(T(I)) THEN GOTO 1600

1500 LET S = S + T(I)

1600 NEXT I

1700 RETURN

2000 END.

Язык COBOL (Кобол)— Common Business Oriented Language был разработан комитетом, представляющем правительство и промышленность США в 1960 г. Его словарь и структура близки к английскому языку. Этот язык ориентирован на деловые задачи, предназначен для обработки больших массивов данных, платежных ведомостей. Данные в нем структурированы как записи, файлы, таблицы и списки. Он разрабатывался специально для деловых людей, профессионально не связанных с программированием. Кобол широко используется при программировании банковских задач, экономических отношений страховых компаний, т.е. там, где необходима обработка табличных данных.

Язык Pascal (Паскаль), названный в честь французского математика и физика Блеза Паскаля, был разработан математиком Николасом Виртом из Швейцарского федерального технологического института в 1960 г. для структурного программирования. Язык принят к освоению в школах США для учащихся, специализирующихся в области информатики.

Язык Паскаль очень компактный: его описание занимает всего 30 страниц и написанная на нем программа весьма немногословна. Язык позволяет контролировать программную логику.

Например, программа решения задачи— найти и напечатать сумму двух чисел— на Паскале выглядит так:

PROGRAM сумма (input, output);

var a, b, s: integer;

begin read (a, b);

s: = a + b;

write (s);

end.

Язык Паскаль оказался настолько удачным, что был принят за международный стандарт ISO 7185. Он широко применяется в программировании задач на персональных компьютерах, в настоящее время применяются его версии Borland Pascal и Turbo Pascal.

В начале 70-х годов Д. Ритчи из Bell Telephone Laboratories разработал язык С (Си). Он сочетает лучшие свойства языка Ассемблер и универсальных языков программирования. Компилятор Си имеется практически на любом компьютере. На языке Си написаны почти вся операционная система UNIX. Си является компактным языком, поддерживает технологию структурного программирования, используемую в машинах последнего поколения.

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

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

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

В начале 80-х годов появился новый вид программирования - объектно-ориентированное. Суть этого программирования заключается в объединении группы данных в объекты и организации взаимодействия между ними. Из объектно-ориентированных языков наиболее распространенными являются С++ и Java. Язык Java получил распространение в сети Интернет.

В объектно-ориентированном программировании завоевала себе место идея визуального программирования, когда интерфейсная часть программного продукта создается в диалоговом режиме и программа собирается из отдельных программных блоков. Появились языки Visual Basic, Delphi, Visual C ++.

И наконец, нужно сказать о логическом программировании и его представителе - языке Пролог. Язык PROLOG (Programming in Logic - программирование в терминах логики) открыл новую область в программировании - логическое программирование. Язык создан французским ученым А.Кольмероэ в 1973 г. Он описывает объекты и их отношения и состоит из трех действий: задание фактов, относящихся к объектам, и отношений между объектами; задание правил манипулирования объектами и их отношений; задание вопросов об объектах и их отношениях.

ПРОЛОГ используется при разработке систем искусственного интеллекта, он принят в качестве составной компоненты системного программирования в проекте компьютеров 5-го поколения.

ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ

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