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

Лекция 1.

Раздел 1. Основы алгоритмизации.

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

Слово алгоритм появилось еще в 9в. Когда на латинский язык переводились труды великого восточного ученого Мухаммеда Аль Хорезми. Он занимался математикой и первым написал четкие, краткие указания, следуя которым можно было решить уравнения первой и второй степени. На латынь имя Аль Хорезми перевели как Алгоритм. И учителя, обучая решению уравнений первой и второй степени, говорили: «Следуйте указаниям алгоритма», а потом просто: «Следуйте алгоритму».

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

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

С алгоритмом обязательно связаны понятия исполнителя, и СКИ.

Исполнитель алгоритма, тот, кто выполняет данный алгоритм. Исполнителем может быть человек, компьютер, ЯП.

СКИ (система команд исполнителя)- та совокупность действий, которые может делать исполнитель.

Возникает вопрос: любая ли последовательность действий (или инструкция) является алгоритмом?

Конечно, нет. Не всякая инструкция алгоритм, а только та, которая обладает определенными свойствами.

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

1. Понятность - все шаги алгоритма должны содержатся в СКИ.

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

3. Определенность - не должно содержаться шагов с неоднозначным смыслом.

4. Результативность - алгоритм должен заканчиваться через конечное число шагов определенным результатом.

5. Массовость - алгоритм создается не для одной конкретной задачи, а для целого блока однотипных задач.

Привести примеры алгоритмов, не удовлетворяющих свойствам.

ü Исполнитель: робот;

СКИ: вперед, вправо, влево, назад;

Алгоритм «перехода к заданному месту»:

Вправо;

Вперед;

Влево;

Вперед;

Вверх;

Влево.

Данный алгоритм не удовлетворяет свойству понятности, так как в СКИ нет команды Вверх.

ü Алгоритм «взятия ручки с синей пастой с парты»

Зайти в класс;

Подойти к парте;

Взять ручку с синей пастой.

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

ü Алгоритм нахождения суммы двух чисел.

Прибавить 2+3;

Результат вывести на экран.

Данный алгоритм не удовлетворяет свойству массовости.

ü Алгоритм вывода на печать квадратов натуральных чисел от 1 до 15.

Задать х значение 1;

Пока х меньше 15 выводить на экран х²;

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

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

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

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

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

Лекция 2.

Вопросы: (отвечаем по цепочки, начиная с первой парты первого ряда)

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

ü Перечислить все свойства алгоритма.

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