Алгоритмы. Понятие алгоритмов, свойства алгоритма.

Тема: Понятие алгоритмов, свойства алгоритма. Исполнители алгоритмов, система команд исполнителя. Способы записей алгоритмов. Формальное исполнение алгоритмов.

Тип урока: ознакомление с новым материалом.

Цели: 

·        Способствовать развитию алгоритмического мышления;

·        Дать понятие алгоритма, рассказать о свойствах, дать классификацию алгоритмов;

·        Познакомить с формой записи алгоритмов – блок-схема.

Оборудование: проектор, презентация.

Ход урока

 1 орг. Момент  

Приветствие, посадка, перекличка.

2 Актуализация опорного материала

Ребята, скажите пожалуйста, как вы понимаете слово  алгоритм? Где нам приходится сталкиваться с этим понятием?

3 Изложение материала

Происхождение термина «алгоритм» связано с математикой. История его возникновения такова. В IX веке в Багдаде жил ученый ал(аль)-Хорезми (полное имя - Мухаммед бен Муса ал-Хорезми, т.е. Мухаммед сын Мусы из Хорезма), математик, астроном, географ. В одном из своих трудов он описал десятичную систему счисления и впервые сформулирован правила выполнения арифметических действии над целыми числами и обыкновенными дробями. Арабский оригинал этой книги был утерян, но остался латинский перевод XII в., по которому Западная Европа ознакомилась с десятичной системой счисления и правилами выполнения арифметических действий.

Ал-Хорезми стремился к тому, чтобы сформулированные им правила были понятными. Достичь этого в IX в., когда еще не была разработана математическая символика (знаки операций, скобки, буквенные обозначения и т.д.), было трудно. Однако ему удаюсь выработать четкий стиль строгого словесного предписания, который не давал читателю возможность уклониться от предписанного или пропустить какие-нибудь действия.

Правила в книгах см-Хорезми в латинском переводе начинались словами «Алгоризми сказал». В других латинских переводах автор именовался как Алгоритмус. Со временем было забыто, что Алгоризми (Алгоритмус) - это автор правил, и эти правила стали называть алгоритмами. Многие столетия разрабатывались алгоритмы для решения все новых и новых классов задач, но само понятие алгоритма не имело точного математического определения.

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

Алгоритм - точное и понятное предписания исполнителю  совершить последовательность действий направленных на решение поставленной задачи.

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

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

Технический исполнитель – банкомат;

Биологический - человек, живой организм;

Биотехника - искусственный интеллект.

Свойства алгоритмов

Дискретность (раздельность, прерывность) – алгоритм должен быть записан  в виде последовательности шагов или этапов.

Понятность исполнитель алгоритма должен знать, как этот алгоритм выполнять.

Определенность (детерминированность) каждое правило алгоритма должно быть четким, однозначным и не оставлять места для произвола.

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

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

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

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

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

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

Формы записи алгоритмов:

Словесный представляет собой описание последовательных этапов обработки данных. Алгоритм представляет собой произвольное изложение на естественном языке

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

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

Графические формы записи алгоритмов:

				Вычисление

 

Основные алгоритмические структуры

Следование(линейный алгоритм)                                         Циклы

 

Ветвление

+

 

Следование – команды выполняются одна за другой  в том порядке, в котором они записаны в алгоритме.( (Пример. Алгоритм открывания двери в квартиру: достать ключ, вставить в замочную скважину, повернуть нужное количество раз, достать ключ, открыть дверь. закрыть дверь)

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

Цикл(повторение) - в процессе выполнения алгоритма многократно повторяется определенный  набор команд. (Пример. (Мытье 10 тарелок: взять тарелку, помыть, поставить в сушку, взять тарелку, помыть, поставить в сушку и т. д. пока не закончатся тарелки.)

4 Применение полученных знаний

Задача  исполнить команды алгоритма при а=1, b=2, с=3

1.  умножить b на b. результат записать в R1 ;             {R1=4}

2.            умножить а на с, результат записать в R2;          {R2=3}

3.            умножить 4 на R2. результат записать в R3;        {R3=12}

4.      вычесть R3 из R1. результат записать в d      (d= -8)

Восстановим формулу вычисления: d=Rl-R3=b*b-4*R2^:=b²-4ac

Что получается? (дискриминант квадратного уравнения. )

Это пример формального исполнителя алгоритма.

Задача2 Нарисовать блок-схему для возведения любого целого числа в квадрат.

5 ИТОГ

Первичная проверка знаний

1.     Что такое алгоритм?

2.     Какими свойствами должен обладать алгоритм?

3.     Приведите  примеры исполнителей алгоритмов?

4.     Какие способы записи существуют?

5.      Приведите пример алгоритмических структур?