Лекция 1 по дисциплине Теория алгоритмов. Лекция 1. Конспект урока на тему "Алгоритм. Свойства алгоритмов. Виды алгоритмов и формы записи алгоритмов"
 Скачать 44 Kb.
|
|
Конспект урока на тему "Алгоритм. Свойства алгоритмов. Виды алгоритмов и формы записи алгоритмов" Слово «алгоритм» происходит от имени великого среднеазиатского учёного Мухаммеда аль-Хорезми́, жившего в первой половине IX ве́ка (точные годы его жизни неизвестны, но считается, что он родился около 780 года, а умер около 850). «Аль-Хорезми» означает «из Хорезма» (исторической области в нынешнем Узбекистане, центром которой был город Хива). Алгоритм - это понятное и точное предписание исполнителю совершить последовательность действий, направленных на достижение определенной цели или на решение поставленной задачи. Свойства алгоритмов. Понятность - исполнитель алгоритма должен знать, как его выполнять; Конечность - выполняемый алгоритм должен приводиться к результату за конечное число шагов; Дискретность - любой алгоритм должен состоять из конкретных действий, следующих в определенном порядке; Результативность - получение результата за конечное число шагов; Массовость - один и тот же алгоритм можно использовать с различными исходными данными; Формальность – возможность выполнять команды механически. Это свойство позволяет поручить исполнение алгоритмов роботам, компьютерам и другим устройствам. Описание действий в алгоритме следуют последовательно друг за другом. Однако очередность выполнения этих действий может быть изменена, если в алгоритме предусмотрен анализ некоторого условия. Путем включения условий создаются алгоритмы с различной структурой, в которой можно выделить несколько типовых конструкций: линейную, разветвляющуюся и циклическую. Линейный алгоритм - это описание действий, которые выполняются однократно в заданном порядке. Разветвляющийся алгоритм - это алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий. Разветвляющийся алгоритм может иметь две формы представления. Запишите: Разветвляющийся алгоритм называется полным, если он имеет вид: “если <условие>, то … иначе …” Разветвляющийся алгоритм называется неполным, если он имеет вид: “если <условие>, то …”. Многие процессы в окружающем мире основаны на многократном повторении одной и той же последовательности действий. Например, каждый год наступают зима, весна, лето, осень. Алгоритм, который содержит описание повторяющихся действий, называют циклическим. Число повторений в циклических процессах известно заранее или зависит от какого-либо условия. Циклический алгоритм - это описание действий, которые должны повторяться указанное число раз или пока не выполнено заданное условие. На практике наиболее распространены следующие формы представления алгоритмов: словесная (записи на естественном языке); графическая (стрелки, изображения, блок-схемы); псевдокоды (полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.); программная (тексты на языках программирования). Рассмотрим их: 1. Словесная форма - это форма описания алгоритма на естественном языке. Данная форма очень удобна, если нужно приближенно описать суть алгоритма. Однако при словесном описании не всегда удается ясно и точно выразить идею. 2. Для более наглядного представления алгоритма используется графическая форма. Графическая форма - изображение алгоритма в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий. 3. Псевдокод представляет собой систему обозначений и правил, предназначенную для единообразной записи алгоритмов. Он занимает промежуточное место между естественным и формальным языком. 4. На практике в качестве исполнителей алгоритмов используются специальные автоматы – компьютеры. Поэтому алгоритм, предназначенный для исполнения на компьютере, должен быть записан на понятном ему языке. Такой язык принято называть языком программирования, а форму представления алгоритма - программной. Алгоритм, записанный на понятном компьютеру языке программирования, называется программой. |