Учебник_Информатика. Стандарт третьего поколениян. В. Макарова, В. Б. Волков
 Скачать 14.49 Mb.
|
|
Номер Наименование Описание 7 Прикладной Взаимодействие с прикладными программами пользователя 6 Представления Шифрование, дешифрование, кодирование, перекодирование 5 Сеансовый Координация связи между двумя рабочими станциями в сети 4 Транспортный Разбиение на пакеты и сборка пакетов в сообщения 3 Сетевой Адресация и маршрутизация пересылаемых пакетов 2 Канальный Формирование пакетов, требуемых для соответствующих сетей 1 Физический Физические, механические и электрические характеристики линий связи 13.7. Феномены века коммуникаций 13.7.1. Военно-техническая область Развитие сетей, было инициировано министерством обороны США и мотивиро ванно в основном военными потребностями. Не удивительно, что именно военные в первую очередь используют современные преимущества, которые дает им сеть: □ получение информации всегда, везде и отовсюду; □ управление войсками всегда, везде и отовсюду; 13.7. Феномены века коммуникаций 383 □ высоконадежная оценка угроз; □ военное прогнозирование и моделирование. Что же касается возможных отрицательных явлений тотального внедрения компьютеров и компьютерных сетей в военную область, то пока их можно увидеть только в фантастических фильмах: суперкомпьютеры начинают мировую войну, суперкомпьютеры правят миром. Цена ошибки или сбоя в компьютерных сетях при передачи военных данных может быть весьма велика. 13.7.2. Финансовая сфера Если поначалу в финансовой сфере компьютерные сети казались великим бла гом, то сегодня это благо надо рассматривать как минимум с большими оговорка ми. Виртуальные рынки, виртуальные биржи, виртуальные деньги, виртуальные товары и услуги — все это стало доступно в любой точке планеты благодаря опо ясывающим планету компьютерным сетям. Но благодаря им же стали возможны и виртуальные аферы, и виртуально организованные финансовые потрясения. 13.7.3. Бизнес В отличие от финансово-экономической области, которая занимается произ водством, регулированием и сбытом денег, сфера бизнеса, производящая реальные товары и услуги, от развития компьютерных сетей только выиграла. Сетевой бизнес развивался так интенсивно, что для его обозначения даже было придумано специальное название — электронная коммерция (e-commerce). Специ альные названия придуманы были даже для сетевых технологий, обеспечивающих электронную коммерцию на том или ином уровне взаимодействия. Английские аббревиатуры этих названий содержат символ двойки, который произносится на английском созвучно предлогу «to», в данном контексте обозначающему дательный падеж (табл. 13.3). Таблица 13.3. Технологии электронной коммерции Аббревиатура Название Примеры В2С Бизнес клиенту (Business-tQ-Client) Покупка в виртуальных магазинах В2В Бизнес бизнесу (Business-to-Business) Фирма, занятая сборкой компьютеров, заказывает комплектующие у фирмы-производителя G2B Государство бизнесу (Government-to-Business) Распространение через сеть нормативных и законода тельных актов, регулирующих работу бизнеса С2 С Клиент клиенту (Client-to-Client) Клиенты обмениваются мнениями о качестве и цене купленного товара. Форумы по продаже вещей, на ходившихся в употреблении P2P Одноранговые сети (Peer-to-Peer) Совместное использование файлов 384 Глава 13. Основы построения компьютерных сетей 13.7.4. География и навигация В области географии и навигации сетевые технологии привнесли в нашу жизнь следующие достижения: □ мгновенное получение спутниковых карт поверхности земли в любой точке, причем если для гражданских нужд степень детализации такая, что позволяет рассмотреть машины на стоянке, то военные карты дают возможность видеть номера этих машин и знаки различия на форме; □ современные навигационные системы, позволяющие прокладывать маршрут практически в любой местности. 13.7.5. Наука Положительными факторами в развитии науки стали следующие возможности: □ мгновенный обмен информацией о результатах проведенных исследований; □ присутствие на виртуальных научных конференциях; □ мгновенная публикация результатов исследований; □ виртуальное участие в научных экспериментах. Однако кроме огромных преимуществ сеть принесла в науку и отрицательные явления, к которым можно отнести появление большого количества квазинаучной информации, не просто доступной, но более доступной для широкой публики, чем истинно научная информация. 13.7.6. Знание С появлением глобальных сетей человечество стало генерировать массивы данных, продуцировать самые разнообразные типы информации, которые нужно было каким-то образом критически осмысливать, упорядочивать, превращая в действенное и полезное знание. Наиболее ярким и впечатляющим примером такого технологического решения является Википедия (см. русский вариант по адресу http://ru.wikipedia.org/), через 5 лет после создания обошедшая по посещаемости общепризнанную, наиболее старую и универсальную энциклопедию, Британнику (http://www.britannica.com/). Таким образом, порождая хаос данных, сеть одновремен но породила и инструмент для преодоления этого хаоса, инструмент эффективной и всесторонней добычи и упорядочивания знаний. Сама технология wiki сейчас широко используется для создания баз знаний самыми различными сетевыми со обществами. 13.7.7. Образование Сетевые технологии в области образования также выступили в крайне неодно значной роли. С одной стороны, они принесли несколько безусловно положитель ных моментов: □ образование стало более доступным благодаря различного рода дистанционным курсам и образовательным программам; 13.7. Феномены века коммуникаций 385 □ работа преподавателя стала более эффективной, поскольку видеть на экране процесс выполнения задания любым учащимся куда продуктивнее, чем под ходить к каждому компьютеру; □ учащиеся получили доступ к альтернативным источникам знания, и препода ватель перестал быть единственным поставщиком знания (теперь при наличии терпения и желания на любую тему в Интернете можно найти самую исчерпы вающую и актуальную информацию). С другой стороны, нельзя не отметить и отрицательные моменты, в частности, теперь учащиеся все реже задания выполняют самостоятельно, предпочитая искать готовые решения в Интернете. 13.7.8. Технологии Само развитие сетевых технологий было основано на энтузиазме групп научных сотрудников и открытости. Первые сетевые операционные системы были откры тыми, причем открытым было все: исходные коды, спецификации протоколов, ре зультаты испытаний и направления исследований. Участники разработок свободно обменивались друг с другом любыми сведениями, и это привело к показательному результату: почти все, что было разработано на заре возникновения сетевых техно логий, используется по сей день. С определенного момента возникшая на основе свободных принципов, развив шаяся и полноценно функционирующая сеть привела к созданию новых техноло гий, которые мы сегодня знаем под общим названием СПО (свободное программ ное обеспечение). Без глобальных сетей даже представить себе невозможно, как группа энтузиастов из самых разных точек земного шара смогла бы организоваться и создать полноценную сетевую операционную систему, конкурирующую сегодня на равных с продуктами самых мощных производителей программного обеспече ния. Речь идет о GNU/Linux. СПО ценно не только само по себе, оно будит творческую мысль у людей в са мых разных отраслях науки и техники, подвигая их на создание открытых аналогов не только программного обеспечения, но и техники. 13.7.9. Общество Влияние, которое оказывает сеть на социум, тоже двойственно. Благодаря се тевым технологиям все больше людей реализует свое право на информацию, в том числе на информацию о действиях власти. Практически все, что власть в любой стране хотела бы сделать тайно, благодаря Интернету сегодня становится явным. Таким образом, Интернет более полноценно, чем обычные средства массовой информации, реализует концепции свободы слова и свободы средств массовой информации. Кроме того, во многих странах давно уже разработаны и внедрены так называемые сетевые правительства, приемные, администрации и прочие сете вые представительства органов власти. Большое количество операций, на которые раньше тратились дни и часы, человек сегодня легко может выполнить, не выходя из дома: заказать справку, а если нужна личная встреча, то записаться на прием 386 Глава 13. Основы построения компьютерных сетей к чиновнику в указанное время. Можно проводить через сеть коммунальные пла тежи или получать информацию о порядке оформления тех или иных документов. Кроме этих «государственных» и «официальных» функций, Интернет оказался благоприятной средой для создания различных сообществ. Сегодня просто невоз можно представить себе жизнь без этого слоя социальной активности: интернет-ча ты, интернет-конференции, блоги, сетевые фан-клубы и, конечно же, драгоценный интернет-пейджер ICQ. Про популярность социальных сетей, таких как «Одно классники» или «В контакте» знает любой пользователь Интернет. Но есть и другая чаша весов. Именно сеть сделала простым и возможным то, что без нее было бы труднодоступно и трудновыполнимо. Призывы к насилию, разжигание расовой, национальной и религиозной розни, публикация фотографий и видеоматериалов, содержащих реальные сцены насилия и жестокости, порногра фия, пошлость, глупость и грубость — все это в избытке выплеснулось на страницы Интернета. Что делать с этими общественными проявлениями? Являются ли они отражением состояния общества, или просто чувство бесконтрольности и аноним ности, которое дает сеть, обостряет в человеке не только хорошее, но и плохое? Так или иначе, обществу еще предстоит оценить данные феномены и выработать необходимый в этом случае иммунитет. 13.7.10. Здоровье и экология Влияние сетевых технологий на экологию и здоровье человека пока мало из учено. Да, мы знаем, что сетевые технологии принесли безусловную пользу в сфере медицины: информация о новых лекарствах и способах лечения, виртуальные консультации у специалистов, оперативная информация о новых видах заболе ваний и методах защиты от них составляют большую ценность и, безусловно, способствуют охране здоровья и развитию медицины. Сегодня уже не редкость проведение операций, курируемых консилиумом врачей, наблюдающих за ходом операции удаленно, на экранах компьютеров, и это тоже феномен, который без сетевых коммуникаций был бы попросту невозможен. Однако все сетевые коммуникации — это мощнейший источник электромагнит ных излучений, оказывающих определенное влияние на организм человека (осо бенно в миллиметровом спектре, на частотах работы технологий Wi-Fi, Bluetooth и мобильных телефонов). То, что такое влияние существует, никаких сомнений нет. Также нет и однозначных результатов научных исследований на этот счет. Еще одним феноменом, напрямую связанным со здоровьем, является доступ ность в сети разного рода медицинских сведений и вызванная этой доступностью иллюзия медицинской осведомленности. Эти иллюзии наличия готовых рецептов от всего несут безусловную опасность для здоровья, поскольку человек, вместо того чтобы обратиться к врачу, начинает лечить себя сам. Вопросы для самопроверки 387 Вопросы для самопроверки 1. Почему сеть на базе мэйнфрема нельзя в полной мере считать компьютерной? 2. Какая идея Бэрэна до сих пор лежит в основе сетевого взаимодействия ком пьютеров? 3. По каким признакам можно классифицировать компьютерные сети? 4. Что такое «широковещание»? 5. Чем отличается сеть с коммутацией каналов от сети с коммутацией пакетов? 6. Перечислите известные вам виды проводных соединений. 7. Верно ли выражение «глобальная компьютерная сеть Интернет»? 8. Что такое «одноранговая сеть»? 9. Что такое «топология сети»? 10. Чем звездообразная топология отличается от кольцевой? 11. На каком основании выбирается топология компьютерной сети? 12. Что такое «витая пара»? 13. Сравните между собой кабели типа «витая пара» и «тонкий коаксиал». В чем преимущества и недостатки того и другого решения? 14. Почему оптоволоконный кабель не получил повсеместного распространения, несмотря на свои достоинства? 15. Каково назначение сетевых адаптеров? 16. Что такое «хаб» и для чего он используется? 17. Что такое «сетевой протокол» и зачем он нужен? 18. В чем разница между сетевой моделью и стеком протоколов? 19. Перечислите известные вам протоколы транспортного уровня стека ТСР\1Р. 20. За что отвечают протоколы прикладного уровня? 21. Перечислите уровни сетевой модели OSI. Литература 1. Олифер В. Г., Олифер Я. А. Компьютерные сети. СПб.: Питер, 2006. 2. Паркер Т., Сиян К. T C P /IP для профессионалов. СПб.: Питер, 2004. 3. Таненбаум Э. Компьютерные сети. СПб.: Питер, 2003. Часть третья Алгоритмическое и программное обеспечение информатики Глава 14. Основы теории алгоритмов.......................................................... 391 Глава 15. Классификация и тенденции развития программного обеспече ния ............................................................................................................ 432 Глава 16. Системное программное обеспечение компьютера.................. 465 Глава 17. Офисное программное обеспечение...........................................502 Глава 18. Средства мультимедиа ................................................................524 Глава 19. Технологии и инструменты программирования.......................... 552 Глава 14 Основы теории алгоритмов 14.1. Представление об алгоритмах 14.2. Способы записи алгоритмов 14.3. Базовые алгоритмические конструкции 14.4. Алгоритмы обработки данных разного типа 14.5. Алгоритмы сортировки и поиска В основе работы любого механизма или устройства, будь то двигатель вну треннего сгорания, сложная компьютерная система или биологический механизм организма человека, лежит определенная и преследующая некоторую цель после довательность действий. Такая последовательность действий получила название «алгоритм». Настоящая глава посвящена описанию того, каким образом можно со ставить и представить на компьютере те или иные алгоритмы, какие задачи можно решать при помощи алгоритмов определенного типа. 14.1. Представление об алгоритмах 14.1.1. Понятие алгоритма Во всех сферах своей деятельности, в частности в сфере обработки информа ции, человек сталкивается с различными способами или методиками решения разнообразных задач. Они определяют порядок выполнения действий для полу чения желаемого результата — мы можем трактовать это как первоначальное или интуитивное определение алгоритма. 392 Глава 14. Основы теории алгоритмов Термин алгоритм происходит от имени средневекового узбекского математика Аль-Хорезми, который еще в 825 году описал правила выполнения четырех ариф метических действий в десятичной системе счисления. Процесс их выполнения и был назван алгоризмом. Впоследствии вместо слова алгоризм стали употреблять латинизированное слово алгорисмусу смысл которого состоял в комбинировании четырех операций арифметического исчисления: сложения, вычитания, умножения и деления. Затем алгоритмус преобразовался в алгорифм. Смысл этого понятия чаще всего связы вался с алгорифмами Евклида — описаниями процессов нахождения наибольшего общего делителя двух натуральных числе, наибольшей общей меры двух отрезков и т. п. Под алгоритмом же понимали конечную последовательность точно сформу лированных правил, которые позволяют решать различные классы задач. Такое определение алгоритма не является строго математическим, так как в нем не со держится точной характеристики того, что следует понимать под классами задач и под правилами их решения. Таким образом, можно нестрого определить алгоритм как однозначно трактуемую процедуру решения задачи. Дополнительные требования о выполнении алгоритма за конечное время для любых входных данных приводят к еще одному неформальному определению алгоритма. Пусть D Z — область (множество) исходных данных задачи Z, a R — множество возможных результатов, тогда мы можем говорить, что алгоритм осуществляет отображение DZ -> R. Поскольку такое отображение может быть не полным, в теории алгоритмов вво дятся понятия частичного и полного алгоритма. Алгоритм называется частичным, если мы получаем результат только для некоторых значений б /, принадлежащих DZ, и полным, если алгоритм получает правильный результат для всех значений d, принадлежащих DZ. Сегодня отсутствует одно исчерпывающе строгое определение понятия «алго ритм». Из разнообразных вариантов словесного определения наиболее удачные, видимо, принадлежат российским ученым А. Н. Колмогорову и А. А. Маркову. 14.1. Представление об алгоритмах 393 Алгоритмы можно подразделить на два класса: численные и логические. Численные алгоритмы — это алгоритмы, в соответствии с которыми решение задач сводится к арифметическим действиям. Логические алгоритмы — это алгоритмы, в соответствии с которыми решение задач сводится к логическим действиям. Несмотря на различие в определениях, к алгоритмам предъявляется ряд общих требований. Итак, алгоритм должен: □ содержать конечное количество элементарно выполнимых предписаний, то есть удовлетворять требованию конечности записи; □ выполнять конечное количество шагов при решении задачи, то есть удовлетво рять требованию конечности действий; □ быть единым для всех допустимых исходных данных, то есть удовлетворять требованию универсальности; □ приводить к правильному по отношению к поставленной задаче решению, то есть удовлетворять требованию правильности. Формально строгие определения понятия алгоритма связаны с введением спе циальных математических конструкций — формальных алгоритмических систем или моделей вычислений, каковыми являются рассматриваемые далее машины Поста и Тьюринга. 14.1.2. Формализация понятия алгоритма посредством машины Поста Пост рассматривает общую проблему, состоящую из множества конкретных проблем, при этом решением общей проблемы является такое решение, которое определяет ответ для конкретной проблемы. Например, нахождение решения уравнения З х х + 9 = 0 — это конкретная проблема, так как в уравнении используются константы, а нахождение решения уравнения а * х + b = 0 — это общая проблема, так как коэффициенты уравнения \ являются переменными величинами. Алгоритм должен быть универсальным, то есть должен находить решения поставленной задачи в общем виде. Отметим, что сам термин «алгоритм» не используется Э. Постом, его заменяет понятие на бора инструкций. Машина Поста представляет собой абстрактный механизм для выполнения алгоритмов. Этот механизм состоит из двух узлов (рис. 14.1): □ бесконечной ленты, разделенной на ячейки, каждая из которых может быть по мечена или не помечена меткой V; □ механизма чтения-записи (в дальнейшем — каретка), который может переме щаться вдоль ленты вправо и влево, записывать метку в пустую ячейку, стирать метку в помеченной ячейке и проверять наличие метки в ячейке. 394 Глава 14. Основы теории алгоритмов Механизм чтения-записи V V V V Лента Рис. 14.1. Машина Поста Конкретная проблема задается «внешней силой» (термин Поста) пометкой ко нечного количества ячеек, при этом очевидно, что любая конфигурация начинается^ и заканчивается помеченной ячейкой. После применения к конкретной проблеме некоторого набора инструкций, решение также представляется в виде набора по меченных и непомеченных ячеек, распознаваемого той же внешней силой. Пост в 1936 г. предложил набор инструкций, или элементарно выполнимых операций, которые выполняет «работник». В терминах современного состояния компьютерной области этот набор инструкций можно трактовать как минималь ный набор битовых операций элементарного процессора. В табл. 14.1 приведены инструкции машины Поста. Латинскими буквами i J J { j 2, и т. д. обозначены номера инструкций; М — пометить ячейку, С — стереть метку. Таблица 14.1. Инструкции машины Поста № |