Моделирование и формализация
Алгоритм и его свойства
Способы записи алгоритмов
Линейные алгоритмы (следование)
Ветвления в алгоритмах
Циклическая форма организации действий
Замкнутые и разомкнутые системы управления
Языки программирования
Вопросы и упражнения
Алгоритм и его свойства
Слово «алгоритм» происходит от латинской формы написания имени арабского математика Аль Хорезми. Известно, что он родился до 800 г., а умер после 847 г., жил и работал в Багдаде - крупном научном центре и влиятельной столице Древнего Востока. Аль Хорезми использовал индийскую позиционную систему счисления с нулём и сформировал правила четырёх арифметических действий над многозначными числами. Первоначально под алгоритмами понимали только эти правила, но в дальнейшем понятие алгоритма стали использовать более широко.
Разработать алгоритм – это разбить задачу на последовательно выполняемые шаги (этапы).
Примеры алгоритмов:
С помощью алгоритмов решаются не только традиционные для математики вычислительные задачи, но и многие другие, возникающие в быту или на производстве. И было бы ошибкой думать, что алгоритмы могут вам пригодиться только в том случае, если вы станете программистами. Умение конструировать алгоритмы и чётко их формулировать - очень важный навык современного человека. Рассмотрим несколько алгоритмов, с которыми можно встретиться в жизни.
Алгоритм пользования автоматической междугородной телефонной связью:
1.Наберите цифру 8 и дождитесь непрерывного гудка.
2.Наберите код вызываемого города.
3.Наберите номер телефона вызываемого абонента.
Дети очень любят играть и иногда в своих играх используют игровые алгоритмы.
Пример игрового алгоритма:
1.Загадай число.
2.Умножь на 5.
3.Прибавь 8.
4.Умножь на 2.
5.Отними 16.
6.Отбрось крайнюю правую цифру и получишь загаданное число.
Вспомните, как вы переходите через проезжую часть. Вы с малых лет помните правила перехода через улицу, а ведь их можно тоже назвать алгоритмом. Вся повседневная жизнь человека - это деятельность по алгоритмам.
Попробуем сравнить все рассмотренные примеры. На первый взгляд, в них нет ничего общего: один алгоритм поможет позвонить за пределы города, другой - решить квадратное уравнение, третий - отгадать задуманное число, а четвёртый - перейти улицу. Но более глубокий анализ покажет наличие последовательности действий в каждом алгоритме. Причём, каждое действие записано в виде одного или нескольких предложений, называемых предписаниями. Требуется точно исполнять все предписания, чтобы от исходных данных перейти к заранее определённому результату.
Следовательно, алгоритм - это строго организованная последовательность действий (предписаний), приводящая от исходных данных к конкретному результату.
Попробуем переставить местами шаги в любом из предложенных алгоритмов:
1. Загадай число.
2. Прибавь 8.
3. Умножь на 5.
4. Отними 16.
5. Умножь на 2.
6.Отбрось крайнюю правую цифру и получишь загаданное число.
Исполнив этот алгоритм, вы не получите требуемого результата.
Результативность - это одно из свойств алгоритма, позволяющее решить задачу за конечное число шагов. В противном случае считается, что алгоритм неприменим для решения данной задачи.
Разделение выполнения решения задачи на отдельные операции - важное свойство алгоритмов, называемое дискретностью. Нельзя перейти к следующему действию, не закончив предыдущего. Снова рассмотрим один из примеров - алгоритм нахождения корней квадратного уравнения: не закончив вычислять дискриминант, вы врядли решите квадратное уравнение.
Итак, исходя из этих основных свойств алгоритма, приходим к выводу:
1.Алгоритм состоит из точных предписаний.
2.Нельзя менять порядок выполнения предписаний.
3.Нельзя переходить к следующему действию, не закончив предыдущего.
Рассмотрим ещё один пример алгоритма:
1. Подойти к реке.
2. Войти в реку.
3. Идти по дну, пока не выйдешь на другой берег.
Выполним ли этот алгоритм, если человек подошёл к реке Волге? Ответ однозначен - нет. А в каком случае этот алгоритм будет выполнен, и кто может пройти по дну реки Волги? Оказывается, алгоритм выполнится, если по дну пойдёт человек со специальным снаряжением или робот-“подводник”. Он также будет исполнен, если человек без снаряжения подойдёт не к Волге, а к маленькой речке, глубина которой не выше шеи человека.
Следовательно, один и тот же алгоритм может быть верным и неверным в зависимости от того, каковы исходные данные и кто исполнитель алгоритма.
Исполнитель - это человек или автомат (в частности им может быть процессор ЭВМ), умеющий выполнять некоторый набор действий которые можно назвать командами.
Исполнитель может исполнять команды из набора и ничего более. Набор команд называют допустимыми действиями исполнителя. Но управлять надо исполнителем правильно и точно.
Рассмотрим пример: имеется исполнитель “Перевозчик”. Набор его допустимых действий следующий:
1. Перевези волка.
2. Перевези козу.
3. Перевези капусту.
4. Переправься обратно один.
Перед нами “гипотетический” человек, который, строго руководствуясь алгоритмом, решает задачу. Про такого человека можно сказать, что он решает поставленную задачу машинально, без эмоций, без мыслей. Его и в самом деле можно заменить машиной, выполняющей те же допустимые действия. Всё, что умеет делать такой человек - это исполнять только четыре команды. Составим для данного исполнителя алгоритм решения следующей задачи: перевозчик находится на левом берегу реки с волком, козой и капустой. Требуется переправить их на правый берег, но лодка слишком мала: перевозчик может взять с собой только одного пассажира - либо волка, либо козу, либо капусту. Но если он оставит на берегу волка с козой, то “от козы останутся лишь рожки да ножки”, если он оставит козу с капустой, то коза съест капусту. Только в присутствии перевозчика они не безобразничают.
Алгоритм “Перевозчик”
Исходные данные: волк, коза, капуста, лодка, перевозчик на левом берегу.
Результат: волк, коза, капуста, лодка, перевозчик на правом берегу.
Исполнитель: перевозчик.
Последовательность действий:
1. Перевези козу.
2. Переправься обратно один.
3. Перевези волка.
4. Перевези козу.
5. Перевези капусту.
6. Переправься обратно один.
7. Перевези козу.
Исполнителем указанных действий является человек - перевозчик, решающий задачу по алгоритму машинально. Исполнителем может быть и какое-то устройство, в этом случае выражение “машинальное действие”, употребляемое обычно в переносном смысле, при современном уровне развития науки и техники приобретает прямой смысл.
Представим себе небольшое устройство, похожее на электронную игру. На экране изображены волк, коза, капуста и перевозчик с лодкой. Рядом с экраном находятся четыре кнопки. Над первой кнопкой надпись “Перевези козу” над второй - “Перевези волка”, над третьей - “Перевези капусту”, над четвёртой - “Переправься обратно один”. Нажимая на кнопки, мы можем передвигать существа по экрану. Других способов управления ими в данном устройстве нет. Последовательность действий для решения задачи будет состоять из нажатий на кнопки в указанном порядке: 1, 4, 2, 1, 3, 4, 1.
Итак, упрощённо исполнителя можно представить как устройство, состоящее из двух частей: устройства управления и набора инструментов. Команды алгоритма выполняются устройством управления с помощью набора инструментов одна за другой.
Совокупность команд, которые могут быть выполнены исполнителем, называется системой команд исполнителя.
Сумеет исполнитель решить предложенную задачу или нет, зависит от среды, в которой он действует, и от правильности системы команд, данных ему.
Знакомство с исполнителем РОБОТ:
Исполнитель не может одиннадцать раз шагнуть вправо, т.к. на 10 шаге клетчатое поле (среда, в которой он действует) закончится. А команду “Шагнуть вправо” он просто не поймёт, т.к. понимает только команду “вправо”. Используемые на практике записи алгоритмов составляются с ориентацией на определённого исполнителя. Чтобы составить для него алгоритм, нужно знать, какие предписания этот исполнитель может понять и исполнить, а какие не может. Следовательно, составляя алгоритм для определённого исполнителя, можно использовать лишь те команды, запись которых имеется в его системе команд, т.е. отдаваться они должны так, как заранее было предусмотрено. Это свойство алгоритмов будем называть понятностью.
Рассмотрим и другие свойства алгоритма: детерминированность и массовость. Детерминированность (определённость) означает, что правила, образующие алгоритм, должны быть строго определенными, однозначными и непротиворечивыми. Этим обеспечивается его независимость от исполнителя, будь то человек, устройство или компьютер. Массовость - это свойство алгоритма обеспечивать решение не одной конкретной задачи, а целого множества задач данного типа.
|
|
