Виды и свойства алгоритмов

План - конспект урока

( 9 класс)

«Алгоритмы, понятия алгоритма, свойства алгоритма. Исполнители алгоритма»

Подготовил:

Учитель информатики

Хакимов Т.Р.

2015-2016

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

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

Цели:

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

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

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

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

Ход урока

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. Приведите пример алгоритмических структур?