Чем определяется свойства алгоритмов дискретность
Студентик.РФ
Алгоритмы
Свойства алгоритма
Алгоритм обладает следующими основными свойствами:
Дискретность – свойство алгоритма, которое характеризует его структуру. Любой алгоритм состоит из отдельных операций (этапов, действий), которые выполняются дискретно (по шагам). Это означает, что алгоритм обладает свойством дискретности.
Детерминированность – свойство алгоритма, указывающее на то, что каждый шаг алгоритма должен быть строго определен и не может допускать различных толкований. Также строго должен быть определен порядок выполнения отдельных шагов, то есть исполнитель должен точно знать последовательность выполнения операций. Любой алгоритм должен быть представлен таким образом, чтобы он мог быть однозначно (точно) реализован исполнителем. Это свойство алгоритма называют также определенностью, однозначностью или точностью.
Массовость (универсальность) – применимость алгоритма ко всем задачам рассматриваемого типа при любых допустимых множествах исходных данных. Здесь важно подчеркнуть, что массовость означает применимость алгоритма ко всем задачам рассматриваемого типа, то есть ко всем задачам, для решения которых он предназначен. Кроме того, здесь необходимо иметь в виду, что реализация алгоритма возможна при любых, но допустимых множествах исходных данных.
Формальность – свойство означающее, что любой исполнитель, выполняющий алгоритм (например, компьютер), действует формально, то есть строго выполняет инструкции предусмотренные разработчиком алгоритма.
Алгоритм. Свойства алгоритма
Существует множество определений понятия «алгоритм»:
Из определений вытекают свойства алгоритма [5]:
Теперь покажем, что конкретный алгоритм обладает этими свойствами. В качестве примера, возьмем алгоритм, изображенный на рис. 1 в виде блок-схемы [6].
Рис 1 Блок-схема алгоритма проверки правильности расстановки скобок
Приведенный алгоритм проверяет правильность расстановки скобок, если скобки расставлены правильно – то каждой закрывающей скобке предшествует соответствующая открывающая, а каждой открывающей соответствует закрывающая.
Суть алгоритма заключается в подсчете глубины вложенности скобок друг в друга. Если в какой-то момент глубина получает значение меньше нуля – то скобки расставлены неправильно. Если просмотрены все символы строки, но счетчик не равен нулю – то в строке есть не закрытые скобки (расставлены неправильно). В противном случае скобки расставлены правильно.
Можно сказать, что алгоритм обладает свойством дискретности, так как весь алгоритм разбит на отдельные части (на блок-схеме это хорошо видно).
Доказать детерминированность алгоритма, достаточно сложно, например, когда алгоритм содержит части, которые выполняются параллельно, но не будем сейчас на этом останавливаться. Скажем, что в данном случае программа является детерминированной, т.к. не содержит фрагментов, зависящих от времени выполнения, т.е. сколько бы мы не тестировали алгоритм на одной и той же строке результат не изменится.
Чтобы показать результативность алгоритма, в данном случае достаточно заметить, что любой путь из начальной вершины в конечную содержит блок вывода результата. Перед блоком «конец» алгоритм содержит лишь 2 альтернативные ветви, каждая из которых выводит некоторый результат.
Алгоритм обладает свойством массовости, т.к. исходными данными для него может быть любая конечная последовательность символов. Алгоритм не обладал бы этим свойством, если бы работал лишь ограниченном наборе исходных данных, например на строках «()» и «())», но на остальных наборах не работал или работал не правильно.
Проверить свойство правильности алгоритма достаточно просто, для этого можно взять несколько примеров исходных данных, для которых результат очевиден и протестировать алгоритм на них, но доказать правильность алгоритма достаточно сложно. Доказательство правильности называется верификацией и явно выходит за рамки этой статьи.
В этой статье мы разобрались с тем, что такое алгоритм и какими основными свойствами он должен обладать. К теме алгоритмов я обязательно вернусь в будущих статьях.
Информатика. 11 класс
Тезаурус
Алгоритм — это точная конечная система предписаний, определяющая содержание и порядок действий исполнителя над некоторыми объектами для получения искомого результата.
Исполнитель алгоритма — это субъект или устройство, способные правильно интерпретировать описание алгоритма и выполнить содержащийся в нем перечень действий.
Дискретность — свойство алгоритма, которое означает, что алгоритм состоит из отдельных команд, каждая из которых выполняется за конечное число шагов.
Детерминированность (или определенность) — свойство алгоритма, которое означает, что при каждом запуске алгоритма с одними и теми же исходными данными должен быть получен один и тот же результат.
Понятность — свойство алгоритма, которое означает, что алгоритм содержит только те команды, которые входят в систему команд исполнителя, для которого он предназначен.
Конечность (или результативность) — свойство алгоритма, которое означает, что для корректного набора данных алгоритм должен завершиться через конечное время с вполне определенным результатом. При этом результатом может быть и сообщение о том, что задача не имеет решений.
Массовость — свойство алгоритма, которое означает, что алгоритм предназначен для решения не одной частной задачи, а для некоторого класса задач.
Сложность алгоритма — количество элементарных шагов в вычислительном процессе этого алгоритма.
Список литературы
Основная литература по теме урока:
— Л. Л. Босова, А. Ю. Босова. Информатика. Базовый уровень: учебник для 11 класса — М.: БИНОМ. Лаборатория знаний, 2017
Дополнительная литература по теме урока:
— К. Ю. Поляков, Е. А. Еремин. Информатика углубленный уровень: учебник для 10 класса: часть 2 — М.: БИНОМ. Лаборатория знаний, 2013
— И. Г. Семакин, Т. Ю. Шеина, Л. В. Шестакова. Информатика и ИКТ. Профильный уровень: учебник для 10 класса — М.: БИНОМ. Лаборатория знаний, 2010
Понятие алгоритма: Дискретность и результативность
Понятие алгоритма – одно из фундаментальных понятий информатики. Алгоритмы являются предметом изучения такой научной дисциплины, как «Теория алгоритмов». Однако при решении практических задач, как правило, не опираются на высокую формализацию данного понятия и ограничиваются содержательным толкованием сущности понятия алгоритма.
Под алгоритмом понимается понятное и точное предписание исполнителю совершить последовательность действий, направленных на достижение поставленной цели
Фрагменты из сказок «Сказка про Федота-стрельца» и «Перышко Финиста ясна сокола» содержат предписание определенному исполнителю, но эти предписания не являются точными.
Фрагмент из сказки об Иване-царевиче и сером волке содержит не предписание, а констатацию того, что произойдет в том или ином случае.
Фрагмент из сказки «Царевна-лягушка» задает понятное и точное предписание детям царя совершить определенные действия для решения вопроса о женитьбе.
Свойство алгоритма, означающее, что результат выполнения алгоритма определяется только входными данными и шагами (последовательностью действий) самого алгоритма называется детерминированностью (определенностью). Можно пояснить это свойство иначе: запись алгоритма должна быть настолько четкой, полной и продуманной в деталях, чтобы у исполнителя не возникала необходимость в принятии решений, не предусмотренных составителем алгоритма.
Дискретность также является свойством алгоритма. Дискретность означает, что описываемый процесс должен быть разбит на упорядоченную последовательность отдельных шагов.
Результативность также является свойством алгоритма. Смысл этого свойства состоит в том, что процесс выполнении алгоритма должен прекратиться за конечное число шагов и при этом должен получиться определенный результат. Вывод о том, что решения не существует, тоже результат.
Массовостьтакже является свойством алгоритма. Массовость означает, что один алгоритм в общем случае может применяться для решения некоторого класса задач, а в простейшем случае обеспечивает возможность использования различных входных данных задачи.
Установите соответствие между характеристиками и названиями языков программирования.
1. Язык, предназначенный для представления в символической форме программ, записанных на машинном языке; позволяющий программисту пользоваться мнемоническими кодами операций, по своему усмотрению присваивать символические имена регистрам ЭВМ и ячейкам памяти, а также задавать наиболее удобные в том или ином контексте схемы адресации.
2. Многоцелевой простой язык символических инструкций для начинающих, разработанный в 1964 г. для использования новичками в Дартмутском колледже, как средство для обучения программированию.
3. Язык, разработанный в 1970 г. швейцарским специалистом в области вычислительной техники профессором Н. Виртом, являющийся прямым развитием направления Алгола и ставший одним из наиболее популярных процедурных языков программирования среди прикладных программистов.
4. Язык, разработанный в начале 70–х гг. для реализации разработки систем, трансляторов, баз данных и других системных и прикладных программ.
Языки типа Автокод-Ассемблер являются машинно-ориентированными, то есть они настроены на структуру машинных команд конкретного компьютера.
Языки программирования высокого уровня (ЯПВУ) являются машинно-независимыми языками.
В 1965 г. в Дартмутском университете был разработан язык Бейсик – язык символических инструкций для начинающих. По замыслу авторов это простой легко изучаемый язык, предназначенный для программирования несложных расчетных задач.
Значительным событием в истории языков программирования стало создание в 1971 г. языка Паскаль. Его автор, швейцарский профессор Н.Вирт, разрабатывал Паскаль как учебный язык структурного программирования.
Язык программирования Си (английское название – С) создавался как инструментальный язык для разработки операционных систем, трансляторов, баз данных и других системных и прикладных программ. Так же, как и Паскаль, Си – это язык структурного программирования, но, в отличие от Паскаля, в нем заложены возможности непосредственного обращения к некоторым машинным командам, к определенным участкам памяти компьютера. Дальнейшее развитие Си привело к созданию языка объектно-ориентированного программирования Си++.
Установите соответствие между характеристиками классов языков программирования (по стилю программирования) и их названиями.
1. Языки, которые являются отражением архитектуры традиционных ЭВМ, предложенной Д. фон Нейманом в 40-х гг.
2. Языки, в которых единственным действием является вызов функции.
3. Языки программирования в терминах логики, первоначально предназначенные для работы с естественными языками.
4. Языки, которые содержат объекты и позволяют разрабатывать хорошо структурированные, надежные и легко модифицируемые программы.
По стилю программирования языки разделяются на процедурные – это языки, которые являются отражением архитектуры традиционных ЭВМ, предложенной Д. фон Нейманом в 40-х гг; функциональные – языки, в которых единственным действием является вызов функции; логические – языки программирования в терминах логики, первоначально предназначенные для работы с естественными языками; объектно-ориентированные – языки, которые содержат объекты и позволяют разрабатывать хорошо структурированные, надежные и легко модифицируемые программы.
Тип данных в языке программирования не определяет …
Концепция типов данных является одной из центральных в любом языке программирования. С типом величины связаны три ее свойства: форма внутреннего представления, множество принимаемых значений и множество допустимых операций (Семакин И.Г. Основы программирования: учебник для сред. проф. образования. М., 2003. С. 37). Следовательно, тип данных не определяет область действия переменных.
Программа, которая выполняет синтаксический и определенный смысловой анализ всего исходного кода программы и затем при отсутствии ошибок переводит его на машинный язык (создает объектный код), называется …
Одним из основных компонентов любой системы программирования является транслятор. Компилятор относится к программам-трансляторам. Компиляторы полностью обрабатывают весь текст программы. Они просматривают его в поисках синтаксических ошибок (иногда несколько раз), выполняют определенный смысловой анализ и затем автоматически переводят (транслируют) на машинный язык – генерируют машинный код. Обычно это промежуточный объектный код, для получения готовой программы к нему необходимо добавить еще ряд компонентов
Интерпретатор, так же как компилятор, относится к программам-трансляторам. Однако, интерпретатор анализирует и выполняет операторы языка из текста программы строго последовательно. Только после того как текущий оператор успешно выполнен, интерпретатор переходит к следующему.
Редактор связей является компонентом систем программирования. Он выполняет связывание объектных модулей и машинного кода стандартных функций и формирует работоспособное приложение – исполнимый код для конкретной платформы.
Отладчик является компонентом современных систем программирования. Он позволяет анализировать работу программы во время ее выполнения.
Оператором языка программирования называется …
Программа обычно представляет собой последовательность операторов. Оператором языка программирования называется наименьшая автономная часть языка программирования, команда. Каждый оператор представляет собой законченную фразу языка программирования и определяет однозначно трактуемый этап обработки данных.
Разрешающая способность экрана в графическом режиме определяется количеством …
Разрешающая способность экрана – это размер экрана монитора по ширине и высоте в пикселях.
Формат _________ применяется для хранения растровых изображений, является родным форматом операционной системы Windows и поддерживается всеми графическими редакторами, работающими под ее управлением.
WMF (Windows MetaFile) – это формат хранения векторных изображений операционной системы Windows (расширение имени файла WMF). По определению поддерживается всеми приложениями этой системы. Однако отсутствие средств для работы со стандартизированными цветовыми палитрами, принятыми в полиграфии, и другие недостатки ограничивают его применение (WMF искажает цвет, не может сохранять ряд параметров, которые могут быть присвоены объектам в различных векторных редакторах).
TIFF (Tagged Image File Format) Этот формат предназначен для хранения растровых изображений высокого качества (расширение имени файла TIF). Является одним из самых распространенных и надежных, его поддерживают практически все программы. TIFF является лучшим выбором при импорте растровой графики в векторные программы и издательские системы. Предусматривает широкий диапазон цветового охвата – от монохромного черно-белого до модели CMYK.
Стандартным расширением тестового файла Microsoft Word, входящего в пакет Microsoft Office 2003, является …
XML – текстовый формат, предназначенный для хранения структурированных данных, для обмена информацией между программами.
Odt – открытый формат файлов документов для хранения и обмена редактируемыми офисными документами. Расширение odt – это стандартное расширение для OpenOffice.
.txt принадлежит текстовым файлам, которые могут содержать только чистый текст.
Из перечисленного ниже векторным графическим редактором является …
Adobe Illustrator – векторный графический редактор фирмы Adobe.
Gimp – это растровый графический редактор, входящий в пакет стандартной установки операционной системы Linux.
Paint – это растровый графический редактор, входящий в пакет стандартной установки операционной системы Windows.
Adobe Photoshop – это растровый графический редактор фирмы Adobe.
Программа _______, предназначенная для работы с электронными таблицами, является абсолютно бесплатной.
Microsoft Excel – это программа для работы с электронными таблицами, входящая в пакет Microsoft Office; является платным продуктом.
Numbers – это программа для работы с электронными таблицами, входящая в пакет iWork; является платным продуктом.
SuperCalc – это программа для работы с электронными таблицами, являющаяся условно-бесплатным продуктом (shareware).
Объект ____________ в Microsoft Access служит для извлечения данных из таблиц и предоставления их пользователю в удобном виде. С помощью этого объекта можно выполнять такие операции,как отбор данных, их сортировку.
Объект «Запрос» служит для извлечения данных из таблиц и предоставления их пользователю в удобном виде. С помощью «Запросов» можно выполнять такие операции,как отбор данных, их сортировку.
Категория «Макрос» предназначена для автоматизации повторяющихся операций при работе с системой управления базами данных.
«Отчет» по свойствам и структуре похож на «Форму», но предназначен только для вывода данных, причем не на экран, а на печатающее устройство. В связи с этим «Отчеты» содержат группировку выводимых данных и специальные элементы управления: колонтитулы, номера страниц, и другие.
«Форма» –это средство для ввода и вывода данных. Смысл ее в том, чтобы предоставить пользователю средства для просмотра или заполнения допустимых полей. Форма может содержать специальные элементы управления.
Не существует ___________ диаграммы.
Биржевая, лепестковая, пузырьковая диаграммы существуют. Биржевая и пузырьковая диаграммы отображают наборы данных из трех значений. Лепестковая диаграмма отображает распределение значений относительно точки отсчета. Не существует флажковой диаграммы.
В Microsoft Office PowerPoint составляющими дизайна слайдов являются …
Дизайн слайда подразумевает под собой то, каким образом будет выглядеть презентация при ее показе, поэтому составляющими дизайна слайдов являются оформление слайдов, цветовые схемы слайдов и эффекты анимации.
Дискретность алгоритма
Исполнение алгоритма распадается на последовательность отдельных шагов,выполнение которых предписывает команда. Таким образом, алгоритм представляет собой последовательность команд, определяющих действия исполнителя. Алгоритм имеет прерывистую (дискретную) структуру: только выполнив одну команду, исполнитель может приступить к выполнению следующей. Это свойство называется дискретностью.
Понятность алгоритма
Правильно составленный алгоритм содержит только те команды, которые входят в систему команд исполнителя, для которого он написан. Такое свойство называется понятностью.
Понятными для исполнителя считаются те команды, которые он может выполнить.
Например, человек, не умеющий складывать однозначные числа (не знающий таблицы сложения), не сможет воспользоваться описанным аль-Хорезми порядком сложения многозначных чисел.
Точность (определенность, однозначность) алгоритма
Важным свойством алгоритма является точность (определенность, однозначность).Каждая команда алгоритма должна однозначно восприниматься исполнителем и предполагать его определенное действие. Выполнив шаг алгоритма, исполнитель должен точно знать, какой шаг выполнять следующим. Примером неточного алгоритма является фраза из рецепта «всыпать 2-3 столовые ложки сахара» или классическое изречение «казнить нельзя помиловать».
Результативность и конечность алгоритма
Исполнение алгоритма должно приводить к получению результата (свойство результативности)за конечное число шагов (свойство конечности).
Массовость алгоритма.
Желательно, чтобы алгоритм удовлетворял свойству массовости, т.е. мог быть применен для решения не только одной конкретной задачи, но и некоторого класса однотипных задач.
Например, правило сложения многозначных чисел не зависит от количества разрядов в слагаемых или их цифрового состава. Оно работает, даже если число представлено не в десятичной системе счисления, а в позиционной системе счисления с любым целочисленным основанием.