Презентация по информатике "Алгоритм и его формальное исполнение"

Кибернетика

В 1948 г. В США и Европе вышла книга Норберта Винера «Кибернетика, или Управление и связь в животном и машине».

С этого момента и стали говорить о новой науке – кибернетике.

Кибернетика – наука об общих свойствах процессов управления в живых и неживых системах.

Управление – это целенаправленное воздействие одних объектов (управляющих) на другие объекты – управляемые.

Алгоритм

Все управляющие воздействия производятся в форме команд.

Команды отдаются с определенной целью.

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

Происхождение слова «алгоритм»

Слово «алгоритм» происходит от имени арабского учёного Мухаммед ибн Муса ал-Хорезми.

Понятие алгоритма

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

Кто играет роль исполнителя и управляющего в следующих системах: школа, самолет, стая волков?

Задание:

Назови исполнителей следующих видов работы:

Уборка мусора во дворе

Обучение детей в школе

Вождение автомобиля

Ответ у доски

Приготовление пищи

Печатание документа на принтере

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

Необходимая задача:

Звонок по телефону…Как позвонить?

Алгоритм действий:

1) поднять телефонную трубку;

2) если услышал длинный гудок, то набрать номер, иначе выполнить  п. 6(телефон не исправен);

3) определить тип гудков: «вызов» или «занято». Если «вызов», перейти на п. 4, если «занято», перейти на п. 6;

4) дождаться 5 вызывающих гудков;

5) если за это время абонент не поднял трубку, то выполнить п. 6.

6) Положить трубку.

АЛГОРИТМ

И его формальное исполнение

КИБЕРНЕТИКА

• В 1948 г. В США и Европе вышла книга Норберта Винера «Кибернетика, или Управление и связь в животном и машине».
• С этого момента и стали говорить о новой науке – кибернетике.
• Кибернетика – наука об общих свойствах процессов управления в живых и неживых системах.
• Управление – это целенаправленное воздействие одних объектов (управляющих) на другие объекты – управляемые.

Норнберт Винер (1894 – 1964 гг.)

Норнберт Винер

(1894 - 1964 гг.)

(справа), Массачусетский технологический институт.

АЛГОРИТМ

• Все управляющие воздействия производятся в форме команд.
• Команды отдаются с определенной целью.
• Последовательность команд по управлению объектом, выполнение которых приводит к достижению поставленной ранее цели называется алгоритмом управления.

ПРОИСХОЖДЕНИЕ СЛОВА « АЛГОРИТМ»

Слово « алгоритм » происходит от имени арабского учёного Мухаммед ибн Муса ал-Хорезми.

В латинском переводе книги Ал-Хорезми правила начинались словами « Алгоризми сказал ». С течением времени люди забыли, что «Алгоризми» - это автор правил, и стали просто называть правила алгоритмами.

ПОНЯТИЕ АЛГОРИТМА

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

Алгоритм – это строго определенная последовательность действий при решении задачи.

Алгоритм содержит несколько шагов.

Шаг алгоритма – это каждое отдельное действие алгоритма.

Исполнитель – это объект, умеющий выполнять определенный набор действий. Исполнителем может быть человек, робот, животное, компьютер.

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

Среда исполнителя – обстановка, в которой функционирует исполнитель.

КТО ИГРАЕТ РОЛЬ ИСПОЛНИТЕЛЯ И УПРАВЛЯЮЩЕГО В СЛЕДУЮЩИХ СИСТЕМАХ : ШКОЛА, САМОЛЕТ, СТАЯ ВОЛКОВ?

Управляющий

Исполнитель

Система

Администрация

Школа

Коллектив, учащиеся

Самолет

Пилот

Самолет

Пассажиры

Стюардессы

Вожак

Остальные волки

Стая волков

ЗАДАНИЕ: НАЗОВИ ИСПОЛНИТЕЛЕЙ СЛЕДУЮЩИХ ВИДОВ РАБОТЫ:

• Уборка мусора во дворе
• Обучение детей в школе
• Вождение автомобиля
• Ответ у доски
• Приготовление пищи
• Печатание документа на принтере

СВОЙСТВА АЛГОРИТМА

• А если мы не закончим действие 4, и сразу будем выполнять действие 5, нам удастся дозвониться?

Необходимая задача:

Звонок по телефону…Как позвонить?

Алгоритм действий:

• поднять телефонную трубку;
• если услышал длинный гудок, то набрать номер, иначе выполнить п. 6(телефон не исправен);
• определить тип гудков: «вызов» или «занято». Если «вызов», перейти на п. 4, если «занято», перейти на п. 6;
• дождаться 5 вызывающих гудков;
• если за это время абонент не поднял трубку, то выполнить п. 6.
• Положить трубку

• А если мы будем делать все действия сразу?

СВОЙСТВА АЛГОРИТМОВ

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

2 апреля 1973 года был сделан первый звонок с помощью мобильного телефона.

Мартин Купер (Martin Cooper) держит в руках беспроводной телефон Motorola DynaTAC.

СВОЙСТВА АЛГОРИТМОВ

Необходимая задача:

Поездка на автобусе номер 2

• Прийти на автобусную остановку;
• Если нет автобуса, то дождаться его приезда;
• Иначе, посмотреть номер маршрута;
• Если номер маршрута – 2, то сесть в него;
• Иначе п. 2.

2

1

СВОЙСТВА АЛГОРИТМОВ

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

Последовательность строго соблюдается.

0 , тогда число A - больше Результативность – исполнение алгоритма должно приводить к конкретному результату. Это свойство требует, чтобы в алгоритме не было ошибок . " width="640"

СВОЙСТВА АЛГОРИТМОВ

Нахождение большего из двух чисел

• Из числа A вычесть число B .
• Если получилось отрицательное значение, то сообщить, что число B больше.
• Если получилось положительное значение, то сообщить, что число A больше.

Если (A-B)

Если (A-B)0 , тогда число A - больше

Результативность – исполнение алгоритма должно приводить к конкретному результату.

Это свойство требует, чтобы в алгоритме не было ошибок .

СВОЙСТВА АЛГОРИТМОВ

Конечность – завершение работы алгоритма за конечное число шагов.

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

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

Т.е. один и тот же алгоритм можно применять к большому числу данных.

Это свойство не следует понимать как возможность решить много задач.

СВОЙСТВА АЛГОРИТМОВ

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

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

СВОЙСТВА АЛГОРИТМА

ФОРМЫ ЗАПИСИ АЛГОРИТМОВ

• Словесно-формульный

Например , Составить алгоритм решения арифметического выражения ( 23+34)*57/3

1 шаг 23+34=57

2 шаг 57*57=3249

3 шаг 3249/3=1083

• С помощью алгоритмического языка

Например , Составить алгоритм решения алгебраического выражения x=2y+z

алг Выражение

арг y,z: цел

рез x: цел

нач

x:= 2* y

x:=x+z

кон

• Таблицы

• Блок-схемы

ЭЛЕМЕНТЫ БЛОК-СХЕМЫ

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

Параллелограмм, предназначен для описания ввода или вывода данных, имеет один вход вверху и один выход внизу

Прямоугольник, применяется для описания линей­ной последовательности команд, имеет один вход вверху и один выход внизу

Ромб, служит для обозначения условий в алгоритми­ческих структурах «ветвление» и «выбор», имеет один вход верху и два выхода (налево, если условие вы­полняется, и направо, если условие не выполняется)

Прямоугольник со срезанным углом, применяется для объявления переменных или ввода комментариев.

Начало

Данные

Последовательность

команд

Условие

Объявление

переменных

МАШИННЫЙ ЯЗЫК

АССЕМБЛЕР

ЯЗЫКИ ПРОГРАММИРОВАНИЯ ВЫСОКОГО УРОВНЯ

QBASIC

PASCAL

Французский физик-математик

Блез Паскаль

Программа Pascal , названная в честь

Блеза Паскаля

DELPHI

ТИПЫ АЛГОРИТМОВ

• Линейный
• Разветвлённый(алгоритмические структуры «ветвление» и «выбор»)
• Циклический (алгоритмическая структура «цикл»)
• Вспомогательный

ТИПЫ АЛГОРИТМОВ

• Линейный алгоритм – это алгоритм, в котором команды выполняются последовательно одна за другой .
• Разветвлённый алгоритм – алгоритм, в котором в зависимости от истинности или ложности условия выполнятся одна или другая серия команд.
• Циклический алгоритм – это алгоритм, в котором одна и та же последовательность действий совершается многократно (или ни разу) до тех пор, пока выполняется условие.
• Вспомогательный алгоритм – самостоятельный алгоритм , снабжённый таким заголовком , который позволяет вызывать этот алгоритм из других алгоритмов.

ЛИНЕЙНЫЙ АЛГОРИТМ

Пример. Алгоритм посадки дерева .

Начало

Выкопать в земле ямку

Опустить в ямку саженец

Закопать ямку с саженцем землёй

Полить саженец водой

Конец

РАЗВЕТВЛЁННЫЙ АЛГОРИТМ

Из трёх монет одинакового достоинства одна фальшивая (лёгкая). Как её найти с помощью одного взвешивания на чашечных весах без гирь?

Начало

Положить по 1 монете на каждую чашу весов,

третью монету отложить в сторону

Весы

в равновесии?

Нет

Да

Монета на поднявшейся

вверх чаше фальшивая

Отложенная монета

фальшивая

Конец

ЦИКЛИЧЕСКИЙ АЛГОРИТМ

Домашнее задание по математике

Начало

Есть

нерешённые задачи

по математике?

Нет

Да

Решить задачу

Пойти погулять

Конец