Алгоритмы

     Ранее часто писали «алгорифм», сейчас такое написание используется редко, но, тем не менее, имеет место (например, Нормальный алгорифм Маркова).

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

     Единого «истинного» определения понятия «алгоритм» нет.

     «Алгоритм — это конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность». (Д. Э. Кнут)

     «Алгоритм — это всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи». (А. Колмогоров)

     «Алгоритм — это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату». (А. Марков)

     «Алгоритм — точное предписание о выполнении в определённом порядке некоторой системы операций, ведущих к решению всех задач данного типа». (Философский словарь / Под ред. М. М. Розенталя)

     «Алгоритм — строго детерминированная последовательность действий, описывающая процесс преобразования объекта из начального состояния в конечное, записанная с помощью понятных исполнителю команд». (Николай Дмитриевич Угринович, учебник «Информатика и информ. технологии»)

     «Алгоритм — это последовательность действий, направленных на получение определённого результата за конечное число шагов».

     «Алгоритм — однозначно, доступно и кратко (условные понятия — названия этапа) описанная последовательность процедур для воспроизводства процесса с обусловленным задачей алгоритма результатом при заданных начальных условиях. Универсальность (или специализация) алгоритма определяется применимостью и надёжностью данного алгоритма для решения нестандартных задач».

     «Алгоритм — это понятные и точные предписания исполнителю совершить конечное число шагов, направленных на решение поставленной задачи».

     «Алгоритм — это некоторый конечный набор рассчитанных на определённого исполнителя операций в результате выполнения которых через определённое число шагов может быть достигнута поставленная цель или решена задача определённого типа».

     «Алгоритм — это последовательность действий, либо приводящая к решению задачи, либо поясняющая почему это решение получить нельзя».

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

     «Алгоритм — это точное предписание, которое задаёт вычислительный (алгоритмический) процесс, начинающийся с произвольного исходного данного и направленный на получение полностью определяемым этим исходным данным результата».

     «Алгоритм — это описание последовательности действий, которое ведёт к конечному результату».

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

• Дискретность — алгоритм должен представлять процесс решения задачи как последовательное выполнение некоторых простых шагов. При этом для выполнения каждого шага алгоритма требуется конечный отрезок времени, то есть преобразование исходных данных в результат осуществляется во времени дискретно.
• Детерминированность — определённость. В каждый момент времени следующий шаг работы однозначно определяется состоянием системы. Таким образом, алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных. В современной трактовке у разных реализаций одного и того же алгоритма должен быть изоморфный граф. С другой стороны, существуют вероятностные алгоритмы, в которых следующий шаг работы зависит от текущего состояния системы и генерируемого случайного числа. Однако при включении метода генерации случайных чисел в список «исходных данных», вероятностный алгоритм становится подвидом обычного.
• Понятность — алгоритм для исполнителя должен включать только те команды, которые ему (исполнителю) доступны, которые входят в его систему команд.
• Завершаемость (конечность) — при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов. С другой стороны, вероятностный алгоритм может и никогда не выдать результат, но вероятность этого равна 0.
• Массовость — универсальность. Алгоритм должен быть применим к разным наборам исходных данных.
• Результативность — завершение алгоритма определёнными результатами.
• Алгоритм содержит ошибки, если приводит к получению неправильных результатов либо не даёт результатов вовсе.
• Алгоритм не содержит ошибок, если он даёт правильные результаты для любых допустимых исходных данных

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

• на естественном языке;
• в виде блок-схемы;
• в виде R-схемы.
• Линейный алгоритм - это такой, в котором все операции выполняются последовательно одна за другой (рис. 2).

Вопрос 6. Алгоритмы: понятие  и свойства. Алгоритмы ветвления.

 

Ответ:

    Алгоритмы: понятие и свойства – ответ  тот же, что и в вопросе 4, т.к. они повторяются.

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

    Алгоритмы разветвленной структуры применяются, когда в зависимости от некоторого условия необходимо выполнить либо одно, либо другое действие. В блок-схемах разветвленные алгоритмы изображаются так, как показано на рис. 3 - 4.

 

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

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

Вопрос 8. Локальные и  глобальные вычислительные сети.

 

Ответ:

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

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

     Все многообразие компьютерных сетей можно  классифицировать по группе признаков:

• Территориальная распространенность;
• Ведомственная принадлежность;
• Скорость передачи информации;
• Тип среды передачи;

     По  территориальной распространенности сети могут быть локальными, глобальными, и региональными. 

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

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

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

     Локальные компьютерные сети.

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

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

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

     Каждый  компьютер, подключенный к локальной  сети, должен иметь специальную плату (сетевой адаптер). Между собой  компьютеры (сетевые адаптеры) соединяются  с помощью кабелей.

     Топология сети.

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

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

Рисунок 5 – Шинная топология

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

     В этом смысле «звезда» более устойчива. Поврежденный кабель – проблема для  одного конкретного компьютера, на работе сети в целом это не сказывается. Не требуется усилий по локализации неисправности. 
 
Рисунок 6 – Топология типа «звезда»

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

     Рисунок 7 – топология типа «кольцо»

     Региональные  компьютерные сети. 

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

     Корпоративные компьютерные сети.