Билет 6
————————————————————————————————————————
1. Понятие алгоритма. Исполнитель алгоритма. Система команд исполнителя (на примере учебного исполнителя). Свойства алгоритма. Способы записи алгоритмов; блок-схемы.
————————————————————————————————————————
За время своего существования человечество выработало правила поведения в определенных ситуациях для достижения поставленных целей. Часто эти правила можно представить в виде инструкций, состоящих из последовательно выполняемых пунктов (шагов). Так, например, в первобытном обществе инструкция охотникам по восполнению продовольственных запасов племени могла бы выглядеть следующим образом:
Возможно, что некоторые наскальные рисунки, сделанные до возникновения письменности, представляли собой своеобразную запись таких инструкций.
Что такое алгоритм?
Алгоритм – это понятное и точное предписание исполнителю выполнить конечную последовательность команд, приводящую от исходных данных к искомому результату.
Алгоритм выполняется за определенное количество шагов. Шаг – отдельное законченное действие.
Рассмотрим пример алгоритма для нахождения середины отрезка при помощи циркуля и линейки.
Алгоритм деления отрезка АВ пополам:
1) поставить ножку циркуля в точку А;
2) установить раствор циркуля равным длине отрезка АВ;
3) провести окружность;
4) поставить ножку циркуля в точку В;
5) провести окружность;
6) через точки пересечения окружностей провести прямую;
7) отметить точку пересечения этой прямой с отрезком АВ.
Каждое указание алгоритма предписывает исполнителю выполнить одно конкретное законченное действие. Исполнитель не может перейти к выполнению следующей операции, не закончив полностью выполнения предыдущей. Предписания алгоритма надо выполнять последовательно одно за другим, в соответствии с указанным порядком их записи. Выполнение всех предписаний гарантирует правильное решение задачи. Данный алгоритм будет понятен исполнителю, умеющему работать с циркулем и знающему, что такое поставить ножку циркуля, провести окружность и т. д.
Анализ примеров различных алгоритмов показывает, что запись алгоритма распадается на отдельные указания исполнителю выполнить некоторое законченное действие. Каждое такое указание называется командой. Команды алгоритма выполняются одна за другой. После каждого шага исполнения алгоритма точно известно, какая команда должна выполняться следующей.
Поочередное выполнение команд алгоритма за конечное число шагов приводит к решению задачи, к достижению цели. Разделение выполнения решения задачи на отдельные операции (выполняемые исполнителем по определенным командам) — важное свойство алгоритмов, называемое дискретностью.
Исполнители часто встречаются в сказках. В одной из них Иван-Царевич говорит Избушке-На-Курьих-Ножках: “Избушка, избушка! Встань к лесу задом, ко мне передом!”. При этом команда должна быть задана очень точно, чтобы исполнитель ее понял. В сказке “Али-Баба и сорок разбойников” волшебная дверь открывалась по команде “Сезам, откройся!”. Жадный Касым, тайно проникший в пещеру, забыл эту фразу и не смог выйти из пещеры.
• Исполнитель алгоритма — это некоторая абстрактная или реальная (техническая, биологическая или биотехническая) система, способная выполнить действия, предписываемые алгоритмом.
• Система команд исполнителя (СКИ) – это все команды, которые исполнитель умеет выполнять.
Отказы исполнителя возникают, если команда вызывается пpи недопустимом для нее состоянии сpеды.
• Среда исполнителя – обстановка, в которой функционирует исполнитель.
Исполнителями могут быть
Как и любой исполнитель, Робот понимает только ограниченный набор команд, которые входят в его СКИ (список команд исполнителя). Некоторые примеры команд:
направо; повернуться на 90 градусов вправо
налево; повернуться на 90 градусов влево
кругом; развернуться кругом (на 180 градусов)
вперед ( n ); перейти на n клеток вперед
назад ( n ); перейти на n клеток назад
посади; посадить цветы на грядке в том месте, где стоит Робот
В какой форме записываются алгоритмы?
На практике наиболее распространены следующие формы представления алгоритмов:
Графический способ записи алгоритмов
(блок-схема)
Графический способ представления алгоритмов является более компактным и наглядным по сравнению со словесным.
При графическом представлении алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий.
В блок-схеме каждому типу действий (вводу исходных данных, вычислению значений выражений, проверке условий, управлению повторением действий, окончанию обработки и т.п.) соответствует геометрическая фигура, представленная в виде блочного символа. Блочные символы соединяются линиями переходов, определяющими очередность выполнения действий.
Основные алгоритмические блоки
Начало-Конец (блок начала и конца алгоритма)
Процесс (вычислительное действие или последовательность действий)
Информатика
Именная карта банка для детей
с крутым дизайном, +200 бонусов
Закажи свою собственную карту банка и получи бонусы
План урока:
Начнем урок с простой задачи. Что нужно сделать, если хочется выпить чая?
Один человек сразу включает чайник, потом начинает искать чашки, заварку, сахар.
Второй действует согласно плану:
Первый человек сразу бежит к цели, сломя голову, а второй – определяется с целью, разбивает сложный процесс на простые этапы и шаг за шагом идти к результату. Такой линейный алгоритм из жизни позволяет не запутаться, не пропустить что-то важное. Второй подход рациональнее, логичнее и удобнее, позволяет сложную задачу разбить на более простые.
Система команд или алгоритм, не просто удобнее, она позволяет выполнить задачу даже тому, кто не делает это часто, то есть новичку.
Алгоритмы, которыми мы пользуемся
Алгоритм – конечная последовательность действия, пошаговый план, инструкция, способ действия позволяющие достичь желаемого результата. Состоит из простейших команд.
Такие удобные инструкции мы используем постоянно, даже не осознавая это.
Давайте вспомним, какими детальными инструкциями мы пользуемся:
Имея цель, мы обрабатываем входные данные и получаем результат или объяснение, почему результат не может быть получен. Это напоминает функцию, но в случае с алгоритмами даны четкие рекомендации, что и как делать.
Пример в виде красочной инструкции и сухой пошаговой рекомендации:
Работа за компьюетром Инструкция по настройке
А в информатике без них не обойтись – именно на алгоритмах основано программирование.
При написании такой последовательности команд важно разбивать процесс на самые простые действия, которые понимаются однозначно как разработчиком, так и тем, кто будет ими пользоваться.
Если действия однотипные, например, «набрать ковш воды и вылить» или «взять яблоко и проверить, есть ли червоточина», то его записывают 1 раз и повторяют конечное число раз.
Когда все задания/этапы будут выполнены, они должны привести к желаемому результату.
Исполнители, система команд исполнителя (СКИ)
Алгоритм разрабатывается с учетом определенного исполнителя. Это означает, что инструкция для пользователя спутниковой антенны и рекомендации для инженера-настройщика будут совершенно разными, хотя в обоих случаях каждый этап будет элементарный.
Исполнитель – субъект/объект, который может выполнить команды данного алгоритма.
Исполнителем может быть живое существо и неживой механизм. Человек, животное, которое понимает команды, робот, станок, компьютер – все они могут быть исполнителями.
Компьютер (ПК) – автоматизированный исполнитель команд. Алгоритмы программ для ПК пишут на языках программирования (С++, Basic, Pascal, Delphi, Ассемблер, Фортран).
Для каждого типа и уровня исполнителей существует своя система команд исполнителя (СКИ).
Свойства алгоритмов
Независимо от того, разрабатывается ход приготовления яичницы или запуска космического корабля, они должны обладать 5 основными свойствами:
Понятность – процедура должна быть на языке, который понятен той категории исполнителей, для которых она пишется.
Для ребенка 2 лет обучение пользованию игрушкой будет происходить простыми словами, с минимумом этапов (возьми, нажми эту кнопочку, поставь на пол). А для ребенка 10 лет инструкция уже будет включать проверку и замену батареек, установку отпавшей части.
Точность – команды должны быть конкретными, понятными, однозначными.
Пример непонятного и неточного задания мы помним из сказки: “Пойди туда, не знаю куда. Принеси то, не знаю что”.
Пример бесконечного алгоритма
В этом примере нет конечных команд: вымыть руки и выключить воду. Пользователь по этой инструкции будет бесконечно мыть руки, точить воду.
Классификация алгоритмов
Если выполняемые действия идут одно за другим, то инструкция будет последовательной, линейной. Если же операции повторяются при разных условиях, то порядок действия будет меняться. Следует использовать различные виды алгоритмов.
Виды алгоритмов:
Чаще используют алгоритмы повторения с условием, так как идеальные условия встречаются редко.
Линейная модель подходит для простых задач, когда нет условий или повторений. Для нее важна последовательность команд алгоритма. Например, вычисление среднего арифметического, площади фигуры. В обычной жизни – это список действий, которые нужно выполнить, чтобы купить хлеб, сварить яйцо или сделать бутерброд.
Запишем схему линейного алгоритма (покупки чая):
Для многих задач важно выполнение определенного условия.
Пример алгоритма ветвления – если нужного сорта нет, то процесс покупки чая усложняется:
Эту же задачу можно описать при помощи циклического алгоритма, если есть повторение определенной операции.
Данный пример включает в себя ветвление «если» и повторение команд:
Цикличные инструкции следует писать так, чтобы не было вечного цикла или зацикливания – бесконечного повторения операции без достижения результата.
Виды записи алгоритмов
Самый простой способ записать алгоритм построчно – словесно. Но текстовая форма оформления подобных детальных инструкций не всегда наглядна и удобна из-за большого количества вспомогательных слов.
Легче воспринимается такой план, если его дополнять картинками.
Особенно неудобно описывать словами математические, физические и химические процессы. Без специальных символов, формул не обойтись. Поэтому используются отраслевые сокращения и обозначения.
Но все эти способы записи алгоритмов уступают формальному, схематическому. Именно такой обобщенный подход позволяет пользователям и исполнителям со всего мира лучше понимать друг друга.
Блок-схема – графическая форма представления алгоритмов при помощи геометрических объектов и стрелок.
Блок схема линейного алгоритма вычисления площади прямоугольника:
Алгоритм – это инструкция к решению определенной задачи. А на этом основании можно написать программу вычисления алгоритма, которая реализует данный вариант решения, плюс ее можно установить, проверить и выполнить на ПК.
Пример алгоритма на Turbo Pascal
При программировании на компьютерных языках используется такой же подход, как и при написании инструкций вручную.
Для примера попробуем программирование линейных алгоритмов при помощи языка Turbo Pascal.
Запустить среду программирования следующими шагами:
Меню Пуск → Все программы → Turbo Pascal
На экране монитора появится оболочка, которая позволяет освоить азы программирования и даже реализовывать непростые проекты.
Оболочка разработана под DOS, что объясняет необычную реализацию интерфейса.
Пишем самый простой алгоритм программы для выведения на экран слов приветствия.
На латинской раскладке набираем в синем окне такие команды:
program Test;
begin
write(‘Доброе утро!’);
Учитываем важные моменты при использовании языка Турбо Паскаль:
Как видим, в программе есть свои слова-команды, как в письменных алгоритмах. Слово program – как заголовок, название объекта, а тest – непосредственно название программы.
Началом является команда begin, end – окончанием, а между ними стоят операторы или команды-действия («write» – напиши на экране). А текст, который нужно выводить на экране берется в скобки и ’….’.
Чтобы запустить программу, следует нажать Ctrl+F9 или набор команд Run Run.
Если нет ошибок в командах, появится такой результат:
Чтобы выйти обратно, можно нажать любую кнопку клавиатуры.
При каждом запуске будет новая запись, на той же строке. Если заменить write на writeln, то текст будет выводиться в новой строчке:
Изучение алгоритмов не только позволяет применять их во всех сферах жизни, начиная с ежедневных домашних дел и заканчивая учебой. Это первый и один из важнейших шагов понимания работы программируемой техники, в том числе ПК. Понимание простейших, линейных алгоритмов, умение их создавать позволяет узнать, как компьютер обрабатывает данные, находит верный результат и выдает его. Далее следует осваивать варианты с ветвлением или повторением.
Без умения создавать алгоритмы в виде блок-схемы, знания их видов и принципов создания невозможно начать изучение языков программирования.
Алгоритмические машины и свойства алгоритмов
Урок 13. Информатика 10 класс (ФГОС)
В данный момент вы не можете посмотреть или раздать видеоурок ученикам
Чтобы получить доступ к этому и другим видеоурокам комплекта, вам нужно добавить его в личный кабинет, приобрев в каталоге.
Получите невероятные возможности
Конспект урока «Алгоритмические машины и свойства алгоритмов»
В начале урока давайте вспомним, что такое алгоритм.
Алгоритм – это строгий порядок правил, которые определяют последовательность шагов обработки информации.
Ранее говорилось о том, что люди хотели создать машину, которая будет исполнять формальный алгоритм без помощи человека.
Для создания такой машины необходимо было выполнить некоторые условия: соответствие техническим требованиям; доскональное изучение работы алгоритма для обработки информации; разработка формализованного способа представления таких алгоритмов.
На этом уроке мы познакомимся с моделями алгоритмических машин в теории алгоритмов, а также вспомним свойства алгоритма.
Само понятие алгоритма исследовалось и совершенствовалось на протяжении многих лет. Но несмотря на все усилия, строгого определения понятия «алгоритм» не было. Поэтому начали появляться различные определения алгоритма. Но в тоже время все они были равнозначными.
Например, Андрей Николаевич Колмагоров, русский советский математик предложил следующее определение: алгоритм – это всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи.
А вот Андрей Андреевич Марков, советский математик, дал следующее определение для алгоритма. Алгоритм – это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату.
Несмотря на то, что было много вариаций определения алгоритма, все они сводились к одним и тем же требованиям:
· алгоритм должен содержать конечное количество простых для выполнения команд, то есть удовлетворять требованию конечности записи;
· алгоритм должен выполнять конечное количество шагов при решении задачи, то есть удовлетворять требованию конечности действий;
· алгоритм должен быть единым для всех допустимых исходных данных, то есть удовлетворять требованию универсальности;
· алгоритм должен приводить к правильному по отношению к поставленной задачи решению, то есть удовлетворять требование правильности.
В 1930-х гг. возникает новая наука – теория алгоритмов. Она занимается изучением алгоритмов. Главным толчком для этого была работа Курта Гёделя, австрийского логика, математика и философа математики.
Он сформулировал и доказал теоремы о неполноте. Его работы были опубликованы в 1931 году. В теореме о неполноте символических логик было показано, что некоторые математические проблемы не могут быть решены при помощи алгоритмов. Эта работа дала толчок к поиску и анализу различных формализаций алгоритма.
Основной вопрос, на который ищет ответ теория алгоритмов таков: для всякой ли задачи обработки информации может быть построен алгоритм решения? Для того, чтобы найти ответ на этот вопрос нужно было изначально договориться об исполнителе, на которого будет ориентирован алгоритм.
Алан Тьюринг, английский математик, логик, криптограф, предложил в качестве исполнителя машину Тьюринга.
Машина использовалась для расшифровки сообщений. На основе открытого текста (стандартные отрывки текста, значение которых известно аналитику), машина Тьюринга искала возможные настройки, использованные для шифрования сообщений. Она производила ряд логических предположений, основываясь на открытом тексте, а затем находила противоречия, отбрасывала набор параметров и переходила к следующему. Таким образом, большая часть всевозможных наборов отсеивалась и для более тщательного анализа оставалось всего несколько вариантов. В 1940 году была запущена такая первая машина.
В 1936–1937 годах американский математик и логик, Эмиль Пост описал другую модель алгоритмической машины. Она называется машиной Поста.
Можно сказать, что эта машина является более упрощённой версией машины Тьюринга. Работа машины Поста основана на двоичном алфавите. Поэтому она представляет для нас наибольший интерес, так как все компьютеры работают с двоичным алфавитом. Более подробно с этой машиной мы познакомимся чуть позже.
Язык программирования алгоритмических машин представляет собой описание конечного числа простых команд, которые могут быть реализованы в автоматическом устройстве.
Таким образом, система команд исполнителя (СКИ) – это совокупность всех команд языка исполнителя.
Алгоритм управления работой алгоритмической машины – это конечная последовательность команд, с помощью которой машина решает задачу обработки информации.
Для алгоритма управления такой машиной существуют свои требования:
· Дискретность. Этот пункт говорит о том, что исполнитель должен выполнять каждый шаг отдельно от других;
· Понятность. В алгоритме используются только команды СКИ, предназначенные конкретно для этого исполнителя;
· Точность. Каждая команда должна конкретно говорить о действии, которое должен выполнять исполнитель;
· Конечность. Для исполнителя должно быть задано определённое (конечное) число шагов, после выполнения которых должен получится искомый результат.
Рассмотрим пример. Нам необходимо записать алгоритм перемещения исполнителя Робот в клетку с домом. Данному исполнителю доступны три команды: вперёд, налево и направо.
Итак, наш алгоритм будет звучать следующим образом:
Ски что это в информатике
13.1 Используя информацию и иллюстративный материал, содержащийся в каталоге «Бурый медведь», создайте презентацию из трёх слайдов на тему «Бурый медведь». В презентации должны содержаться краткие иллюстрированные сведения о внешнем виде, об ареале обитания, образе жизни и рационе бурых медведей. Все слайды должны быть выполнены в едином стиле, каждый слайд должен быть озаглавлен.
13.2 Создайте в текстовом редакторе документ и напишите в нём следующий текст, точно воспроизведя всё оформление текста, имеющееся в образце.
Данный текст должен быть написан шрифтом размером 14 пунктов. Основной текст выровнен по ширине, и первая строка абзаца имеет отступ в 1 см. В тексте есть слова, выделенные жирным шрифтом, курсивом и подчеркиванием.
При этом допустимо, чтобы ширина Вашего текста отличалась от ширины текста в примере, поскольку ширина текста зависит от размера страницы и полей. В этом случае разбиение текста на строки должно соответствовать стандартной ширине абзаца.
Выполняя задание, обратите внимание на общие требования к оформлению текстовых документов и презентаций: памятка для учащихся.
13.1 Используя информацию и иллюстративный материал, содержащийся в каталоге «Пингвин», создайте презентацию из трёх слайдов на тему «Пингвин». В презентации должны содержаться краткие иллюстрированные сведения о внешнем виде, об ареале обитания, образе жизни и рационе пингвинов. Все слайды должны быть выполнены в едином стиле, каждый слайд должен быть озаглавлен.
13.2 Создайте в текстовом редакторе документ и напишите в нём следующий текст, точно воспроизведя всё оформление текста, имеющееся в образце.
Данный текст должен быть написан шрифтом размером 14 пунктов. Основной текст выровнен по ширине, и первая строка абзаца имеет отступ в 1 см. В тексте есть слова, выделенные жирным шрифтом, курсивом и подчеркиванием.
При этом допустимо, чтобы ширина Вашего текста отличалась от ширины текста в примере, поскольку ширина текста зависит от размера страницы и полей. В этом случае разбиение текста на строки должно соответствовать стандартной ширине абзаца.
Выполняя задание, обратите внимание на общие требования к оформлению текстовых документов и презентаций: памятка для учащихся.
13.1 Используя информацию и иллюстративный материал, содержащийся в каталоге «Орёл», создайте презентацию из трёх слайдов на тему «Орёл». В презентации должны содержаться краткие иллюстрированные сведения о внешнем виде, об ареале обитания, образе жизни и рационе орлов. Все слайды должны быть выполнены в едином стиле, каждый слайд должен быть озаглавлен.
13.2 Создайте в текстовом редакторе документ и напишите в нём следующий текст, точно воспроизведя всё оформление текста, имеющееся в образце.
Данный текст должен быть написан шрифтом размером 14 пунктов. Основной текст выровнен по ширине, и первая строка абзаца имеет отступ в 1 см. В тексте есть слова, выделенные жирным шрифтом, курсивом и подчеркиванием.
При этом допустимо, чтобы ширина Вашего текста отличалась от ширины текста в примере, поскольку ширина текста зависит от размера страницы и полей. В этом случае разбиение текста на строки должно соответствовать стандартной ширине абзаца.
Выполняя задание, обратите внимание на общие требования к оформлению текстовых документов и презентаций: памятка для учащихся.
13.1 Используя информацию и иллюстративный материал, содержащийся в каталоге «Благородный олень», создайте презентацию из трёх слайдов на тему «Благородный олень». В презентации должны содержаться краткие иллюстрированные сведения о внешнем виде, об ареале обитания, образе жизни и рационе благородных оленей. Все слайды должны быть выполнены в едином стиле, каждый слайд должен быть озаглавлен.
13.2 Создайте в текстовом редакторе документ и напишите в нём следующий текст, точно воспроизведя всё оформление текста, имеющееся в образце.
Данный текст должен быть написан шрифтом размером 14 пунктов. Основной текст выровнен по ширине, и первая строка абзаца имеет отступ в 1 см. В тексте есть слова, выделенные жирным шрифтом, курсивом и подчеркиванием.
При этом допустимо, чтобы ширина Вашего текста отличалась от ширины текста в примере, поскольку ширина текста зависит от размера страницы и полей. В этом случае разбиение текста на строки должно соответствовать стандартной ширине абзаца.
Выполняя задание, обратите внимание на общие требования к оформлению текстовых документов и презентаций: памятка для учащихся.
