УЧРЕЖДЕНИЕ ОБРАЗОВАНИЯ  ФЕДЕРАЦИИ ПРОФСОЮЗОВ РЕСПУБЛИКИ БЕЛАРУСЬ

МЕЖДУНАРОДНЫЙ ИНСТИТУТ ТРУДОВЫХ И СОЦИАЛЬНЫХ ОТНОШЕНИЙ 

Кафедра логистики 
 
 
 
 
 
 
 

Самостоятельная управляемая работа студента

по курсу  «Алгоритм. Понятие алгоритма. Типы алгоритмических процессов» 

Вариант №28 
 
 
 
 
 
 
 
 
 
 
 
 
 

Выполнила студентка

Степура А.А.

Ф-т  МЭО и М, 1-й курс

Группа 1015 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Минск 2010 

     АЛГОРИТМ. ПОНЯТИЕ АЛГОРИТМА. ТИПЫ АЛГОРИТМИЧЕСКИХ ПРОЦЕССОВ. 

     ОГЛАВЛЕНИЕ

     ВВЕДЕНИЕ 2

     АЛГОРИТМ. ПОНЯТИЕ АЛГОРИТМА. 4

     ТИПЫ  АЛГОРИТМИЧЕСКИХ  ПРОЦЕССОВ. 5

     ЗАКЛЮЧЕНИЕ 9

     ЛИТЕРАТУРА 10

 

     ВВЕДЕНИЕ

     Слово алгоритм содержит в своем составе  преобразованное географическое название Хорезм. Термин "алгоритм" обязан своим происхождением великому ученому  средневекового Востока - Мухаммеду  ибн Мусе ал-Хорезми. Он жил приблизительно с 783-го по 850 г.В латинских переводах с арабского арифметического трактата ал-Хорезми его имя транскрибировалось как «algorismi». Откуда и пошло слово "алгоритм" - сначала для обозначения алгоритмов цифровых вычислений десятичной позиционной арифметики, а затем для обозначения 'произвольных процессов,' в которых искомые величины последовательно определяются из исходных данных по определенным правилам -инструкциям. Вплоть до 30-х годов нашего столетия понятие алгоритма оставалось интуитивным, имевшим скорее методологическое, чем математическое значение. К началу ХХ в. много ярких примеров алгоритмов дали алгебра и теория чисел. Среди них упомянем алгоритм Евклида нахождения наибольшего общего делителя двух натуральных чисел или двух целочисленных многочленов, алгоритм Гаусса решения системы линейных уравнений, алгоритм нахождения рациональных корней многочленов одного переменного с рациональными коэффициентами, алгоритм  Штурма определения числа действительных корней многочлена с действительными коэффициентами на некотором отрезке действительных чисел, алгоритм разложения многочлена от одного переменного на неприводимые множители. Эти алгоритмические проблемы решены указанием конкретных результатов такого типа достаточно интуитивного понятия алгоритма. Решение таких проблем потребовало привлечения новых логических средств. Ведь одно дело - доказать существование разрешающего алгоритма: это можно сделать, используя интуитивное понятие алгоритма. Другое дело - доказать несуществование алгоритма: для этого нужно знать точно, что такое алгоритм.

 

АЛГОРИТМ. ПОНЯТИЕ АЛГОРИТМА.

     Алгоpитм — заранее заданное понятное и точное пpедписание возможному исполнителю совеpшить определенную последовательность действий для получения решения задачи за конечное число шагов. Это — не определение в математическом смысле слова, а, скорее, описание интуитивного понятия алгоритма, раскрывающее его сущность. Понятие алгоритма является не только одним из главных понятий математики, но одним из главных понятий современной науки. Более того, с наступлением эры информатики алгоритмы становятся одним из важнейших факторов цивилизации.Исполнитель алгоритма — это некоторая абстрактная или реальная (техническая, биологическая или биотехническая) система, способная выполнить действия, предписываемые алгоритмом. Сpеда (или обстановка) — это "место обитания" исполнителя.

     Исполнителя хаpактеpизуют:

• среда;
• элементаpные действия;
• cистема команд;
• отказы.

     Каждый  исполнитель может выполнять  команды только из некотоpого стpого заданного списка — системы команд исполнителя. Для каждой команды должны быть заданы условия пpименимости и описаны pезультаты выполнения команды. После вызова команды исполнитель совеpшает соответствующее элементаpное действие. Отказы исполнителя возникают, если команда вызывается пpи недопустимом для нее состоянии сpеды. Обычно исполнитель ничего не знает о цели алгоpитма. Он выполняет все полученные команды, не задавая вопросов "почему" и "зачем". В информатике универсальным исполнителем алгоритмов является компьютер.

 

     Основные  свойства алгоритмов следующие:

1. Понятность для исполнителя — исполнитель алгоритма должен понимать, как его выполнять:имея алгоритм и произвольный вариант исходных данных, исполнитель должен знать, как надо действовать для выполнения этого алгоритма. 2.   Дискpетность — алгоpитм должен пpедставлять пpоцесс pешения задачи как последовательное выполнение пpостых шагов . 3.   Опpеделенность — каждое пpавило алгоpитма должно быть четким, однозначным и не оставлять места для пpоизвола. 4.Pезультативность . 5.Массовость .

        рис.1 . Алгоритм посадки живой изгороди.

 

ТИПЫ  АЛГОРИТМИЧЕСКИХ  ПРОЦЕССОВ.

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

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

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

     

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

     

     Существуют  две схемы циклических вычислительных процессов.

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

 

Примеры структуры ветвления

 

       

     рис.2. Блок-схема алгоритма.

ЗАКЛЮЧЕНИЕ

 

        Теория алгоритмов оказала существенное влияние на развитие ЭВМ и практику программирования. В теории алгоритмов были предугаданы основные концепции, заложенные в аппаратуру и языки программирования ЭВМ. Упоминаемые выше главные алгоритмические модели математически эквивалентны; но на практике они существенно различаются сложностными эффектами, возникающими при реализации алгоритмов, и породили разные направления в программировании. Так, микропрограммирование строится на идеях машин Тьюринга, структурное программирование заимствовало свои конструкции из теории рекурсивных функций, языки символьной обработки информации (РЕФАЛ, ПРОЛОГ) берут начало от нормальных алгоритмов Маркова и систем Поста. 

 

Литература¹

  Вычислительная  техника и программирование. Под  ред. А.В.Ретрова. - М.:Высшая школа, 1990 [1]

  Кузнецов  А.А. и др. Основы информатики. - М.: Дрофа, 1998 [2]

  Кушниренко  А.Г. и др. Информатика. - М.: Дрофа, 1998 [3]

  Успенский В.А., Семенов А.А. Теория алгоритмов: основные открытия и приложения. М., 1987. [4]

  Шауцукова Л.З. Информатика 10 - 11. М.: Просвещение, 2007 [5]