Razdel_13_Osn_alg_i_i_progr_ya_11_05_10

Часть 13. Основы алгоритмизации и программирования

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

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

лизированные редакторы, которые ориентированы на конкретный язык программирования и позволяют в процессе ввода текста выделять ключе-

вые слова и идентификаторы разными цветами и шрифтами. Подобные ре-

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

томатически проверять правильность синтаксиса программы непосред-

ственно во время ее ввода.

2.Исходный текст с помощью программы-компилятора переводится

вмашинный код. Если обнаружены синтаксические ошибки, то результи-

рующий код создан не будет. На этом этапе уже возможно получение го-

товой программы, но чаще всего в ней не хватает некоторых компонентов,

поэтому компилятор обычно выдает промежуточный объектный код (дво-

ичный файл, стандартное расширение .OBJ).

3. Исходный текст большой программы состоит, как правило, из не-

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

тем надо объединить в одно целое. Кроме того, к ним надо добавить ма-

шинный код подпрограмм, реализующих различные стандартные функции

(например, вычисляющих математические функции sin или In). Такие функции содержатся в библиотеках (файлах со стандартным расширением

.LIB), которые поставляются вместе с компилятором. Сгенерированный код модулей и подключенные к нему стандартные функции надо не просто объединить в одно целое, а выполнить такое объединение с учетом требо-

ваний операционной системы, то есть получить на выходе программу, от-

вечающую определенному формату. Объектный код обрабатывается спе-

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

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

21

Часть 13. Основы алгоритмизации и программирования

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

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

.ЕХЕ.

Интегрированные системы программирования

Итак, для создания программы нужны:

•текстовый редактор;

•компилятор;

•редактор связей;

•библиотеки функций.

Как правило, в стандартную поставку входят как минимум три последних компонента, но хорошая интегрированная система включает в себя и спе-

циализированный текстовый редактор, причем почти все этапы создания программы в ней автоматизированы: после того как исходный текст вве-

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

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

даются сообщения о найденных ошибках. В современных интегрирован-

ных системах имеется еще один компонент — отлад чику который позво-

ляет анализировать работу программы во время ее выполнения. С его по-

мощью можно последовательно выполнять отдельные операторы исходно-

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

но.

22

Часть 13. Основы алгоритмизации и программирования

Среды быстрого проектирования

В последние несколько лет в программировании (особенно в про-

граммировании для операционной системы Windows) наметился так назы-

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

ботки графических приложений была сложность создания различных эле-

ментов управления и контроля их работы. Достаточно взглянуть на окно любой Windows-npoгpaммы. В нем имеется множество стандартных эле-

ментов управления (кнопки, пункты меню, списки, переключатели и т. д.).

Очень трудоемко вручную описывать процесс создания этих элементов в соответствии с требованиями Windows, на глазок определять координаты,

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

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

рого проектирования (Rapid Application Development, CAD-среды). Все не-

обходимые элементы оформления и управления создаются и обслужива-

ются не путем ручного программирования, а с помощью готовых визуаль-

ных компонентов, которые с помощью мыши «перетаскиваются» в проек-

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

ствующих элементов. При этом вспомогательный исходный текст про-

граммы, ответственный за создание и работу этих элементов, генерируется

RAD-средой автоматически, что позволяет сосредоточиться только на ло-

гике решаемой задачи. В результате программирование во многом заменя-

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

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

ются библиотеки компонентов — объектные репозитории. Компоненты

23

Часть 13. Основы алгоритмизации и программирования

выступают в роли «строительных кирпичиков», позволяющих собирать го-

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

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

1.1.12Архитектура программных систем

В то время как большинство автономных приложений: офисные про-

граммы, среды разработки, системы подготовки текстов и изображений -

выполняются на одном компьютере, крупные информационные комплексы

(например, система автоматизации предприятия) состоят из десятков и со-

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

выполняясь на разных компьютерах. В таких случаях говорят, что они ра-

ботают в различной программной архитектуре. Она делится на следую-

щие группы.

Автономные приложения. Работают на одном компьютере.

Приложения в файл-серверной архитектуре. Компьютеры пользова-

телей системы объединены в сеть, при этом на каждом из них (на клиент-

ском месте) запущены копии одной и той же программы, которые обра-

щаются за данными к серверу — специальному компьютеру, который хра-

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

родействием, большим объемом памяти, на нем установлена специальная

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

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

деляется в транзакцию — элементарную операцию по обработке данных,

имеющую фиксированное начало, конец (успешное или неуспешное за-

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

24

Часть 13. Основы алгоритмизации и программирования

наличия на них достаточно производительных ПК (это так называемые си-

стемы с толстым клиентом — программой, которая выполняет всю обра-

ботку получаемой от сервера информации).

Приложения в клиент-серверной архитектуре. Эта архитектура по-

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

временного доступа к данным способен еще выполнять программы (обыч-

но выполняются СУБД — тогда сервер называется сервером баз данных),

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

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

Запускаемые на них приложения реально осуществляют небольшие объе-

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

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

ходит из строя, то работа всей системы останавливается. Поэтому в неко-

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

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

новлена специальная программа—монитор транзакций, которая оптими-

зирует обработку транзакций и балансирует нагрузку на серверы. В боль-

шинстве практических случаев все серверы соединены последовательно —

позвенно, и выход из строя одного звена если и не останавливает всю рабо-

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

Приложения в распределенной архитектуре. Чтобы избежать недо-

статков рассмотренных архитектур, были придуманы специальные техно-

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

торые можно запускать на любых серверах, связанных в сеть (компоненты

25

Часть 13. Основы алгоритмизации и программирования

как бы распределены по сети). Основное преимущество подобного подхо-

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

граммы-мониторы, которые следят за корректностью работы компонентов и позволяют им «переговариваться» между собой, сразу перезапуская вре-

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

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

зователем, осуществляется с произвольного клиентского места. При этом,

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

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

гии — CORBA консорциума OMGJava Beans компании Sun и СОМ+/.NET

корпорации Microsoft.

Основные системы программирования

Из универсальных языков программирования сегодня наиболее по-

пулярны следующие:

• Бейсик (Basic) — для освоения требует начальной подготовки (об-

щеобразовательная школа);

•Паскаль (Pascal) — требует специальной подготовки (школы с углубленным изучением предмета и общетехнические вузы);

•Си++ (C++), Ява (Java), Си Шарп (С#) — требуют профессиональ-

ной подготовки (специализированные средние и высшие учебные заведе-

ния).

26

Часть 13. Основы алгоритмизации и программирования

Для каждого из этих языков программирования сегодня имеется не-

мало систем программирования, выпускаемых различными фирмами и ориентированных на различные модели ПК и операционные системы.

Наиболее популярны следующие визуальные среды быстрого проектиро-

вания программ для Windows:

•Basic: Microsoft Visual Basic;

•Pascal: Borland Delphi;

•C++ : Microsoft Visual C++ ;

•Java: BorlandJBuilder;

•C#: Microsoft Visual Studio .NE, Borland C#Builder.

Для разработки серверных и распределенных приложений можно ис-

пользовать систему программирования Microsoft Visual C++, продукты фирмы Borland, практически любые средства программирования mjava.

Алгоритмическое (модульное) программирование

Алгоритм — это формальное описание способа решения задачи путем разбиения ее на конечную по времени последовательность действий (эле-

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

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

риям (например, очевидности) не имеет смысла детализировать. Основная идея алгоритмического программирования — разбиение программы на по-

следовательность модулей, каждый из которых выполняет одно или не-

сколько действий. Единственное требование к модулю — чтобы его вы-

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

чительной). Алгоритм на выбранном языке программирования записыва-

ется с помощью команд описания данных, вычисления значений и управ-

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

27

Часть 13. Основы алгоритмизации и программирования

2 Словесные алгоритмы

2.1 Определение алгоритма

Алгоpитм — точное и понятное пpедписание исполнителю со-

веpшить последовательность действий, направленных на решение по-

ставленной задачи.

Название "алгоритм" произошло от латинской формы имени средне-

азиатского математика аль-Хорезми — Algorithmi. Алгоритм — одно из основных понятий информатики и математики.

2.2 "Исполнитель алгоритма"

Исполнитель алгоритма — это некоторая абстрактная или реальная

(техническая, биологическая или биотехническая) система, способная вы-

полнить действия, предписываемые алгоритмом.

Исполнителя хаpактеpизуют:

среда;

элементарные действия;

система команд;

отказы.

Сpеда (или обстановка) — это "место обитания" исполнителя.

Система команд. Каждый исполнитель может выполнять команды только из некоторого строго заданного списка — системы команд испол-

нителя. Для каждой команды должны быть заданы условия применимо-

сти (в каких состояниях среды может быть выполнена команда) и описаны

результаты выполнения команды.

После вызова команды исполнитель совершает соответствующее

элементаpное действие.

28

Часть 13. Основы алгоритмизации и программирования

Отказы исполнителя возникают, если команда вызывается при не-

допустимом для нее состоянии среды.

Обычно исполнитель ничего не знает о цели алгоритма. Он выполня-

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

В информатике универсальным исполнителем алгоритмов является компьютер.

2.3 Свойства алгоритмов

Основные свойства алгоритмов следующие:

Понятность для исполнителя — т.е. исполнитель алгоритма дол-

жен знать, как его выполнять.

Дискретность (прерывность, раздельность) — т.е. алгоритм дол-

жен представлять процесс решения задачи как последовательное выполне-

ние пpостых (или ранее определенных) шагов (этапов).

Опpеделенность — т.е. каждое пpавило алгоpитма должно быть четким, однозначным и не оставлять места для пpоизвола. Благодаpя этому свойству выполнение алгоpитма носит механический хаpактеp и не тpебу-

ет никаких дополнительных указаний или сведений о pешаемой задаче.

Pезультативность (или конечность). Это свойство состоит в том,

что алгоpитм должен пpиводить к pешению задачи за конечное число ша-

гов.

Массовость. Это означает, что алгоpитм pешения задачи pазpаба-

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

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

2.4 Форма записи алгоритмов

На практике наиболее распространены следующие формы представ-

ления алгоритмов:

29

Часть 13. Основы алгоритмизации и программирования

словесная (записи на естественном языке);

графическая (изображения из графических символов);

псевдокоды (полуформализованные описания алгорит-

мов на условном алгоритмическом языке, включающие в себя как элементы языка программирования, так и фразы естественного язы-

ка, общепринятые математические обозначения и др.);

программная (тексты на языках программирования).

2.5Словесный способ записи алгоритмов

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

вольном изложении на естественном языке.

Например. Записать алгоритм нахождения наибольшего общего де-

лителя (НОД) двух натуральных чисел.

Алгоритм может быть следующим:

1.задать два числа;

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

3.определить большее из чисел;

4.заменить большее из чисел разностью большего и меньшего из

чисел;

5.повторить алгоритм с шага 2.

Описанный алгоритм применим к любым натуральным числам и должен приводить к решению поставленной задачи. Убедитесь в этом са-

мостоятельно, определив с помощью этого алгоритма наибольший общий делитель чисел 125 и 75.

Словесный способ не имеет широкого распространения по следую-

щим причинам:

такие описания строго не формализуемы;

страдают многословностью записей;

30