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

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

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

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

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

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

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

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

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

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

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

 

 

 

РЕФЕРАТ

 

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

 

 

 

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

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

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

 

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

студентка 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) удобнее применять не словесную запись, а формулу: