Принципы разработки алгоритмов и программ

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

 линейной структуры,

 разветвляющейся структуры,

 цик­лической структуры.

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

Отметим, что алгоритм заварки чая, приведенный выше, является по своей структуре линей­ным, алгоритм задачи 4.1. — разветвляющимся. Приме­ром циклического алгоритма может служить алгоритм начисления зарплаты согласно правилу задачи 4.1, но не для одного сотрудника, а для группы, например, из 20 человек, т. е. алгоритм, в котором многократно вы­полняются одни и те же операции.

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

Задача 4.2.

Даны длины двух катетов прямоугольного треугольника. Определить периметр этого треуголь­ника. Требуется составить алгоритм решения задачи.

Решение:

1. Выделяем исходные данные и результа­ты (это первое, что должен содержать алгоритм, соглас­но правилам его записи). Исходные данные: А, В — длины катетов. Результат: Р — периметр треугольника.

2. Согласно определению: «Алгоритм — это метод ре­шения задачи...». Следовательно, далее нужно выбрать метод решения задачи — и это самое главное! («нельзя сварить бульон из курицы, не имея курицы»). А зная метод, надо изложить его в соответствии с правилами за­писи алгоритмов, т. е. сначала разбить его на этапы. В нашем случае метод решения задачи на ЭВМ такой:

1. Ввод данных.

2. Вычисление .

3. Вычисление .

4. Вывод Р.

Решение задачи, как видим, состоит из IV этапов.

Далее изображаем каждый из указанных этапов в виде определенной геометрической фигуры (блока) и соединяем их стрелками. В результате получаем схему алгоритма за­дачи (см. рис. 4.2).

Можно сформулировать общие правила построения схемы алгоритма задачи (иногда их называют «Основные принципы алгоритми­зации»):

1. Выявить исходные данные, результаты, дать им имена.

2. Выбрать метод (порядок) решения задачи.

3. Разбить метод решения задачи на этапы (с учетом возможностей ЭВМ).

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

5. В полученной схеме при любом варианте вычислений:

- предусмотреть выдачу результатов или сообщений об их отсутствии;

- обеспечить возможность после выполнения любой опера­ции так или иначе перейти к блоку Останов (к выходу схемы).

Рис. 4.2 Схема алгоритма за­дачи

Введение в вычислительные сети

1.1. Сети: основные понятия

Телематика – это новая научно-техническая дисциплина, предметом кото­рой являются методы и средства передачи информации на рас­стояния, существенно превышающие линейные размеры площа­ди, занимаемой участниками связи. Название дисциплины про­изошло из частей слов “телекоммуникации” и “информатика”.

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

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

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

Вычислительная сеть – информационная сеть, в состав кoторой входит вычислительное оборудование. Компонентами вы­числительной сети могут быть ЭВМ и периферийные устройства, являющиеся источниками и приемниками данных, передаваемых по сети. Эти компоненты составляют оконечное оборудование данных (ООД, или DTE – Data Terminal Equipment). В качестве ООД могут выступать ЭВМ, принтеры, плоттеры и другое вы­числительное, измерительное и исполнительное оборудование автоматических и автоматизированных систем.

Терминал – устройство, предназначенное для взаимодействия пользователя с вычислительной системой или сетью ЭВМ. Состоит из устройства ввода (чаще всего это клавиатура) и одного или нескольких устройств вывода (дисплей, принтер и т.д.).

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

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

Подготовка данных, передаваемых или получаемых ООД от среды передачи данных, осуществляется функциональным бло­ком, называемым аппаратурой окончания канала данных (АКД, или DCE – Data Circuit-Terminating Equipment). АКД может быть конструктивно отдельным или встроенным в ООД бло­ком. ООД и АКД вместе представляют собой станцию данных, которую часто называют узлом сети. Примером АКД может служить модем.

Классификация сетей

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

территориальные – охватывающие значительное географи­ческое пространство; среди территориальных сетей можно вы­делить сети региональные и глобальные, имеющие соответст­венно региональные или глобальные масштабы; региональные сети иногда называют сетями MAN (Metropolitan Area Network), а общее англоязычное название для территориальных сетей – WAN (Wide Area Network);

локальные (ЛВС) – охватывающие ограниченную террито­рию (обычно в пределах удаленности станций не более чем на несколько десятков или сотен метров друг от друга, реже на 1...2 км); локальные сети обозначают LAN (Local Area Network);

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

Особо выделяют единственную в своем роде глобальную сеть Internet. Это всемирная компьютерная сеть, сеть сетей, объединяющая посредством межсетевых интерфейсов многие сети. Internet охватывает американский континент, Европу, Азию. Некоторые сети, входящие в состав Internet, сами по себе велики, другие имеют свои подсети. В настоящее время сеть Internet объединяет более 2,5 млн. компьютеров многих стран мира и доступна нескольким десяткам миллионов пользователей.

С технической точки зрения Internet – объединение транснациональных компьютерных сетей, работающих по самым разнообразным протоколам, связывающим всевозможные типы компьютеров, физически передающих данные по телефонным проводам и оптоволокну, через спутники и радиомодемы. Координацию сети осуществляет Центр информационных сетей при Стенфордском исследовательском институте в Менло Парк, Калифорния.

На российском рынке глобальных вычислительных сетей наиболее активно и эффективно функционируют следующие сетевые структуры: РОСПАК, GLASNET, РЕЛКОМ, ИНФОТЕЛ.

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

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

Развитие интерсетей заключается в разработке средств со­пряжения разнородных подсетей и стандартов для построения подсетей, изначально приспособленных к сопряжению.

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

В зависимости от способа управления различают сети:

“клиент/сервер” – в них выделяется один или несколько узлов (серверы), выполняющих в сети управляющие или специальные обслуживающие функции, а осталь­ные узлы (клиенты) являются терминальными, в них работают пользователи;

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

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

В зависимости от того, одинаковые или неодинаковые ЭВМ применяют в сети, различают сети однотипных ЭВМ, называе­мые однородными, и разнотипных ЭВМ – неоднородные (гете­рогенные). В крупных автоматизированных системах, как пра­вило, сети оказываются неоднородными.

В зависимости от прав собственности на сети последние могут быть сетями общего пользования (public) или частными (private). Среди сетей общего пользования выделяют теле­фонные сети ТфОП (PSTN – Public Switched Telephone Net­work) и сети передачи данных (PSDN – Public Switched Data Network).

Сети также различают в зависимости от используемых в них протоколов и по способам коммутации.

Способы коммутации