Алгоритмы и их свойства

МИНОБРНАУКИ РОССИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ  ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«КОМИ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ ИНСТИТУТ»

(Коми пединститут)

Факультет Педагогики и психологии

Специальность

«Начальное и дошкольное образование»

Кафедра Начального и дошкольного  образования

(очное отделение)

РЕФЕРАТ

АЛГОРИТМЫ И ИХ СВОЙСТВА

Научный руководитель:

ст. преподаватель 

                                                                        Мищенкова Нина Петровна

Исполнитель:

студентка 6125 группы

Новинская Мария Сергеевна

 
                                                   Сыктывкар, 2013        
 
                                                         1                                                                                                                       

                                                     
 
СОДЕРЖАНИЕ

Введение…..…………………………………………………………………….………………3

Основное содержание

1. Понятие алгоритма…………………………………………………………….4
2. История алгоритмов…………………………………………………………..4
3. Свойства алгоритма…………………………………………………………..5
4. Пример моего алгоритма…………………………………………………….8
5. Способы записи алгоритмов…………………………………………………9
6. Виды алгоритмов……………………………………………………………..12

Заключение……………………………………………………………………………………13

Список литературы…………………………………………………………………………..13 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
                                                                      2 
                                                 ВВЕДЕНИЕ 
 
 
    Большинство действий, совершаемых человеком, выполняются по определенным правилам. Их эффективность во многом зависит от того, насколько он представляет, что делать в каждый момент времени, в какой последовательности, каким должен быть итог его действий .Другими словами, результат деятельности человека непосредственно зависит от того, насколько он представляет алгоритмическую сущность своих действий. 
     Кроме того, применение в производстве и быту различных автоматов, компьютеров  требует от человека строгого  соблюдения определенной последовательности действий при их использовании ,что, в свою очередь ,невозможно без предварительного составления алгоритмов. 
    Таким образом, осмысление и разработка алгоритмов выполняемых действий становится существенным   компонентом деятельности человека, составной частью ее культуры мышления и поведения. Алгоритм-одно из фундаментальных понятий ,которое используется в различных   областях  знания, но изучается оно в математике и информатике. Его освоение начинается уже в начальной школе на уроках математики, где ученики овладевают алгоритмами арифметических действий, знакомятся  с правилами вычитания числа из суммы, суммы из числа и др. 
   Вообще формирование алгоритмического мышления  у младших  школьников в настоящее время является одной из важнейших задач учителя, и поэтому ему требуются определенные знания  об алгоритмах, а также некоторые умения в их построении.  

 
 
 
 
 
 
 
 
 
 
 
 
 
 
                                                          ОСНОВНОЕ СОДЕРЖАНИЕ 

                                           1.Определение алгоритма     
 
Слово «Алгоритм» происходит от algorithmi - латинского написания имени 
аль-Хорезми,  под  которым  в   средневековой   Европе   знали величайшего 
математика из Хорезма (город в современном Узбекистане) Мухаммеда бен  Мусу, жившего в 783-850 гг. В своей книге «Об индийском счете»  он сформулировал правила записи натуральных чисел с помощью арабских цифр и правила действий над ними  столбиком.  В дальнейшем  алгоритмом   стали   называть   точное предписание,  определяющее   последовательность   действий,   обеспечивающую получение требуемого результата из  исходных  данных.  Алгоритм  может быть предназначен для выполнения его человеком или автоматическим  устройством. Создание алгоритма, пусть даже самого простого,  -  процесс творческий.  Он доступен исключительно живым существам,  а долгое  время считалось, что только человеку. Другое дело  -  реализация  уже имеющегося  алгоритма.  Ее можно поручить субъекту или объекту, который не обязан  вникать в существо дела, а возможно, и не  способен  его понять.  Такой субъект или объект принято называть формальным исполнителем. Примером  формального исполнителя может служить стиральная машина-автомат,  которая  неукоснительно  исполняет предписанные ей действия, даже  если  вы  забыли  положить  в  нее порошок. Человек тоже может выступать в роли формального исполнителя,  но  в первую очередь формальными   исполнителями   являются   различные   автоматические устройства, и компьютер в том числе. Каждый алгоритм создается в расчете на вполне  конкретного исполнителя.  Те  действия,  которые может   совершать исполнитель,  называются  его допустимыми   действиями.   Совокупность допустимых действий образует систему команд  исполнителя.  Алгоритм  должен содержать только те действия, которые допустимы для данного исполнителя.

В Математическом энциклопедическом  словаре понятие алгоритм 
характеризуется как понятие математики  и информатики: «Алгоритм – точное предписание, которое задает вычислительный процесс (называемый в этом случае алгоритмическим),начинающийся с произвольного исходного данного…и направленный на получение полностью определяемого этим исходным данным результата. Алгоритмы прослеживаются в математике в течение всего времени ее существования. Общее понятие алгоритма сформировалось, однако, лишь в ХХ в.»

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

                                 2.Свойства алгоритма 
Чтобы какую-либо программу действий можно было назвать алгоритмом, она должна удовлетворять ряд требований. Эти требования называют свойствами алгоритма.

1.Каждая программа, задающая  алгоритм, должна состоять из  конечного числа шагов, а каждый  шаг должен быть точно и  однозначно определен. Это свойство  алгоритмов называют свойством определенности (или детерминированности).

Согласно этому свойству в алгоритмах не может быть таких, например, предписаний, как «сложить х с одним из данных чисел а или b», «привести два-три примера истинных и ложных высказываний» и т.д.

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

Дискретная структура алгоритмов хорошо видна в алгоритмах выполнения арифметических действий. Например, алгоритм нахождения суммы 34+23 формулируется  так:

            1)Пишу десятки под десятками, а единицы под единицами

      2)Складываю единицы: 4+3=7, пишу 7 под единицами.

      3)Складываю десятки: 3+2=5, пишу 5 под десятками.

      4)Читаю ответ: сумма равна 57.

3.Каждый шаг программы, задающей  алгоритм, должен состоять из  выполнимых действий. Это означает, что предусмотренные действия  были выполнимы теми исполнителями,  которым она адресована. Так, например, задание «решить уравнение х+9=17»  один ученик уверенно выполняет  и получает искомое значение  переменной х, так как владеет  всеми действиями, необходимыми  для решения простейших уравнений:

1)Прочитай уравнение;

2)Вспомни правило, как найти  значение неизвестного;

3)Реши уравнение;

                           4)Сделай проверку; 
                           5)Запиши ответ.

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

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

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

          Все сказанное характеризует  свойство алгоритма, называемое свойством понятности.

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

5.Программа, задающая алгоритм, должна быть применима к любой задаче рассматриваемого типа. Другими словами, каждый алгоритм предназначен для решения не одной-единственной, а любой из некоторого бесконечного класса однотипных задач. Например, алгоритм решения линейного уравнения первой степени применяется для всех уравнений вида ax+b=0. В этом состоит свойство массовости алгоритма.

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

Алгоритмы могут быть предназначаться  как исполнителю-человеку, так и  исполнителю-машине. И в связи  с этим между ними могут быть различия. Действия, понятные человеку, могут  быть не понятны машине (например, действие «вспомни правило»), и наоборот. Предписания  для человека могут содержать  желательные, но не обязательные действия, или их можно поменять местами. Например, чтобы определить значение истинности конъюнкции двух высказываний А и В, нужно:

1)Определить значение истинности высказывания А;

2)Определить значение истинности высказывания В;

3)Определить значение истинности высказывания А ʌ В.

     Так как операция конъюнкции коммутативна, т.е. А ʌ В <=> В ʌ А, то пункты 1) и 2) можно поменять местами. Такой выбор последовательности шагов осуществляет исполнитель-человек, но не машина. Если свойства детерминированности и дискретности сохраняются с некоторой степенью точности, т.е. в программе возможна перестановка шагов или она содержит желательные, но не обязательные шаги, то мы имеем не алгоритм, а алгоритмическое предписание. Однако, несмотря на различия между этими понятиями, часто алгоритмические предписания называются алгоритмами.

                                        3.Пример моего алгоритма 
                                   Алгоритм заварки чая 
 
1. Подготовить исходные величины - чай, воду, чайник, стакан, ложку.

2. Налить в чайник воду.

3. Довести воду до кипения  и снять с огня.

4. Всыпать в чайник  чай.

5. Довести воду до кипения,  снять с огня.

6. Чай готов. Процесс  прекратить.

Из определения алгоритма  вытекают его свойства:

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

2.      Определенность. Данное свойство означает, что  простые шаги, составляющие алгоритм, должны быть четкими, однозначными  и не оставлять места для  произвола.

3.      Понятность. Свойство, говорящее о том, что  исполнитель алгоритма должен  знать как выполнить каждый шаг алгоритма.

4.      Результативность. Это свойство означает, что алгоритм  должен приводить к решению  задачи за конечное число шагов.

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

Разработанная последовательность действий будет алгоритмом, если она  обладает всеми перечисленными выше свойствами.

                                      4.Способы записи алгоритмов 

Известны различные способы  записи алгоритмов: словесная запись, формульная, табличная, на языке блок-схем или алгоритмическом языке.

Словесная запись - это форма представления алгоритмических предписаний. Она допускает употребление естественного языка и математической символики, что делает предписание понятным и доступным для усвоения. Форму словесной записи имеют многие «бытовые» алгоритмические предписания, часто применяемые в повседневной жизни: как испечь пирог, как пользоваться электроприбором, как получить книгу в библиотеке и т.д. Вообще в этой форме могут быть описаны любые предписания, в том числе и математические. Например, алгоритмическое предписание нахождения середины отрезка АВ может иметь вид:

1. Поставить ножку циркуля в точку А;
2. Установить раствор циркуля, равный длине отрезка АВ;
3. Провести окружность;
4. Поставить ножку циркуля в точку В;
5. Провести окружность;
6. Отметить точки пересечения окружностей;
7. Через отмеченные точки провести прямую;
8. Отметить точку пересечения прямой с отрезком АВ.

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

Например, для нахождения корней квадратного  уравнения  ax²+ bx + c = 0 (а≠0) удобнее применять не словесную запись, а формулу:

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

Рассмотрим алгоритмическое предписание  решения следующей задачи: «В одном  куске 72 м ткани, а в другом в  у раз больше. Сколько метров ткани во втором куске? Составь выражение и найди его значение, если у=2, 4, 8».

Словесная запись алгоритма решения  данной задачи такова:

1. Составить выражение;
2. Найти его выражение для у=2;
3. Найти его выражение для у=4;
4. Найти его выражение для у=8.

Если же оформить предписание  в виде таблицы, то запись будет иметь  вид:

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

1. Каждый шаг записывается в форме определенной геометрической фигуры (блока);
2. Блок, соответствующий команде, предусматривающий выполнение некоторого действия, в результате которого образуется какой-то новый промежуточный или конечный результат, изображается в виде прямоугольника. Внутри него записывается выполняемое действие. Такие блоки называются арифметическими, или, в более общем виде, перерабатывающими информацию, так как не всегда выполняемые действия являются арифметическими;
3. Блок, соответствующий команде, предусматривающей проверку некоторого условия, изображается в виде ромба. Проверяемое логическое условие записывается внутри него. Выполнение данной команды не приводит к новому результату, а лишь определяет дальнейший ход процесса решения. Такие блоки называются логическими;
4. Если за шагом А непосредственно следует шаг В, то от блока А к блоку В проводится стрелка. От каждого арифметического блока исходит только одна стрелка; от каждого каждого логического – две стрелки: одна с пометкой «да»(или «+»), идущая к блоку, следующему за логическим блоком, если условие выполняется, другая – с пометкой «нет» (или «-»), идущая к блоку, следующему за логическим, если условие не выполняется;
5. Начало и конец алгоритма изображаются блоками в виде овалов, внутри которых записываются соответственно слова «Начало» и «Конец».

В качестве примера такой  записи рассмотрим алгоритмическое  предписание для решения задачи: «Из ряда чисел 15, 16, 17, 18 выпиши значение х, при которых верно неравенство  х+24>40».

      начало

         Х+24

Больше 40?

конец

                Х

     выписывать

 да нет

  В соответствии с этой схемой устанавливаем, что если х=15, то х+24 больше 40, следовательно, при этом значении х неравенство х+24>40 верным не будет. Аналогично для х=16. Если же х=17, то х+24 будет больше 40, и, значит, при этом значении х неравенство х+24>40 будет верным. Аналогично и для х=18.

Видим, что блок-схема  наглядно представляет логику решения  задачи. Поэтому запись алгоритмов в виде блок-схем имеет широкое  распространение.

Еще один способ – это  запись на определенном алгоритмическом языке. Она используется в том случае, когда исполнитель данного алгоритма – машина, причем каждая машина имеет свой, только ей понятный язык: фортран, паскаль, бейсик, лого и др.

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

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

                                                  5.Виды алгоритмов 
 
 
Существует 4 вида алгоритмов: линейный, циклический, разветвляющийся, вспомогательный.

Линейный (последовательный) алгоритм — описание действий, которые выполняются однократно в заданном порядке.

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

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

Многие процессы в окружающем мире основаны на многократном повторении одной и той же последовательности действий. Каждый год наступают весна, лето, осень и зима. Жизнь растений в течение года проходит одни и  те же циклы. Подсчитывая число полных поворотов минутной или часовой  стрелки, человек измеряет время.

Условие — выражение, находящееся  между словом «если» и словом «то» и принимающее значение «истина» или «ложь».

Разветвляющийся алгоритм — алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий.

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

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

Неполная форма, в которой  действия пропускаются: «если условие, то...».

Вспомогательный алгоритм — алгоритм, который можно использовать в других алгоритмах, указав только его имя.

Например: в детстве мы учились суммировать единицы, затем десятки, чтобы суммировать двузначные числа, содержащие единицы мы не учились новому методу суммирования, а воспользовались старыми методами. 
 
                                           6.Заключение 

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

• Алгоритм;
• Алгоритмическое предписание;
• Линейный, разветвляющийся ,вспомогательный и циклический алгоритм.

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

 
                                    Список литературы 
 
 
1)Стойлова Л.П. Математика: Учеб. пособие для студ. сред. пед. учеб. заведений. – 2-е издание, исправленное. – М.: Издательский центр «Академия», 1997. – 464 с.

2)Прохоров Ю.В. Математический  энциклопедический словарь / Под.ред Ю.В. Прохоров – М. «Советская энциклопедия»;1988. – 847 с. 
3)Интернет ресурс: 
http://metod-kopilka.ru/page-2-2-9-6.html