Какое свойство алгоритма называется дискретность

I. Дискретность

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

II. Определённость

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

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

Формальному исполнителю здесь неясно, требуется ли трясти смесь, пока она вся не станет комом, и какой всё-таки величины кастрюля. Большая или маленькая? И до какой температуры надо подогреть коньяк. Так что такой алгоритм любому исполнителю выполнить довольно трудно, практически невозможно. Можно сказать, что в алгоритме не должны присутствовать не определённые слова: немного, чуть-чуть, слегка и т. д.

III. Результативность

Третье свойство — результативность алгоритма. Это свойство подразумевает, что каждый шаг (и алгоритм в целом) после своего завершения даёт среду, в которой все имеющиеся объекты однозначно определены. Если это по каким — либо причинам невозможно, то алгоритм должен сообщать, что решение задачи не существует.

К примеру, в инструкции по применению лекарства от кашля сказано:
Если врач не прописал, то принимать 3-4 раза в день по 15-20 капель, лучше всего в горячей сладкой воде.
Здесь не определено, например, когда должен заканчиваться алгоритм — когда кашель пройдет или когда лекарство закончиться. Свойство результативности обычно подразумевает конечность алгоритма, т. е. завершение его работы за конечное число шагов (при этом количество шагов может быть заранее не известным и различным для разных исходных данных) .

IV. Понятность

Надо сказать, что алгоритм должен быть понятен не только автору, но и исполнителю. Если мы предложим исполнителю, например утюгу постирать одежду, то он никогда этого не сделает, потому, что не поймет, т. к. такой программы в нём не заложено. Или, например, если мы предложим какому-нибудь мальчику испечь торт то у него, как правило, ни чего не получится, потому что этого они делать не умеют. Но если мы составим подробный алгоритм работы, разобьем его на элементарные шаги, такие, что он без труда поймёт и сможет выполнить каждый шаг, то он сможет успешно испечь любой торт. Каждый шаг алгоритма обязательно представляет собой какое-либо допустимое действие исполнителя. Это свойство алгоритма называют понятностью.

V. Массовость

Наконец, еще одно свойство алгоритма — массовость. Оно означает, что имеется некоторое множество данных, которые могут обрабатываться алгоритмом, или данный алгоритм может быть применен для решения любой задачи одного типа. Массовость алгоритма тесно связанна с понятностью, в качестве примера можно разобрать пример с тортом, и сказать, что чем подробнее будет описан алгоритм приготовления, тем больше вероятности, что торт будет испечен. Также в качестве примера можно взять руководство по эксплуатации электрических приборов, инструкции и т. д. , чем полнее изложен алгоритм работы с приборами, тем легче нам с вами будет в нем разобраться. С точки зрения практической ценность алгоритмов важно, что бы множество допустимых исходных данных было достаточно большим, как правило, практическая ценность алгоритма не велика, если его можно использовать только один раз.

Источник

Понятие алгоритма.
Свойства алгоритма.

Исполнители алгоритмов (назначение, среда, режим работы, система команд).

Компьютер как формальный исполнитель алгоритмов (программ).

Цель урока:

Дать понятие алгоритму и его свойствам.
Воспитание умения слушать учителя.
Развитие познавательного интереса.

План урока:

Постановка цели урока.
Проверка домашнего задания.
Объяснение нового материала.
Примеры алгоритмов.
Домашняя работа.
Подведение итогов урока.

Ход урока

I. Организация начала урока.

II. Актуализация знаний.

III. Постановка целей и задач.

IV. Объяснение нового материала.

V. Закрепление изученного на уроке.

VI. Информация о домашнем задании.

VII. Подведение итогов урока.

Объяснение нового материала.

Появление алгоритмов связывают с зарождением математики. Более 1000 лет назад (в 825 году) ученый из города Хорезма Абдулла (или Абу Джафар) Мухаммед бен Муса аль-Хорезми создал книгу по математике, в которой описал способы выполнения арифметических действий над многозначными числами. Само слово алгоритм возникло в Европе после перевода на латынь книги этого математика.

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

Вы постоянно сталкиваетесь с этим понятием в различных сферах деятельности человека (кулинарные книги, инструкции по использованию различных приборов, правила решения математических задач…). Обычно мы выполняем привычные действия не задумываясь, механически. Например, вы хорошо знаете, как открывать ключом дверь. Однако, чтобы научить этому малыша, придется четко разъяснить и сами эти действия и порядок их выполнения:

1. Достать ключ из кармана.
2. Вставить ключ в замочную скважину.
3. Повернуть ключ два раза против часовой стрелки.
4. Вынуть ключ.

Если вы внимательно оглянитесь вокруг, то обнаружите множество алгоритмов которые мы с вами постоянно выполняем. Мир алгоритмов очень разнообразен. Несмотря на это, удается выделить общие свойства, которыми обладает любой алгоритм.

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

1. Дискретность (алгоритм должен состоять из конкретных действий, следующих в определенном порядке);
2. Детерминированность (любое действие должно быть строго и недвусмысленно определено в каждом случае);
3. Конечность (каждое действие и алгоритм в целом должны иметь возможность завершения);
4. Массовость (один и тот же алгоритм можно использовать с разными исходными данными);
5. Результативность (отсутствие ошибок, алгоритм должен приводить к правильному результату для всех допустимых входных значениях).

Виды алгоритмов:

1. Линейный алгоритм (описание действий, которые выполняются однократно в заданном порядке);
2. Циклический алгоритм (описание действий, которые должны повторятся указанное число раз или пока не выполнено задание);
3. Разветвляющий алгоритм (алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий)
4. Вспомогательный алгоритм (алгоритм, который можно использовать в других алгоритмах, указав только его имя).

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

Стадии создания алгоритма:

1. Алгоритм должен быть представлен в форме, понятной человеку, который его разрабатывает.
2. Алгоритм должен быть представлен в форме, понятной тому объекту (в том числе и человеку), который будет выполнять описанные в алгоритме действия.

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

Исполнитель — объект, который выполняет алгоритм.

Идеальными исполнителями являются машины, роботы, компьютеры…

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

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

Компьютер – автоматический исполнитель алгоритмов.

Алгоритм, записанный на «понятном» компьютеру языке программирования, называется программой.

Программирование — процесс составления программы для компьютера. Для первых ЭВМ программы записывались в виде последовательности элементарных операций. Это была очень трудоемкая и неэффективная работа. Поэтому в последствии были разработанные специальные языки программирования. В настоящее время существует множество искусственных языков для составления программ. Однако, так и не удалось создать идеальный язык, который бы устроил бы всех.

Алгоритм называется линейным, если все его действия выполняются последовательно друг за другом от начала и до конца.

Пример №1.

Составьте алгоритм вычисления выражения

у=2х+в, х=5, в=5. На языке блок-схем:

На естественном языке:

1.х=5

2. В=5

3.у=2х+в

4. Напечатать у

Решение задач ЕГЭ А8

a = 9876
b = (a div 1000)*5 mod 10
a = (b*10)+a div 100

{div и mod – операции, вычисляющие результат деления нацело первого аргумента на второй и остаток от деления соответственно}

a = 9876
b = mod(div(a,1000)*5, 10)

a = (b*10)+div(a,100)

|div и mod – функции, вычисляющие результат деления нацело первого аргумента на второй и остаток от деления соответственно

a = 148, b = 5

a = 148, b = 16

a = 4, b = 148

a = 5, b = 45

Например, дано 2348 (mod или div) 100. Делим 2348 на 100. Получаем 23,48.
Справа от запятой mod,
слева div.
Приоритеты операций: *, /, DIV, MOD, +, -.

23, 48

divmod

Закрепление изученного на уроке.

b:= (adiv 10) + 14;
a:= (bmod 10) + 2;
{div и mod – операции, вычисляющие результат деления нацело первого аргумента на второй и остаток от деления соответственно}

a:= 3 + 8*4
b:= div(a,10) + 14
a:= mod(b, 10) + 2
|div и mod – функции, вычисляющие результат деления нацело первого аргумента на второй и остаток от деления соответственно

Информация о домашнем задании.

§ 4.1 ; 4.2
Вопросы в конце параграфа

Подведение итогов урока.

Литература

Н.Д.Угринович «Информатика и ИКТ» для 11 класса
Л.З. Шауцукова Л.З. «Информатика» для 10-11класса
Материалы сайта: https://www.alleng.ru
А.Г. Гейн, А.И. Сенокосов, Н.А. Юнерман «Информатика»

Источник

ПОНЯТИЕ АЛГОРИТМА.
СВОЙСТВА АЛГОРИТМА. ВИДЫ АЛГОРИТМОВ. СПОСОБЫ ОПИСАНИЯ АЛГОРИТМОВ

Алгоритмом называется
точное и понятное предписаниe исполнителю совершить последовательность
действий, направленных на решение поставленной задачи. Слово «алгоритм»
происходит от имени математика Аль Хорезми, который сформулировал правила
выполнения арифметических действий. Первоначально под алгоритмом понимали
только правила выполнения четырех арифметических действий над числами.
В дальнейшем это понятие стали использовать вообще для обозначения последовательности
действий, приводящих к решению любой поставленной задачи. Говоря об алгоритме
вычислительного процесса, необходимо понимать, что объектами, к которым
применялся алгоритм, являются данные. Алгоритм решения вычислительной
задачи представляет собой совокупность правил преобразования исходных
данных в результатные.

Основными свойствами
алгоритма являются:

детерминированность
(определенность). Предполагает получение однозначного результата вычислительного
процecca при заданных исходных данных. Благодаря этому свойству процесс
выполнения алгоритма носит механический характер;
результативность.
Указывает на наличие таких исходных данных, для которых реализуемый
по заданному алгоритму вычислительный процесс должен через конечное
число шагов остановиться и выдать искомый результат;
массовость. Это
свойство предполагает, что алгоритм должен быть пригоден для решения
всех задач данного типа;
дискретность.
Означает расчлененность определяемого алгоритмом вычислительного процесса
на отдельные этапы, возможность выполнения которых исполнителем (компьютером)
не вызывает сомнений.

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

Наибольшее распространение
благодаря своей наглядности получил графический (блок-схемный) способ
записи алгоритмов.

Блок-схемой
называется графическое изображение логической структуры алгоритма, в котором
каждый этап процесса обработки информации представляется в виде геометрических
символов (блоков), имеющих определенную конфигурацию в зависимости от
характера выполняемых операций. Перечень символов, их наименование, отображаемые
ими функции, форма и размеры определяются ГОСТами.

При всем многообразии
алгоритмов решения задач в них можно выделить три основных вида вычислительных
процессов:

линейный;
ветвящийся;
циклический.

Линейным
называется такой вычислительный процесс, при котором все этапы решения
задачи выполняются в естественном порядке следования записи этих этапов.

Ветвящимся
называется такой вычислительный процесс, в котором выбор направления обработки
информации зависит от исходных или промежуточных данных (от результатов
проверки выполнения какого-либо логического условия).

Циклом называется
многократно повторяемый участок вычислений. Вычислительный процесс, содержащий
один или несколько циклов, называется циклическим.
По количеству выполнения циклы делятся на циклы с определенным (заранее
заданным) числом повторений и циклы с неопределенным числом повторений.
Количество повторений последних зависит от соблюдения некоторого условия,
задающего необходимость выполнения цикла. При этом условие может проверяться
в начале цикла — тогда речь идет о цикле с предусловием, или в конце —
тогда это цикл с постусловием.

Источник

Понятие алгоритма – одно из фундаментальных понятий информатики. Алгоритмы являются предметом изучения такой научной дисциплины, как «Теория алгоритмов». Однако при решении практических задач, как правило, не опираются на высокую формализацию данного понятия и ограничиваются содержательным толкованием сущности понятия алгоритма.
Под алгоритмом понимается понятное и точное предписание исполнителю совершить последовательность действий, направленных на достижение поставленной цели

Фрагменты из сказок «Сказка про Федота-стрельца» и «Перышко Финиста ясна сокола» содержат предписание определенному исполнителю, но эти предписания не являются точными.

Фрагмент из сказки об Иване-царевиче и сером волке содержит не предписание, а констатацию того, что произойдет в том или ином случае.

Фрагмент из сказки «Царевна-лягушка» задает понятное и точное предписание детям царя совершить определенные действия для решения вопроса о женитьбе.

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

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

Результативность также является свойством алгоритма. Смысл этого свойства состоит в том, что процесс выполнении алгоритма должен прекратиться за конечное число шагов и при этом должен получиться определенный результат. Вывод о том, что решения не существует, тоже результат.

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

Установите соответствие между характеристиками и названиями языков программирования.
1. Язык, предназначенный для представления в символической форме программ, записанных на машинном языке; позволяющий программисту пользоваться мнемоническими кодами операций, по своему усмотрению присваивать символические имена регистрам ЭВМ и ячейкам памяти, а также задавать наиболее удобные в том или ином контексте схемы адресации.
2. Многоцелевой простой язык символических инструкций для начинающих, разработанный в 1964 г. для использования новичками в Дартмутском колледже, как средство для обучения программированию.
3. Язык, разработанный в 1970 г. швейцарским специалистом в области вычислительной техники профессором Н. Виртом, являющийся прямым развитием направления Алгола и ставший одним из наиболее популярных процедурных языков программирования среди прикладных программистов.
4. Язык, разработанный в начале 70–х гг. для реализации разработки систем, трансляторов, баз данных и других системных и прикладных программ.

Языки типа Автокод-Ассемблер являются машинно-ориентированными, то есть они настроены на структуру машинных команд конкретного компьютера.
Языки программирования высокого уровня (ЯПВУ) являются машинно-независимыми языками.
В 1965 г. в Дартмутском университете был разработан язык Бейсик – язык символических инструкций для начинающих. По замыслу авторов это простой легко изучаемый язык, предназначенный для программирования несложных расчетных задач.
Значительным событием в истории языков программирования стало создание в 1971 г. языка Паскаль. Его автор, швейцарский профессор Н.Вирт, разрабатывал Паскаль как учебный язык структурного программирования.
Язык программирования Си (английское название – С) создавался как инструментальный язык для разработки операционных систем, трансляторов, баз данных и других системных и прикладных программ. Так же, как и Паскаль, Си – это язык структурного программирования, но, в отличие от Паскаля, в нем заложены возможности непосредственного обращения к некоторым машинным командам, к определенным участкам памяти компьютера. Дальнейшее развитие Си привело к созданию языка объектно-ориентированного программирования Си++.

Установите соответствие между характеристиками классов языков программирования (по стилю программирования) и их названиями.
1. Языки, которые являются отражением архитектуры традиционных ЭВМ, предложенной Д. фон Нейманом в 40-х гг.
2. Языки, в которых единственным действием является вызов функции.
3. Языки программирования в терминах логики, первоначально предназначенные для работы с естественными языками.
4. Языки, которые содержат объекты и позволяют разрабатывать хорошо структурированные, надежные и легко модифицируемые программы.

По стилю программирования языки разделяются на процедурные – это языки, которые являются отражением архитектуры традиционных ЭВМ, предложенной Д. фон Нейманом в 40-х гг; функциональные – языки, в которых единственным действием является вызов функции; логические – языки программирования в терминах логики, первоначально предназначенные для работы с естественными языками; объектно-ориентированные – языки, которые содержат объекты и позволяют разрабатывать хорошо структурированные, надежные и легко модифицируемые программы.

Тип данных в языке программирования не определяет …

Концепция типов данных является одной из центральных в любом языке программирования. С типом величины связаны три ее свойства: форма внутреннего представления, множество принимаемых значений и множество допустимых операций (Семакин И.Г. Основы программирования: учебник для сред. проф. образования. М., 2003. С. 37). Следовательно, тип данных не определяет область действия переменных.

Программа, которая выполняет синтаксический и определенный смысловой анализ всего исходного кода программы и затем при отсутствии ошибок переводит его на машинный язык (создает объектный код), называется …

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

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

Редактор связей является компонентом систем программирования. Он выполняет связывание объектных модулей и машинного кода стандартных функций и формирует работоспособное приложение – исполнимый код для конкретной платформы.

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

Оператором языка программирования называется …

Программа обычно представляет собой последовательность операторов. Оператором языка программирования называется наименьшая автономная часть языка программирования, команда. Каждый оператор представляет собой законченную фразу языка программирования и определяет однозначно трактуемый этап обработки данных.

Разрешающая способность экрана в графическом режиме определяется количеством …

Разрешающая способность экрана – это размер экрана монитора по ширине и высоте в пикселях.

Формат _________ применяется для хранения растровых изображений, является родным форматом операционной системы Windows и поддерживается всеми графическими редакторами, работающими под ее управлением.

BMP (Windows Device Independent Bitmap) — является родным форматом операционной системы Windows и поддерживается всеми графическими редакторами, работающими под ее управлением.

WMF (Windows MetaFile) – это формат хранения векторных изображений операционной системы Windows (расширение имени файла WMF). По определению поддерживается всеми приложениями этой системы. Однако отсутствие средств для работы со стандартизированными цветовыми палитрами, принятыми в полиграфии, и другие недостатки ограничивают его применение (WMF искажает цвет, не может сохранять ряд параметров, которые могут быть присвоены объектам в различных векторных редакторах).

TIFF (Tagged Image File Format) Этот формат предназначен для хранения растровых изображений высокого качества (расширение имени файла TIF). Является одним из самых распространенных и надежных, его поддерживают практически все программы. TIFF является лучшим выбором при импорте растровой графики в векторные программы и издательские системы. Предусматривает широкий диапазон цветового охвата – от монохромного черно-белого до модели CMYK.

PDF (Portable Document Format) — это формат описания документов, разработанный фирмой Adobe (расширение имени файла PDF). Хотя этот формат в основном предназначен для хранения документа целиком, его впечатляющие возможности позволяют обеспечить эффективное представление изображений. Формат является аппаратно-независимым, поэтому вывод изображений допустим на любых устройствах – от экрана монитора до фотоэкспонирующего устройства. Мощный алгоритм сжатия со средствами управления итоговым разрешением изображения обеспечивает компактность файлов при высоком качестве иллюстраций.

Стандартным расширением тестового файла Microsoft Word, входящего в пакет Microsoft Office 2003, является …

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

Odt – открытый формат файлов документов для хранения и обмена редактируемыми офисными документами. Расширение odt – это стандартное расширение для OpenOffice.

.txt принадлежит текстовым файлам, которые могут содержать только чистый текст.

.doc — является стандартным расширением тестового файла Microsoft Word, входящего в пакет Microsoft Office 2003.

Из перечисленного ниже векторным графическим редактором является …

Adobe Illustrator – векторный графический редактор фирмы Adobe.

Gimp – это растровый графический редактор, входящий в пакет стандартной установки операционной системы Linux.

Paint – это растровый графический редактор, входящий в пакет стандартной установки операционной системы Windows.

Adobe Photoshop – это растровый графический редактор фирмы Adobe.

Программа _______, предназначенная для работы с электронными таблицами, является абсолютно бесплатной.

Microsoft Excel – это программа для работы с электронными таблицами, входящая в пакет Microsoft Office; является платным продуктом.

Numbers – это программа для работы с электронными таблицами, входящая в пакет iWork; является платным продуктом.

SuperCalc – это программа для работы с электронными таблицами, являющаяся условно-бесплатным продуктом (shareware).

Объект ____________ в Microsoft Access служит для извлечения данных из таблиц и предоставления их пользователю в удобном виде. С помощью этого объекта можно выполнять такие операции,как отбор данных, их сортировку.

Объект «Запрос» служит для извлечения данных из таблиц и предоставления их пользователю в удобном виде. С помощью «Запросов» можно выполнять такие операции,как отбор данных, их сортировку.

Категория «Макрос» предназначена для автоматизации повторяющихся операций при работе с системой управления базами данных.

«Отчет» по свойствам и структуре похож на «Форму», но предназначен только для вывода данных, причем не на экран, а на печатающее устройство. В связи с этим «Отчеты» содержат группировку выводимых данных и специальные элементы управления: колонтитулы, номера страниц, и другие.

«Форма» –это средство для ввода и вывода данных. Смысл ее в том, чтобы предоставить пользователю средства для просмотра или заполнения допустимых полей. Форма может содержать специальные элементы управления.

Не существует ___________ диаграммы.

Биржевая, лепестковая, пузырьковая диаграммы существуют. Биржевая и пузырьковая диаграммы отображают наборы данных из трех значений. Лепестковая диаграмма отображает распределение значений относительно точки отсчета. Не существует флажковой диаграммы.

В Microsoft Office PowerPoint составляющими дизайна слайдов являются …

Дизайн слайда подразумевает под собой то, каким образом будет выглядеть презентация при ее показе, поэтому составляющими дизайна слайдов являются оформление слайдов, цветовые схемы слайдов и эффекты анимации.

Источник