Что такое однозначность в информатике
Свойства алгоритма
К алгоритму решения задач предъявляются высокие требования. Он должен обладать дискретностью, массовостью, компактностью, детерминированностью и результативностью.
Дискретность алгоритма определяет то, что всякий алгоритм имеет прерывистый, дискретный характер, т.е. представляет собой последовательность выполненных один за другим отдельно законченных шагов.
Массовостью алгоритма называется его способность быть пригодным для решения широкого класса задач данного типа. Алгоритм должен составляться не для решения отдельно взятой проблемы (задачи), а для создания возможности решения всех типов подобных проблем.
Детерминированность (определенность) алгоритма – это строгая определенность (однозначность предписываемых действий в каждой инструкции алгоритма), конкретность, чтобы в его записи не оставалось место двусмысленности и произвольному толкованию.
Результативностьюалгоритма называется свойство обеспечения нужного результата за конечное число шагов, если данные принадлежат области исходных данных, которыми определена массовость алгоритма.
Конечность определяет, что каждое действие в отдельности и алгоритм в целом должны иметь возможность завершения.
Понятность алгоритма – это обязательность составления алгоритма учетом системы команд исполнителя, т.е. алгоритм должен быть зафиксирован в той форме, которая будет понятна исполнителю. Значения всех приведенных действий в алгоритме должны быть ясными, точными и определенными.
Компактностью алгоритма называется его краткость, свойство минимальности инструкций. Наиболее удачно составленным алгоритмом считается алгоритм, обладающий компактностью и минимальностью количества вычислений при обязательной массовости алгоритма.
Каждый исполнитель должен однозначно понимать правило выполнения каждого действия алгоритма. Это называется свойством однозначности алгоритма.
Урок информатики по теме «Алгоритм. Свойства алгоритма». 9-й класс
Класс: 9
В течение всей жизни каждый человек постоянно пользуется набором всевозможных алгоритмов — правил, которые заложены природой, даны воспитанием, обучением, тренировкой, выработаны на основе собственного опыта. Инструкции, в которых указано, как пользоваться лифтом, телефоном, различными автоматами и бытовыми приборами, правила перехода улицы, оказания первой медицинской помощи, распорядок дня, кулинарные рецепты, порядок проведения химического опыта, правила вычислений, методы решения алгебраических и геометрических задач — все это можно считать алгоритмами. Таким образом, все мы живем в мире алгоритмов. Алгоритмы экономят силы и время человека, так как однажды усвоенным правилом (алгоритмом) он может пользоваться всю жизнь.
Приведите пример алгоритма перехода дороги с светофором, и без светофора.
Ваш мозг постоянно занят работой, поиском решений. Говорят, что человек составляет алгоритм.
Тема нашего сегодняшнего урока. Алгоритм. Свойства алгоритма.
В природе все взаимосвязано, все на все влияет и все зависит друг от друга. Складываются сложные цепочки событий. Если вынуть хоть одно звено, вся цепочка разорвется.
Как вы думаете, что будет если убрать из рецепта вторую команду? А четвертую?
Надо научится выстраивать в нужном порядке все звенья какой-нибудь жизненной или математической задачи. Эти умения нужны и при обработке информации. Информацию следует обрабатывать по определенным правилам, которые выполняются в определенном порядке.
Итак, давайте с вами, попробуем дать определения понятию алгоритм.
Учащиеся формулируют и записывают с доски.
Алгоритм – понятное и точное предписание исполнителю совершить последовательность действий, направленных на достижение указанной цели или на решение поставленной задачи.
Учащиеся записывают в тетрадь определение.
В своих трудах по арифметике и алгебре он разработал, в частности, правила выполнения четырех арифметических операций над многозначными десятичными числами. Эти правила определяют последовательность действий, которые необходимо выполнить, чтобы получить сумму чисел, произведение и т. д. Почти в таком же виде эти правила изучаются всеми школьниками в начальных классах.
Латинский перевод книги начинается словами «Dixit Algorizmi» (сказал Алгоризми). Так как сочинение об арифметике было очень популярно в Европе, имя автора (Algorizmi или Algorizmus) стало нарицательным и средневековые математики так называли арифметику, основанную на десятичной позиционной системе счисления. Позднее европейские математики стали называть так всякую систему вычислений по определенному правилу. В настоящее время термин «алгоритм» означает набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное число действий.
Затем понятие алгоритма переместилось в область логики, где появилась теория алгоритмов, изучавшая процесс доказательств или разрешимость и неразрешимость математических задач. В 1937 году, когда английский математик Алан Тьюринг доказал теоретически возможность построения устройства, осуществляющего алгоритм. Такое абстрактное устройство получило название МАШИНА ТЬЮРИНГА. Аналогичный, но более простой исполнитель алгоритма – МАШИНА ПОСТА. Когда же были созданы первые ЭВМ, понятие алгоритма и теория алгоритмов переместились в новую науку, связанную с этими вычислительными устройствами – информатику.
Приведите примеры алгоритмов.
А теперь скажите кто может выполнить данный алгоритм?
Приведите пример алгоритмов с разными исполнителями.
Получается, всякий алгоритм составляется в расчете на определенного исполнителя. Им может быть человек, робот, компьютер и др. Чтобы составить алгоритм для исполнителя, нужно знать, какие команды исполнитель может понять и исполнить, а какие нет.
Исполнитель – объект, который будет выполнять алгоритм.
Приведите примеры исполнителей и что они могут делать.
В классе исполнителей выделяют два типа: формальные, неформальные. Формальный исполнитель одну и ту же команду всегда выполнит одинаково, неформальный может выполнять команду по-разному. Неформальный исполнитель – человек, формальный – технические устройства.
У каждого исполнителя можно выделить: среду исполнителя, систему команд исполнителя, систему отказов.
Среда – обстановка, в которой работает исполнитель.
Система команд исполнителя (СКИ) – совокупность команд, которую исполнитель умеет выполнять.
Система отказов – ситуации сбоя работы исполнителя, которые возникают, если команда вызывается пpи недопустимом для нее состоянии сpеды («не понимаю», «не могу»).
«Не понимаю» – возникает тогда, когда исполнителю дается команда не входящая в его СКИ, «не могу» – когда команда из СКИ не может быть выполнена в конкретных условиях среды.
Укажите для данных примеров среду, ски, систему отказов.
Свойства алгоритмов
1. Как мы уже знаем, алгоритм задает полную последовательность действий, которые необходимо выполнять для решения задачи. При этом, как правило, для выполнения этих действий их расчленяют (разбивают) в определенной последовательности на простые шаги. Возникает упорядоченная запись совокупности четко разделенных предписаний (директив, команд), образующих прерывную (или, как говорят, дискретную) структуру алгоритма. Выполнить действия следующего предписания можно лишь выполнив действия предыдущего.
Под ДИСКРЕТНОСТЬЮ понимают возможность разбиения алгоритма на отдельные элементарные действия, выполнение которых человеком или машиной не вызывает сомнения.
Пример по алгоритму заваривая чая
2. Чтобы исполнитель сумел решить поставленную перед ним задачу, используя алгоритм, он должен уметь выполнить каждое его указание. Иными словами, он должен понимать суть управления. То есть при составлении алгоритма нужно обязательно учитывать «правила игры», т.е. систему предписаний (или систему команд), которые понимает ЭВМ. Мы будем говорить в данном случае о «понятности» алгоритма.
Под «ПОНЯТНОСТЬЮ» алгоритмов понимают указания, которые понятны исполнителю.
Пример по пришиванию пуговицы.
3. Будучи понятным, алгоритм не должен все же содержать предписаний, смысл которых может восприниматься неоднозначно. Этими свойствами часто не обладают предписания и инструкции, которые составляются для людей.
Например, вспомним известную всем притчу о царской воле. Царь приказал подчиненным выполнить такой указ: «Казнить нельзя помиловать». Он забыл в указе поставить запятую, а подчиненные не знали, что им делать. Указание «казнить нельзя, помиловать» и «казнить, нельзя помиловать» задают совсем разные действия, от которых зависит жизнь человека.
Кроме того, в алгоритмах недопустимы такие ситуации, когда после выполнения очередного предписания алгоритма исполнителю неясно, какое из них должно выполняться на следующем шаге.
Под ОДНОЗНАЧНОСТЬЮ алгоритмов понимается единственность толкования правил выполнения действий и порядка их выполнения.
Пример, фрагмент мультфильма «Стран невыученных уроков».
4. Очень важно, чтобы составленный алгоритм обеспечивал решение не одной частной задачи, а мог выполнять решение широкого класса задач данного типа.
Алгоритм можно использовать для любого квадратного у равнения. Такой алгоритм будет МАССОВЫЙ.
Пример с чайниками, обогревателями.
5. Под КОНЕЧНОСТЬЮ алгоритмов понимают завершение работы алгоритма в целом за конечное число шагов.
Пример с ловлей рыбы.
6. Еще к желательным свойствам алгоритмов нужно отнести РЕЗУЛЬТАТИВНОСТЬ, она предполагает, что выполнение алгоритмов должно завершаться получением определенных результатов.
Подобные ситуации в информатике возникают, когда какие-либо действия невозможно выполнить. В математике такие ситуации называют неопределенностью. Например, деление числа на ноль, извлечение квадратного корня из отрицательного числа, да и само понятие бесконечности неопределенно. Поэтому, если алгоритм задает бесконечную последовательность действий, то в этом случае он также считается результатом неопределенным.
Но можно действовать по-другому. А именно: указать причину неопределенного результата. В таком случае, пояснения типа «на ноль делить нельзя», «компьютер выполнить такое не в состоянии» и т.п. можно считать результатом выполнение алгоритма.
Таким образом, свойство результативности состоит в том, что во всех» случаях можно указать, что мы понимаем под результатом выполнения алгоритма.
Пример с нахождением стрелы Ивана Царевича у лягушки.
7. И последнее общее свойство алгоритмов – их правильность.
Мы говорим, что алгоритм ПРАВИЛЬНЫЙ, если его выполнение дает правильные результаты решения поставленных задач.
Соответственно мы говорим, что алгоритм СОДЕРЖИТ ОШИБКИ, если можно указать такие допустимые исходные данные или условия, при которых выполнение алгоритма либо не завершится вообще, либо не будет получено никаких результатов, либо полученные результаты окажутся неправильными.
Пример с арифметическим выражением.
Вывод:
Учащиеся записывают в тетрадь свойства.
Решение задач на определение свойств. Обсуждение свойств с классом.
Задание 1.
Определить какое свойство алгоритма, не выполняется в данной инструкции и какие изменения необходимо внести, чтобы получился алгоритм.
Инструкция по варке манной каши
Молоко вскипятить добавить соль, сахар, засыпать тонкой струйкой, непрерывно помешивая манную крупу, довести до кипения, прокипятить минут 5-7, добавить масло и дать остыть.
Нет понятности: какое количество (в граммах) брать продуктов.
Задание 2.
Определить какое свойство алгоритма, не выполняется в данной инструкции и какие изменения необходимо внести, чтобы получился алгоритм.
Нет результативности. Что делать в том случае, если А=В?
Задание 3.
Нет конечности. Что делать в том случае, когда доски закончились?
Практическая работа в парах (5 мин.)
Задание 1. Исправьте алгоритм «Получения кипятка», чтобы предотвратить несчастный случай.
Задание 2. Используя представленные команды, составить алгоритм покраски мяча
Задание 3. Составить инструкцию, в которой не выполняется хотя бы одно свойство алгоритма. Записать какие изменения нужно в нее внести, чтобы получить алгоритм.
Тест самопроверкой (5 мин.)
А) Указание на выполнение действий,
Б) Система правил, описывающая последовательность действий, которые необходимо выполнить для решения задачи,
В) Процесс выполнения вычислений, приводящих к решению задачи
2. Свойство алгоритма – дискретность, выражает, что:
А) Команды должны следовать последовательно друг за другом,
Б) Каждая команда должна быть описана в расчете на конкретного исполнителя,
В) Разбиение алгоритма на конечное число команд
3. Среда исполнителя – это:
А) Обстановка, в которой работает исполнитель.
Б) Объект, который будет выполнять алгоритм
В) Совокупность команд, которую исполнитель умеет выполнять.
4. В расчете на кого должен строиться алгоритм:
А) В расчете на ЭВМ,
Б) В расчете на умственные способности товарища,
В) В расчете на конкретного исполнителя
5. Какое из перечисленных свойств относится к свойствам алгоритма:
А) Визуальность,
Б) Совокупность,
В) Понятность
6. Исполнитель «человек» – это
А) Формальный исполнитель
Б) Неформальный исполнитель
В) Нормальный исполнитель
Подведение итогов (5 мин.)
Домашнее задание:
1. Выучить теоретический материал
2. Привести 3 примера алгоритмов для различных исполнителей.
3. Составить 2 инструкции, в которых не выполняется хотя бы одно свойство алгоритма. Записать какие изменения нужно в них внести, чтобы получить алгоритм.
Что такое однозначность в информатике
4.3. основные свойства алгоритмов
Алгоритм относится к фундаментальным понятиям информатики. На понятии алгоритма построены все основные принципы программирования — составления программ для вычислительных машин.
Алгоритм — это совокупность действий со строго определенными правилами выполнения. В информатике изучаются различного рода алгоритмы — диалоговые алгоритмы, алгоритмы обработки данных, вычислительные алгоритмы, алгоритмы управления роботами, станками и другими техническими устройствами.
Пример диалогового алгоритма:
Для описания алгоритмов используются блок-схемы, изображенные справа, или структурированная запись, приведенная слева. Достоинство блок-схемы — ее безусловная наглядность, очаровывающая новичков и учителей.
Однако блок-схемы приходится рисовать, а не записывать. Самое неприятное — внесение изменений и исправлений в блок-схемы, требующее перерисовки рамок и стрелок, а иногда и всей блок-схемы в целом.
Еще более сложно искать ошибки в запутанных блок-схемах, напоминающих блюдо из спагетти. И в то же время блок-схемы до сих пор требуются отечественными стандартами документирования программ.
Достоинство структурированной записи алгоритмов заключается в простоте их чтения и ввода с экрана ЭВМ. По форме они могут просто совпадать сзаписью программ, а разница между ними в том, что алгоритмы записываются на родном языке, понятном широкому кругу людей, а программы — на языке программирования, понятном компьютерам.
Следующее достоинство структурированной записи — простота внесения исправлений и изменений с использованием даже простейших редакторов текстов. По этим причинам за рубежом блок-схемы уже давно не используются ни для документирования, ни для обучения, а все современные языки программирования построены на принципах структурной записи текстов.
Приведем примеры описания алгоритма и программы в структурированной записи:
алг «приветствие» ‘ приветствие
запрос(«Ваше uмя=»,NN) input «Ваше имя=»,NN$
вывод(«Добрый дeнь»,NN) print «Добрый дeнь»,NN$
Алгоритм, приведенный слева, записан на псевдокоде. Псевдокод — это язык записи структурированных алгоритмов в качестве документации к программам для ЭВМ. Особенность псевдокода заключается в том, что описания на нем выполняются на родном языке — русском, английском, украинском, казахском, немецком и т. п.
Программа, приведенная справа, записана на языке Бейсик — языке программирования персональных ЭВМ. Языками программирования называются формализованные языки, используемые для записи программ на ЭВМ. Одним из них является язык Бейсик.
Достоинство псевдокода заключается в том, что описание алгоритмов на родном языке намного проще читать и понимать, чем запись программ на языке с иностранной лексикой. По этим причинам псевдокод используется как основное средство документирования программ во всех ведущих фирмах, занимающихся разработкой программ.
С точки зрения информатики алгоритмы, записанные в такой обобщенной записи, позволяют выразить общую логику работы программ независимо от используемых языков программирования и типов ЭВМ. При этом алгоритмы, записанные в такой обобщенной форме, могут быть реализованы с помощью различных языков программирования для самых различных типов ЭВМ.
В качестве примера приведем реализацию этого же диалогового алгоритма на самой ранней версии языка Бейсик, использовавшегося на самых первых персональных компьютерах:
алг «приветствие» 10 ‘ приветствие
запрос(«Ваше uмя=»,NN) 30 input «Ваше имя=», NN$
вывод(«Добрый день»,NN) 40 print «Добрый день»,NN$
Основные свойства алгоритмов и программ для вычислительных машин — однозначность, результативность, правильность и массовость. Этими свойствами алгоритмы отличаются от различного рода расплывчатых и неоднозначных предписаний, инструкций и кулинарных рецептов, которые могут толковаться и исполняться многими способами.
Однозначность алгоритмов — это однозначность правил их выполнения. Следствием этого свойства алгоритмов является однозначность результатов их выполнения в одинаковых начальных условиях. Это не всегда верно для кулинарных рецептов, когда разные исполнители в одних и тех же условиях могут придавать различный вкус и пикантность одним и тем же блюдам.
Результативность — это завершение выполнения алгоритмов определенными результатами. Результативность — наиболее важное свойство алгоритмов и программ, предназначенных для решения прикладных задач. Алгоритмы и программы, не дающие результатов или ведущие к сбоям и отказам, никому не нужны.
Массовость — это возможность применения алгоритмов в различных конкретных исходных условиях. Массовые алгоритмы особенно важны для решения прикладных задач, когда алгоритмы и программы должны обеспечить решение целого класса задач, различающихся исходными данными.
Правильность алгоритмов определяется-правильностью результатов, получаемых с их помощью. По этой причине правильность алгоритмов и программ является относительным понятием. Оценка правильности может проводиться только при наличии требований к конечным результатам.
Алгоритм считается правильным, если он дает правильные результаты при любых допустимых начальных условиях. Правильность алгоритмов гарантирует правильность результатов их выполнения.
Алгоритм содержит ошибки, если его выполнение может привести к отказам, сбоям или неправильным результатам либо вовсе не дает никаких результатов. Эти ошибки называются алгоритмическими. Алгоритмы и программы, содержащие такие ошибки, могут нанести вред или ущерб тем, кто захочет ими воспользоваться.
Для оценки правильности алгоритмов и программ необходимо уметь оценивать результаты выполнения составляющих их действий и конечные результаты их выполнения в целом.
Простейший вид машинных операций — операции присваивания. С помощью присваиваний в алгоритмах описываются вычисления в программах для ЭВМ. Рассмотрим примеры операций присваивания и описания результатов их выполнения.
Запись присваиваний читается:
а := 0 — «переменной а присвоить значение 0»;
b := b+1 — «переменной b присвоить значение b+1».
Записи в колонке результатов читаются так:
а = 0 — «значение а равно 0»;
b’ = b+1 — «значение b’ равно b+1».
Здесь а и b — программные переменные — область машинной памяти, в которой хранятся их значения а и b. В отличие от обычных математических переменных программные переменные могут получать новые значения. В частности, присваивание b := b+1 записывает в программную переменную b новое значение b’, равное величине b+1, где b — прежнее значение переменной b.
Для описания результатов выполнения алгоритмов и программ могут и должны использоваться спецификации. Спецификации — это точные, математически строгие описания. Примерами спецификаций могут служить сценарии диалоговых программ.
Сценарии диалоговых алгоритмов и программ — это совокупность текстов, картинок и сообщений, появляющихся на экранах ЭВМ. Рассмотрим в качестве примера сценарий алгоритма рисования домика на экране ЭВМ.
Решение — следующие алгоритм и программа, результатом работы которых должен быть приведенный выше рисунок:
Однако результатом выполнения приведенных алгоритма и программы будет следующий рисунок:
Причиной того, что на этом рисунке крыша «поехала» влево, являются алгоритмические ошибки — неправильный расчет координат крыши в алгоритме, из-за чего составленная программа дает не тот рисунок, который указан в сценарии.
Примером прикладного алгоритма и программы может служить следующий алгоритм расчета прибыли:
алг «расчет прибыли» ‘ расчет прибыли
запрос («доходы =»,d) input «доходы =»,d
запрос («расходы =»,r) input «расходы=»,r
вывод («прибыль =», р) print «прибыль =», р
Сценарий диалога Протокол диалога
доходы =? доходы =? 1000
расходы =? расходы =? 700
прибыль = прибыль = 300
Для проверки правильности алгоритма и программы необходима постановка задачи. Приведем строгую постановку решаемой задачи.
Задача: расчет прибыли.
Для оценки правильности полученных результатов нужно сверить расходы и прибыль с доходами. В нашем случае это должно быть 700 + 300 = 1000, что выражает правильный конечный результат при указанных данных.
Для оценки правильности алгоритма и программы в целом необходимо рассмотреть конечные результаты их выполнения при произвольных значениях данных d и r. Вычисляемая величина р по алгоритму будет равна:
Подставляя в условие постановки задачи это значение, получаем:
d = r + p = r + (d— r) = d — верное тождество.
Таким образом, при любых значениях исходных данных результаты выполнения приведенного алгоритма будут правильными.
1. Что такое алгоритм?
2. Каковы основные виды алгоритмов?
3. Что такое однозначность алгоритмов?
4. Что такое результативность алгоритмов?
5. Что такое правильность алгоритмов?
6. Что такое массовость алгоритмов?
7. Что такое алгоритмические ошибки?
1. Составьте сценарий, алгоритм и программу:
а) поздравления с Новым годом;
б) поздравления с Днем рождения;
в) регистрации даты рождения;
г) регистрации фамилии и имени.
2. Составьте сценарий диалога, алгоритм и программу:
а) расчета сдачи за товар;
б) расчета остатка от прибыли;
в) пересчета рубль/доллар;
г) расчета остатка времени до 18.00.
3. Составьте сценарий, алгоритм и программу вычислений:
а) времени движения по длине пути и скорости;
б) длины пути по времени и скорости движения;
в) средней скорости по времени и длине пути.
4. Составьте картинки, алгоритмы и программу рисования:
а) российского флага; г) украинского флага;
б) шведского флага; д) французского флага;
в) японского флага; е) британского флага.
5. Составьте сценарий, алгоритмы и программу на Бейсике вывода изображений:
а) яхты; д) автомобиля;
б) трактора; е) усадьбы;
Содержание
Читать: Аннотация
Читать: Введение
Читать: Глава 1. информация и персональные эвм
Читать: 1.1. введение в информатикуЧитать: 1.2. персональные компьютерыЧитать: 1.3. работа на персональных эвмЧитать: 1.4. редактирование текстов на эвмЧитать: 1.5. обучение с помощью эвм
Читать: Глава 2. элементы интернет-технологийЧитать: 2.1. работа в сети интернетЧитать: 2.2. поиск информации в интернетЧитать: 2.3. электронная почтаЧитать: 2.4. создание сайтов в интернетЧитать: 2.5. электронная коммерция
Читать: Глава 3. элементы информационных технологийЧитать: 3.1. базы данных на эвмЧитать: 3.2. элементы математической логикиЧитать: 3.3. принципы логического выводаЧитать: 3.4. базы знаний на эвмЧитать: 3.5. законы логического вывода
Читать: Глава 4. решение задач на эвмЧитать: 4.1. выполнение расчетов на эвмЧитать: 4.2. постановка и решение задачЧитать: 4.3. основные свойства алгоритмовЧитать: 4.4. базовые средства программированияЧитать: 4.5. основы структурного программированияЧитать: 4.6. основы безошибочного программированияЧитать: 4.7. средства обработки данных
Читать: Глава 5. технология решения задач Читать: 5.1. решение задач на эвмЧитать: 5.2. анализ правильности алгоритмовЧитать: 5.3. решение прикладных задачЧитать: 5.4. элементы доказательного программированияЧитать: 5.5. решение сложных задач
Читать: Глава 6. экзамены по информатикеЧитать: 6.1. экзамены и зачеты по информатикеЧитать: 6.2. решение экзаменационных задачЧитать: 6.3. проверка программ на эвмЧитать: 6.4. олимпиадные задачи по информатикеЧитать: 6.5. технология дистанционного обучения
Читать: Приложение
Читать: Интерпретатор языка прологЧитать: 1. назначение интерпретатора прологаЧитать: 2. запуск интерпретатора прологаЧитать: 3. диалог с программами на прологеЧитать: 4. ввод и редактирование программЧитать: 5. операции с файламиЧитать: 6. краткое описание языка пролог
Читать: Толковый словарь
Читать: Список рекомендуемой литературы