Алгоритм - это понятное и точное предписание исполнителю совершить последовательность действий, направленных на достижение определенной цели или на решение поставленной задачи.
Лекция 7
Тема:Алгоритмы и способы их описания. Принципы обработки информации компьютером.
Цели и задачи урока:
- Познакомить обучающихся с определением алгоритма и его основных свойств, рассказать о формах записи алгоритмов и их основных структурах.
- Представление числовой информации с помощью систем счисления.
- Развивать логику, умение анализировать, сравнивать, делать выводы, высказывать свою мысль.
- Воспитывать аккуратность, внимательность, вежливость и дисциплинированность, бережное отношение к своему здоровью.
- Практические задания.
Тип урока: лекция, изучения нового.
Оборудование: компьютер, проектор.
Ожидаемые результаты:
В конце занятия студенты смогут:
- дать определение алгоритма и его основных свойств;
- назвать основные структуры алгоритмов;
- рассказать об основных формах записи алгоритмов.
- Переводить числа из одной СС в другую.
Ход урока
I. Организационный момент.(Приветствие и проверка отсутствующих).
II. Изучение нового материала.
Многие считают, что информатика нужна только для того, чтобы научиться работать на компьютерах. Но это заблуждение, которое мы постараемся опровергнуть на нашем уроке, тема которого: «Алгоритмы. Свойства алгоритмов. Виды и способы записи алгоритмов».
Цель нашего урока – выяснить, что такое алгоритм, познакомится с историей возникновения данного понятия, его свойствами, видами алгоритмов и формами, с помощью которых можно записать тот или иной алгоритм, а также где в реальной жизни мы встречаемся с алгоритмами.
В настоящее время слово “алгоритм” является одним из важнейших понятий науки информатики.
Слово «алгоритм» происходит от имени великого среднеазиатского учёного Мухаммеда аль-Хорезми́, жившего в первой половине IX ве́ка (точные годы его жизни неизвестны, но считается, что он родился около 780 года, а умер около 850). «Аль-Хорезми» означает «из Хорезма» (исторической области в нынешнем Узбекистане, центром которой был город Хива).
А теперь выполним следующее задание.
Запишите определение алгоритма:
Алгоритм - это понятное и точное предписание исполнителю совершить последовательность действий, направленных на достижение определенной цели или на решение поставленной задачи.
Приведите примеры алгоритмов.
Ответы учащихся …
Из приведенных вами примеров видно, что мир алгоритмов очень разнообразен. Но, несмотря на это, можно выделить общие свойства, которыми обладает любой алгоритм:
Понятность - исполнитель алгоритма должен знать, как его выполнять;
Конечность - выполняемый алгоритм должен приводиться к результату за конечное число шагов;
Дискретность - любой алгоритм должен состоять из конкретных действий, следующих в определенном порядке;
Результативность - получение результата за конечное число шагов;
Массовость - один и тот же алгоритм можно использовать с различными исходными данными;
Формальность – возможность выполнять команды механически.
Это свойство позволяет поручить исполнение алгоритмов роботам, компьютерам и другим устройствам.
Описание действий в алгоритме следуют последовательно друг за другом. Однако очередность выполнения этих действий может быть изменена, если в алгоритме предусмотрен анализ некоторого условия. Путем включения условий создаются алгоритмы с различной структурой, в которой можно выделить несколько типовых конструкций: линейную, разветвляющуюся и циклическую.
Рассмотрим эти конструкции:
Предположим, что требуется составить алгоритм результата выражения: 50+10-15+20.
Как вы будем выполнять действия в этом выражении?
Ответы учащихся …
В этом примере вы выполняли действия в том порядке, в котором они записаны. Такие алгоритмы получили название линейных алгоритмов.
Запишите определение линейного алгоритма: Линейный алгоритм - это описание действий, которые выполняются однократно в заданном порядке.
Приведите примеры таких алгоритмов.
Ответы учащихся …
Давайте вспомним сюжет из русской сказки. Царевич останавливается у развилки дороги и видит камень с надписью: “Направо пойдешь - коня потеряешь, налево пойдешь - сам пропадешь …”. Подобная ситуация, заставляющая нас принимать решение в зависимости от некоторого условия, постоянно встречается в повседневной жизни.
Приведите пример такой ситуации.
Ответы учащихся …
Алгоритм, в котором используется условие, получил название разветвляющегося алгоритма.
Запишите определение разветвляющегося алгоритма: Разветвляющийся алгоритм - это алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий.
Разветвляющийся алгоритм может иметь две формы представления.
Запишите: Разветвляющийся алгоритм называется полным, если он имеет вид: “если <условие>, то … иначе …”
Разветвляющийся алгоритм называется неполным, если он имеет вид: “если <условие>, то …”.
Многие процессы в окружающем мире основаны на многократном повторении одной и той же последовательности действий. Например, каждый год наступают зима, весна, лето, осень.
Алгоритм, который содержит описание повторяющихся действий, называют циклическим. Число повторений в циклических процессах известно заранее или зависит от какого-либо условия.
Запишем определение циклического алгоритма: Циклический алгоритм - это описание действий, которые должны повторяться указанное число раз или пока не выполнено заданное условие.
Итак, любой алгоритм можно составить, используя только типовые алгоритмические конструкции.
Формы же представления этих алгоритмов могут быть разными.
На практике наиболее распространены следующие формы представления алгоритмов:
- словесная (записи на естественном языке);
- графическая (стрелки, изображения, блок-схемы);
- псевдокоды (полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.);
- программная (тексты на языках программирования).
Рассмотрим их:
1. Словесная форма - это форма описания алгоритма на естественном языке.
Данная форма очень удобна, если нужно приближенно описать суть алгоритма. Однако при словесном описании не всегда удается ясно и точно выразить идею.
2. Для более наглядного представления алгоритма используется графическая форма. Графическая форма - изображение алгоритма в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий.
Тема: Представление алгоритма в виде блок-схемы
В виде последовательности действий можно описать решения многих задач. Такое описание алгоритма естественным языком является словесной формой представления алгоритмов. Этот способ очень удобен, если требуется приблизительное описание сути алгоритма. Но он не всегда ясно и точно выражает идею.
Чаще всего алгоритм составляют (описывают) словесно, а затем, для его более наглядного представления, используют графическую форму – блок-схему. Блок-схема составляется из стандартных графических объектов:
| название фигуры | изображение | обозначаемый шаг алгоритма |
| овал | начало или конец алгоритма | |
| параллелограмм | ввод данных или вывод результата | |
| прямоугольник | выполнение действия | |
| ромб | проверка условия |
Последовательность действий указывается с помощью стрелок, соединяющих фигуры, обозначающие шаги алгоритма.
Составим представление в виде блок-схемы различных алгоритмических структур.
Линейный алгоритм.
Вопрос: какой алгоритм называется линейным?
Ответ: алгоритм, в котором команды выполняются последовательно друг за другом, называется линейным.
Рассмотрим алгоритм посадки дерева:
· выкопать в земле ямку
· опустить в ямку саженец
· засыпать ямку с саженцем землей
· полить саженец водой
С помощью блок-схемы данный алгоритм можно изобразить так, как показано на рисунке.
Разветвляющийся алгоритм
Ситуация, когда заранее известна последовательность требуемых действий, встречаются крайне редко. В жизни часто приходится принимать решение в зависимости от сложившейся обстановки.
Вопрос: какой алгоритм называется разветвляющимся?
Ответ: форма организации действий, при которой в зависимости от выполнения некоторого условия совершается одна или другая последовательность шагов, называется ветвлением.
Разветвляющийся алгоритм имеет две формы представления: полную и неполную.
Рассмотрим каждую на примерах:
Пример 1. ЕСЛИ уроки выучены, ТО иди гулять, ИНАЧЕ учи уроки.
В виде блок-схемы это будет выглядеть следующим образом:
Пример 2. ЕСЛИ низко ласточки летают, ТО будет дождь.
В виде блок-схемы это будет выглядеть следующим образом:
В первом случае разветвляющийся алгоритм имеет полную форму, а во втором - неполную.
Циклические алгоритмы
На практике часто встречаются задачи, в которых одно или несколько действий бывает необходимо повторить несколько раз, пока соблюдается некоторое заранее установленное условие.
Форма организации действий, при которой выполнение одно и той последовательности команд повторяется, пока выполняется некоторое заранее установленное условие, называется циклом (повторением). Алгоритм, содержащий циклы, называется циклическим алгоритмом или алгоритмом с повторениями.
Рассмотрим два варианта: условие поставлено в начале цикла, условие поставлено в конце цикла.
Пример 1. Рассмотрим алгоритм
1) смотрю телевизор вечером
2) если время меньше полуночи, то выполнить действие 1
3) если уже полночь, то завершаю просмотр
Блок-схема будет выглядеть следующим образом:
В данном случае выполнение условия приводило к продолжению работы цикла. Как только условие перестало выполняться, то работа цикла завершилась. Такой вид цикла называется ЦИКЛ с предусловием.
Пример 2. Рассмотрим алгоритм:
1) покрасим доску
2) если доски закончились, то завершаем работу
3) если есть еще доска, то перейти к ней и выполнить действие 1
Блок-схема будет выглядеть следующим образом:
В этом случае сначала выполняется действие, а затем проверяется условие и если оно не выполняется, то цикл продолжает работу. В случае выполнения условия, цикл завершает работу. Такой вид цикла называется ЦИКЛ с постусловием.
Домашнее задание . По условию задачи составить блок-схему: В корзине имеются белые и черные шары. Нужно белые шары положить в белую коробку, а черные – в черную.
Решение:
- Какие объекты участвуют в нашей задаче? (Корзина с шарами, шары, коробки.)
- Представим, как происходит сортировка шаров:
• приносят корзины с шарами;
• берут шар;
• смотрят на шар;
• если шар белый, то его кладут в белую коробку, иначе -в черную;
• берут следующий шар;
• смотрят...
- Что является самым важным в задаче? (Цвет шара.)
- С чего начинается алгоритм? (НАЧАЛО.)
- Далее надо ввести ШАРЫ или КОРЗИНУ С ШАРАМИ.
- Дальше? (Идет сортировка шаров: взять шар, посмотреть на него, определить цвет, положить в нужную коробку.)
- Для того чтобы определить цвет, как нам это изобразить в алгоритме? (УСЛОВИЕ с вопросом: «Шар белый?».)
- Из условия будет два выхода: ДА и НЕТ. Разберем, что будет на ветке «Да»? (ОБРАБОТКА «В белую коробку».) Что будет на ветке «Нет»?
- Куда дальше продолжить связь?
- Если мы в этом месте закончим алгоритм, то, после того как мы положим шар в коробку, дальнейшая сортировка прекратится.
- Недостаток этой блок-схемы заключается в том, что в ней нет конца.
- Что надо добавить, чтобы алгоритм имел окончание? (Надо узнать, есть ли в корзине еще шары, если да, то взять новый шар, иначе... закончить алгоритм.)
3.Псевдокод представляет собой систему обозначений и правил, предназначенную для единообразной записи алгоритмов. Он занимает промежуточное место между естественным и формальным языком. (слайд 21)
Принципы обработки информации компьютером.
На практике в качестве исполнителей алгоритмов используются специальные автоматы – компьютеры. Поэтому алгоритм, предназначенный для исполнения на компьютере, должен быть записан на понятном ему языке. Такой язык принято называть языком программирования, а форму представления алгоритма - программной.
Алгоритм, записанный на понятном компьютеру языке программирования, называется программой.Программа – это последовательность инструкций и правил, которые сообщают компьютеру определенный порядок выполнения заданий.
"Все есть число", — говорили пифагорийцы, подчеркивая необычайно важную роль чисел в практической деятельности. Известно множество способов представления чисел. В любом случае число изображается символом или группой символов (словом) некоторого алфавита. Будем называть такие символы цифрами. Для представления чисел используются непозиционные и позиционные системы счисления.