Алгоритм –это точно определенная, однозначная последовательность простых (элементарных) шагов, обеспечивающих решение любой задачи из некоторого класса. 5 страница
Эти языки позволяют решить, вообще говоря, любую задачу, хотя трудоемкость решения конкретной задачи в разных языках будет отличаться.
В настоящее время в распоряжении программиста имеется весьма обширный спектр языков-инструментов, из которых для любой конкретной задача можно выбрать тот, что позволяет решить ее оптимальным путем.
6.3 Графическая форма представления алгоритма
Другое название данной формы – схема алгоритма. Графическая форма предназначена только для исполнителя «человек». Главное достоинство такой формы - наглядность. Схема позволяет охватить весь алгоритм сразу, отследить различные варианты его выполнения.
На стадии разработки в блоках можно делать записи как на естественном, так и на формализованном языке. Однако в схемах, как правило, подробное описание конкретных действий выполняется только для простых алгоритмов.
В данной форме для представления отдельных блоков алгоритма используется обусловленный набор геометрических фигур. Принятые обозначения – графические примитивы приведены на рисунке 6.1.
По блок-схеме гораздо проще осуществлять запись алгоритма на каком-либо формальном языке. Правда, синтаксическое богатство языков программирования выше языка графических схем (например, различные виды циклов не имеют собственного представления в языке схем алгоритмов).
Отметим наиболее важные моменты при составлении блок-схем:
- не надо излишне детализировать и усложнять блок-схему; необходимо показывать только основные и наиболее важные для решения шаги;
- используйте только вертикальные и горизонтальные линии;
- линии не должны пересекаться, во избежание пересечений можно пользоваться символами – соединителями;
- указывать направления необходимо для линий, направленных вверх или влево, для других – стрелки необязательны;
- любая линия должна быть направлена к какому-либо блоку;
- в точках разветвления программы необходимо писать слова «да» или «нет» с целью указания выбранного направления.
Примеры схем алгоритмов.
1. Нахождение корней квадратного уравнения
2. Алгоритм Евклида
6.4 Структурная теорема
До середины 60-х годов теории разработки алгоритмов не существовало – процесс разработки целиком определялся опытом и искусством программиста. Однако по мере роста сложности программ возникла необходимость создания методологии их разработки, и она появилась в виде структурного программирования.
Идеи структурного программирования были высказаны в 1965 года Дейкстрой, но сведены в законченную систему правил итальянскими математиками Бомом и Джакопини.
Введем следующее понятие функционального блока.
Функциональный блок – часть алгоритма, организованная как простое действие (то есть имеющее один вход и один выход).
Функциональные блоки связываются между собой с помощью базовых управляющих структур (включаются в поток управления).
Стандартные базовые управляющие структуры:
1. последовательный (линейный) управляющий блок – последовательно выполняется несколько функциональных блоков.
Линейному потоку управления на языке блок схем соответствует структура, приведенная на рисунке 6.2.
Очевидно, что несколько функциональных блоков, связанных линейным потоком управления, могут быть объединены в один функциональный блок.
Второй тип потока управления называется ветвлением – он организует выполнение одного из 2-х функциональных блоков в зависимости от значения проверяемого логического условия (рисунок 6.3).
Если структура содержит два функциональных блока (S1 и S2), то ветвление называется полным. Возможно существование неполного ветвления – при этом один из блоков пуст (обычно это S1).
Третий тип потока управления называется циклическим – он организует многократное повторение функционального блока, пока логическое условие его выполнения является истинным.
Поскольку ветвление и циклический тип управления имеют один вход и один выход, они в целом тоже подходят под определение функционального блока.
Структурная теорема гласит, что с помощью стандартных (базовых) управляющих структур может быть представлен любой алгоритм. Алгоритм, представленный с помощью только базовых структур, называется структурным.
Структурный алгоритм обладает рядом замечательных преимуществ по сравнению с неструктурированным:
- понятность и простота восприятия (так как невелико число структур, которыми он образован);
- проверяемость (для проверки любой из основных структур достаточно убедиться в правильности входящих в нее функциональных блоков);
- модифицируемость (простота изменения структуры алгоритма, поскольку составляющие блоки относительно независимы).
На основе структурной теоремы разработан и широко используется так называемый структурный метод программирования.
Основой метода является использование принципа модульности построения сложных программ. При этом каждый программный модуль организуется в виде стандартного функционального блока (то есть строится из 3-х базовых управляющих структур) и выполняет лишь одну функцию по обработке данных.
Модули обладают определенной автономностью, что позволяет их отладку вести независимо (даже отдельно разрабатывать). Это обеспечивает относительную простую модифицируемость как отдельного модуля, так и программы в целом.
6.5 Основные подходы к разработке алгоритмов
Конечно, когда тебе говорят сделать первый шаг и когда тебе говорят, как это сделать – это не одно и тоже. Нахождение такой точки опоры, также как и понимание того, как с ее помощью найти окончательное решение, требует от человека творческих способностей.
Отметим основные походы к разработке алгоритма.
1. Попытаться решить задачу в обратном порядке. Например, если нужно найти способ порождения определенных выходных данных при заданных входных, то можно попытаться начать решение с выходных данных и вернуться к заданным исходным данным.
(Алгоритм сложения фигурок из листа бумаги – взять сложенную птицу и последовательно развернуть ее, чтобы понять, как сложить?)
2. Найти связанную с исходной задачу, которую легче решить или решение которой уже найдено, а затем попытаться применить это решение к текущей задаче.
3. Применить пошаговую детализацию (нисходящий метод), не пытаясь решить всю задачу с множеством деталей сразу. Разбивая исходную задачу на подзадачи, мы решаем ее за несколько шагов, найти решение которых проще, чем решение всей задачи. Эти шаги могут также быть разбиты на меньшие и так до тех пор, пока вся задача не будет сведена к набору легко решаемых подзадач.
Сегодня это – один из основных подходов к разработке программного обеспечения, так как пошаговая детализация естественно адаптируется к модульному представлению. Пример такого подхода к разработке алгоритма приведен на рисунке 6.4.
Но отсюда не следует делать ошибочный вывод, что любой алгоритм может быть построен с помощью пошаговой детализации.
6.6 Проверка правильности программы
Рассмотрим решение следующей задачи.
У путешественника есть золотая цепь, состоящая из 7 колец. Он должен остановиться в гостинице на несколько дней (но не более 7). Плата за сутки равна 1 кольцу цепочки. Каково наименьшее число колец, на которые нужно разрезать цепь, чтобы платить за гостиницу по одному кольцу каждое утро, не платя за ночлег заранее?
Решение. Можно догадаться, что разрезать нужно не каждое кольцо цепочки. Если мы разрежем 2-ое кольцо, то освобождается и первое, и второе. Следовательно, нужно разрезать только 2, 4, 6 кольца.
Уменьшение числа разрезанных колец приводит к тому, что какие-либо 2 кольца становятся соединенными. Поэтому правильный ответ – 3 кольца.
Действительно ли это правильное решение задачи?
Можно предложить такой вариант решения: Если разрезать только третье кольцо, то мы будем иметь 3 части цепочки, состоящей из 1, 2 и 4 колец. Дальше можно действовать следующим образом:
Первое утро: отдать 1 кольцо.
Второе утро: забрать кольцо и отдать 2.
Третье утро: отдать 1 кольцо.
Четвертое утро: забрать все кольца (1 + 2) и отдать 4 кольца.
Пятое утро: отдать 1 кольцо.
Шестое утро: забрать одно кольцо и отдать 2.
Седьмое утро: отдать 1 кольцо.
Следовательно, первый ответ, который считали правильным, таковым не является. Можно ли быть уверенным, что найденное решение правильное? Меньше 1 кольца нельзя разрезать, следовательно, новое решение минимально.
Этот пример подчеркивает различие между решением, которое считается правильным, и решением, которое действительно является таковым. Не всегда это – одно и тоже. Известно большое количество историй о ПО, которое считалось правильным, однако переставало работать в критических ситуациях из-за возникновения каких-либо условий.
Таким образом, проверка правильности программного обеспечения имеет большое значение, а поиск эффективных методов проверки является активно развивающейся областью ВТ.
Формальные методы проверки правильности программ не разработаны настолько хорошо, чтобы их можно было с легкостью применять к общим прикладным задачам.
В результате в настоящее время в большинстве случаев программное обеспечение проверяется посредством его тестирования при различных условиях, что очень ненадежно.
Проверка путем тестирования доказывает только то, что программа работает правильно в случае, предусмотренном тестированием. Любые дополнительные умозаключения – просто предположения.
Следовательно, ошибки в программе, так же как наша ошибка в решении задачи о цепочке, могут оставаться незамеченными.
Контрольные вопросы и задачи
1. Понятие алгоритма.
2. Перечислите основные свойства алгоритмов.
3. Почему естественный язык не может использоваться для представления алгоритмов для исполнителя «компьютер»?
4. Какие формы представления алгоритмов используются для исполнителя «человек»?
Задача 1. Постройте схему алгоритма и напишите его представление на псевдокоде для решения задачи: по координатам точки (x, y) определить номер координатной четверти, которой принадлежит точка.
Задача 2. Следующая программа вычисляет произведение двух неотрицательных целых чисел x и y, суммируя x раз число y (то есть 3*4 = 4+4+4). Является ли программа правильной?
Алг Mult (x, y);
произв := y; 0 × 4
Счетчик := 1; Произв. 4
Пока (счетчик < x) повторять Счетчик 1
(произв :=произв + y; Пока – не выполняется
счетчик := счетчик + 1) ® результат Произв. = 4,
Вывод произв.; а должен быть 0
Конец.
7 Начальные сведения о вычислительных сетях
7.1 Классификация вычислительных сетей
Ранние компьютерные сети состояли из машин, соединяемых только для передачи файлов. Сегодня взаимодействие между компьютерами имеет более широкое применение. Так, в условиях вычислительной сети предусмотрены возможности:
- организации параллельной обработки данных многими ЭВМ;
- создания распределенных баз данных, размещаемых в памяти различных ЭВМ;
- специализации отдельных ЭВМ для эффективного решения определенных классов задач;
- резервирования вычислительных мощностей и средств передачи данных на случай выхода из строя отдельных из них с целью быстрого восстановления нормальной работы сети;
- стабилизации и повышения уровня загрузки ЭВМ и дорогостоящего периферийного оборудования; и т.д.
Компьютерные сети разделяют на локальные и глобальные. Локальная сеть обычно состоит из компьютеров, объединенных в отдельный комплекс. Например, компьютеры, используемые в лаборатории или в организации, обычно связаны локальной сетью. Глобальная сеть объединяет машины, которые могут находиться и в соседних городах, и в разных концах света.
По второму классификационному признаку – типу ЭВМ, включенных в состав сети, – сети делятся на:
однородные (гомогенные) – состоят из программно-совместимых ЭВМ;
неоднородные (гетерогенные) – ЭВМ, входящие в сеть, программно не совместимы.
По характеру реализуемых функций сети делятся на:
вычислительные – предназначенные для решения задач управления на основе вычислительной обработки исходной информации;
информационные – предназначенные для получения справочных данных по запросу пользователей;
смешанные – в которых реализуются вычислительные и информационные функции.
Следующий классификационный признак – способ управления:
- децентрализованное управление – каждая ЭВМ сети включает полный набор программных средств для координации сетевых операций. Сети такого типа достаточно сложны и дороги.
- централизованное управление – есть «главная» ЭВМ, которая выполняет координацию сетевых операций.
По структуре построения (топологии), сети делятся на:
- радиальные (звезда) .
В центре находится пассивный соединитель или активный повторитель - достаточно простые и надежные устройства. Для защиты от нарушений в кабеле используется центральное реле, которое отключает вышедшие из строя кабельные лучи. Для звезды с интеллектуальным центром центральный узел отвечает за маршрутизацию данных через себя и локализацию неисправностей.
- кольцевые .
Для топологии «кольцо» сигналы передаются только в одном направлении. Конечно, это замедляет передачу данных в кольце, причем длительность задержки определяется числом компьютеров, включенных в сеть. При отказе канала между двумя узлами происходит отказ всей сети.
- многосвязные .
Данная конфигурация устойчива к перегрузкам и отказам, у нее высокая надежность, однако достаточно сложная логика обмена данными.
- общая шина .
Для такой топологии характерна простота управления, простота расширения сети, минимальный расход кабеля. Однако труден поиск неисправностей и необходимо резервирование главной шины.
- иерархические .
Каждое из устройств обеспечивает непосредственное управление устройствами низшими по иерархии. Отличается простотой в общем управлении сетью, хорошими возможностями при расширении сети.
При выборе сетевой топологии преследуются следующие цели:
- обеспечение максимальной надежности;
- выбор маршрута по тракту наименьшей стоимости;
- предоставление конечному пользователю наиболее удобных времени ответа и пропускной способности.
И, наконец, по правам на внутреннее строение сети, сети делятся на:
- открытые сети (Интернет) – всеобщее достояние;
- закрытые сети (системы Novell) – права принадлежат некоторой компании (корпорации).
7.2 Локальные вычислительные сети (ЛВС)
ЛВС - это сети на базе ПЭВМ (ПК), ориентированные на объединение вычислительных машин и периферийных устройств, сосредоточенные на небольшом пространстве (в пределах одного помещения, здания, группы зданий, в пределах нескольких комнат).
Сравнительно низкая стоимость, высокая живучесть и простота комплексирования эксплуатации ЛВС, оснащенность современными операционными системами, высокоскоростными средствами передачи данных и т.д. способствовали их быстрому распространению для автоматизации управленческой деятельности в учреждениях, на предприятиях, а также для создания на их основе информационных, измерительных и управляющих систем технологических и производственных процессов.
При незначительной удаленности вычислительного оборудования наиболее эффективным средством связи между отдельными аппаратными компонентами ЛВС является последовательный интерфейс.
Классификация ЛВС.
К 1-ой группе относятся ЛВС, ориентированные на массового пользователя. Такие ЛВС объединяют в основном ПК с помощью систем передачи данных, имеющих низкую стоимость и обеспечивающих передачу информации на расстояние 100 – 500 м со скоростью 20 – 50 кбит/с.
Ко 2-ой группе относятся ЛВС, объединяющие кроме ПЭВМ микропроцессорную технику, встроенную в технологическое оборудование (средства обработки документальной информации, кассовые аппараты, сканеры и т.п.). Система передачи данных таких ЛВС обеспечивает передачу информации на расстояние до 1 км со скоростью 50кбит - 1 М бит/с.
К 3-ей группе относятся ЛВС, объединяющие ПЭВМ, мини-ЭВМ и ЭВМ среднего класса. Эти ЛВС используются для организации управления сложными производственными процессами с применением робототехнических комплексов, для создания систем управления научными исследованиями и т.п.
Для ЛВС 4-ой группы характерно объединение в своем составе всех классов ЭВМ. Такие ЛВС применяются в сложных системах управления крупным производством и даже отдельной отраслью. Скорость передачи здесь от 10 ¸ 50 М Бит/с на расстояние до 10 км.
По топологическим признакам ЛВС делятся на:
- ЛВС с общей шиной – одна из машин служит в качестве системного обслуживающего устройства, обеспечивающего централизованный доступ к общим файлам и БД, печатающим устройствам и другим вычислительным ресурсам.
ЛВС данного типа приобрели большую популярность благодаря низкой стоимости, высокой гибкости и скорости передачи данных, легкости расширения сети.
К недостаткам шинной топологии относят необходимость использования довольно сложных протоколов и уязвимость в отношении физических повреждений кабеля;
- ЛВС с кольцевой топологией характеризуется тем, что информация по кольцу может передаваться только в одном направлении и все подключенные компьютеры могут участвовать в ее приеме и передаче.
При этом абонент – получатель должен пометить полученную информацию маркером, иначе могут появиться «заблудившиеся» данные, мешающие нормальной работе сети.
Как последовательная конфигурация, кольцо особенно уязвимо в отношении отказов: выход из строя какого-либо сегмента кабеля приводит к прекращению обслуживания всех пользователей;
- иерархическая ЛВС («дерево») представляет собой более развитый вариант структуры ЛВС, построенной на основе общей шины.
Дерево образуется путем соединения нескольких шин с корневой системой, где размещаются самые важные компоненты ЛВС.
Оно обладает необходимой гибкостью, чтобы охватить средствами ЛВС несколько этажей в здании или несколько зданий на одной территории и реализуется, как правило, в сложных системах, насчитывает десятки и даже сотни абонентов ;
- радиальная («звезда») – в центре сети обычно размещается коммутирующее устройство, обеспечивающее жизнеспособность системы. ЛВС подобной конфигурации находят применение в автоматизированных учрежденческих системах управления, использующих централизованные БД.
Такие сети менее надежны, чем сети с общей шиной или иерархические, но эта проблема решается дублированием аппаратуры центрального узла. Еще один недостаток такой топологии – значительное потребление кабеля;
- наиболее сложной и дорогой является многосвязная топология, в которой каждый узел связан со всеми другими узлами сети.
Эта топология сети применяется очень редко, в основном там, где требуются исключительно высокие надежность сети и скорость передачи данных.
На практике встречаются гибридные ЛВС, приспособленные к требованиям конкретного заказчика и сочетающие фрагменты различных топологий.
7.3 Организация обмена информацией в ЛВС
Характер топологии сети оказывает влияние на организацию обмена информацией между ее абонентами. Как правило, такой обмен информацией осуществляется с помощью фиксированных блоков информации, которые называются пакетами.
Любой пакет, независимо от структуры ЛВС, включает в себя адреса получателя и отправителя, собственно данные и контрольную сумму
| Адрес получателя | Адрес отправителя | Данные | Контрольная сумма |
Каждое устройство принимает пакеты, которые ему адресованы, проверяет корректность полученных данных по контрольной сумме и посылает соответствующий ответ устройству-отправителю. Поскольку одно устройство может получать пакеты от нескольких устройств, адрес отправителя является обязательной частью формата.
Стремительное развитие ЛВС, использование в них технических и программных средств, производимых часто в разных странах, сделали необходимыми принятие международных соглашений, стандартов на передачу информации, то есть на характеристики каналов связи, стыковки ПЭВМ с каналами связи, правила стыковки сетей друг с другом, протоколы межмашинного и межсетевого взаимодействия и т.д.
Международная организация по стандартизации ISO подготовила модель взаимодействия открытых информационных сетей. Эта модель разработана и принята в качестве международного стандарта и включает 7 уровней взаимодействия на строго иерархической основе по принципу «снизу – вверх».
Определены следующие уровни взаимодействия:
- физический (сопряжение с каналом связи);
- канальный (управление передачи информации по каналу);
- сетевой («прокладывание» пути между системой – отправителем и системой – получателем);
- транспортный (управление процессом передачи по этому пути);
- сеансовый;
- прикладной;
- уровень представления данных.
Каждый из названных выше уровней выполняет указания уровня, расположенного над ним. Задача всех 7 уровней – обеспечение надежности взаимодействия прикладных процессов
В принципе, в любую структуру ЛВС может быть подключена любая ПЭВМ, если она способна выполнять не только прикладные процессы, но и процессы взаимодействия. Это значит, что машина, ставшая абонентом сети, должна иметь: аппаратуру сопряжения с сетью и передачи данных; специальное программное обеспечение, реализующее процессы взаимодействия; оперативную память достаточной емкости для хранения специального программного обеспечения.
В любой ЛВС могут использоваться различные физические носители сигналов. Простейшей физической средой является витая пара. Это самый дешевый носитель, но у него есть и недостатки: плохая защищенность от электрических помех, простота несанкционированного подключения, ограниченная дальность и скорость передачи данных.
Многожильные кабели дороже, чем витая пара, но позволяют повысить скорость передачи. Наиболее распространенной средой передачи данных в ЛВС является коаксиальный кабель, обладающий хорошей электрической изоляцией и высокой скоростью передачи данных.
В последнее время все большее применение находят световоды (оптоволоконные кабели), которые имеют небольшую массу, высокую скорость передачи (до 1 Гбит/с), невосприимчивы к электрическим помехам, полностью пожаро- и взрывобезопасны, сложны для несанкционированного подключения. Возможно использование в ЛВС и радиосреды.
7.4 Методы доступа в ЛВС (управление правом отправки
сообщения)
Протокол кольцевой сети с маркерным доступом (token ring protocol).
Он был разработан IBM в 70-х гг. ХХ в. и до сих пор остается распространенным протоколом для сетей с кольцевой топологией.
Согласно этому протоколу все машины сети передают сообщения в единственном общем для всех направлении. Это означает, что все сообщения, пересылаемые по сети, перемещаются в одном направлении, переходя от машины к машине. Когда сообщение достигает пункта назначения, машина-адресат сохраняет его копию и пересылает ее дальше по сети. Когда копия сообщения достигает машины, пославшей его, эта машина узнает, что сообщение достигло пункта назначения и удаляет его из сети.
Как разрешить ситуацию, когда несколько машин требуют отправки сообщений? Или какая-нибудь одна требует постоянной отправки своих собственных сообщений, а не передает сообщения других машин?
Для того, чтобы разрешить эту проблему, по сети пересылается уникальная последовательность битов, которая называется маркером (token). Владение этим маркером дает машине право отправки своего сообщения. Машине, не владеющей маркером, разрешается только пересылать полученное сообщение следующей машине. Обычно каждая машина пересылает маркер, так же как она пересылает сообщение.
Однако, если машине, получившей маркер, требуется поместить в сеть свое сообщение, она отсылает одно сообщение и удерживает маркер. Когда сообщение завершает свой цикл по кольцевой сети, машина передает маркер следующей машине. Точно так же, следующая машина, получив маркер, может или сразу переслать его или отправить свое сообщение, прежде чем послать маркер следующей. Таким образом, каждая машина сети имеет равную возможность отправки сообщения по мере перемещения маркера по сети.
Другой протокол управления правом отсылки сообщения используется в Ethernet, который представляет собой распространенную версию сети с шиной топологией. (Сегодня это наиболее распространенный метод объединения персональных компьютеров в сеть. Платы контроллера Ethernet для ПК легко доступны и просто устанавливаются.)
Право отправлять сообщение контролируется протоколом CSMA/CD (Carrier Sense Multiple Access with Collision Detection) – множественный доступ с контролем несущей и обнаружением конфликтов). Согласно этому протоколу каждое сообщение, отправляемое какой-либо машиной, пересылается всем машинам сети. Каждая ЭВМ контролирует все сообщения, но хранит только адресованные ей. Для того, чтобы отправить сообщение, машина ждет освобождения шины, а затем начинает отправку, продолжая контролировать шину.
Если в это время другая машина также начинает отправлять сообщение, обе машины обнаруживают конфликт и останавливаются на некоторый произвольный промежуток времени, а затем пробуют отправить сообщение снова. (В результате получается метод, подобный тому, который используется группой людей во время беседы. Если 2 человека начинают говорить одновременно, они оба на какое-то время замолкают. Различие заключается в том, что люди произносят при этом «Извините, что вы хотели сказать?», «Нет, нет, вы первый!», в то время как компьютер просто повторяет попытку отправить сообщение.)
8 Глобальные вычислительные сети
Наиболее ярким примером глобальной интерсети является Интернет (Internet), который развился из исследовательской программы, созданной в 1973 году Управление перспективных исследовательских проектов (Defense Advanced Research Project Agency – DARPA). Целью этого проекта был поиск средств объединения множества различных компьютерных сетей, чтобы они могли функционировать как единая надежная связная система.
Сегодня Интернет является всемирным соединением глобальных и локальных сетей, содержащих миллионы машин.
Интернет можно рассматривать как набор доменов (domen), каждый из которых состоит из сети или небольшой интерсети, управляемой одной организацией, такой как университет, производственная компания или правительственный институт. Каждый домен является автономной системой, которую можно изменять согласно собственным потребностям. Для того, чтобы создать домен, организация должна зарегистрироваться в некоммерческой организации по назначению адресов и имен в Интернете.
Отдельные пользователи, которые хотят получить доступ к Интернету, также могут создать и зарегистрировать свой домен. Однако более распространена схема, когда пользователь получает доступ к Интернету через домен, основанный организацией, сотрудником которой он является. Или же пользователь оплачивает соединение с доменом, установленным поставщиком услуг Интернета. При этом соединение пользователя с поставщиком услуг осуществляется по телефонной линии.