в чем состоит суть свойства алгоритма результативность
Алгоритм. Свойства алгоритма
Существует множество определений понятия «алгоритм»:
Из определений вытекают свойства алгоритма [5]:
Теперь покажем, что конкретный алгоритм обладает этими свойствами. В качестве примера, возьмем алгоритм, изображенный на рис. 1 в виде блок-схемы [6].
Рис 1 Блок-схема алгоритма проверки правильности расстановки скобок
Приведенный алгоритм проверяет правильность расстановки скобок, если скобки расставлены правильно – то каждой закрывающей скобке предшествует соответствующая открывающая, а каждой открывающей соответствует закрывающая.
Суть алгоритма заключается в подсчете глубины вложенности скобок друг в друга. Если в какой-то момент глубина получает значение меньше нуля – то скобки расставлены неправильно. Если просмотрены все символы строки, но счетчик не равен нулю – то в строке есть не закрытые скобки (расставлены неправильно). В противном случае скобки расставлены правильно.
Можно сказать, что алгоритм обладает свойством дискретности, так как весь алгоритм разбит на отдельные части (на блок-схеме это хорошо видно).
Доказать детерминированность алгоритма, достаточно сложно, например, когда алгоритм содержит части, которые выполняются параллельно, но не будем сейчас на этом останавливаться. Скажем, что в данном случае программа является детерминированной, т.к. не содержит фрагментов, зависящих от времени выполнения, т.е. сколько бы мы не тестировали алгоритм на одной и той же строке результат не изменится.
Чтобы показать результативность алгоритма, в данном случае достаточно заметить, что любой путь из начальной вершины в конечную содержит блок вывода результата. Перед блоком «конец» алгоритм содержит лишь 2 альтернативные ветви, каждая из которых выводит некоторый результат.
Алгоритм обладает свойством массовости, т.к. исходными данными для него может быть любая конечная последовательность символов. Алгоритм не обладал бы этим свойством, если бы работал лишь ограниченном наборе исходных данных, например на строках «()» и «())», но на остальных наборах не работал или работал не правильно.
Проверить свойство правильности алгоритма достаточно просто, для этого можно взять несколько примеров исходных данных, для которых результат очевиден и протестировать алгоритм на них, но доказать правильность алгоритма достаточно сложно. Доказательство правильности называется верификацией и явно выходит за рамки этой статьи.
В этой статье мы разобрались с тем, что такое алгоритм и какими основными свойствами он должен обладать. К теме алгоритмов я обязательно вернусь в будущих статьях.
Алгоритм и его свойства.
1. Конечность(результативность) алгоритма означает, что за конечное число шагов должен быть получен результат;
2. Дискретность алгоритма означает, что алгоритм должен быть разбит на последовательность выполняемых шагов;
3. Понятность алгоритма означает, что алгоритм должен содержать только те команды, которые входят в набор команд, который может выполнить конкретный исполнитель;
4. Точность алгоритма означает, что каждая команда должна пониматься однозначно;
5. Массовость алгоритма означает, что однажды составленный алгоритм должен подходить для решения подобных задач с разными исходными данными.
6. Детерминированность (определенность). Алгоритм обладает свойством детерминированности, если для одних и тех же наборов исходных данных он будет выдавать один и тот же результат, т.е. результат однозначно определяется исходными данными.
Таким образом, Алгоритм — это понятное и точное предписание исполнителю, выполнить конечную последовательность шагов, приводящей от исходных данных к искомому результату.
Другие статьи в литературном дневнике:
Портал Стихи.ру предоставляет авторам возможность свободной публикации своих литературных произведений в сети Интернет на основании пользовательского договора. Все авторские права на произведения принадлежат авторам и охраняются законом. Перепечатка произведений возможна только с согласия его автора, к которому вы можете обратиться на его авторской странице. Ответственность за тексты произведений авторы несут самостоятельно на основании правил публикации и российского законодательства. Вы также можете посмотреть более подробную информацию о портале и связаться с администрацией.
Ежедневная аудитория портала Стихи.ру – порядка 200 тысяч посетителей, которые в общей сумме просматривают более двух миллионов страниц по данным счетчика посещаемости, который расположен справа от этого текста. В каждой графе указано по две цифры: количество просмотров и количество посетителей.
© Все права принадлежат авторам, 2000-2021 Портал работает под эгидой Российского союза писателей 18+
Понятие алгоритма. Свойства алгоритма.
Одним из фундаментальных понятий в информатике является понятие алгоритм. Происхождение самого термина «алгоритм» связано с математикой. Это слово происходит от Algorithmi – латинского написания имени Мухаммеда аль-Хорезми (787 – 850), выдающегося математика средневекового Востока. В XII в. был выполнен латинский перевод его математического трактата, из которого европейцы узнали о десятичной позиционной системе счисления и правилах арифметики многозначных чисел. Именно эти правила в то время называли алгоритмами. Сложение, вычитание, умножение столбиком, деление уголком многозначных чисел – вот первые алгоритмы в математике.
Любой алгоритм должен удовлетворять основным свойствам::
Конечность алгоритма означает, что за конечное число шагов должен быть получен результат. Поэтому иногда это свойство называют результативностью.
Дискретность (прерывность, раздельность) – алгоритм должен представлять процесс решения задачи как последовательное выполнение простых (или ранее определенных) шагов. Каждое действие, предусмотренное алгоритмом, исполняется только после того, как закончилось исполнение предыдущего.
Понятностьалгоритма означает, что алгоритм должен содержать только те команды, которые входят в СКИ-система команд исполнителя.
Определенность – каждое правило алгоритма должно быть четким, однозначным и не оставлять места для произвола. Благодаря этому свойству выполнение алгоритма носит механический характер и не требует никаких дополнительных указаний или сведений о решаемой задаче.
Корректность – свойство алгоритма, заключающееся в способности алгоритма давать правильные результаты при различных исходных данных.
Массовость – алгоритм решения задачи разрабатывается в общем виде, то есть, он должен быть применим для некоторого класса задач, различающихся только исходными данными. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма.
Презентация к уроку
Цель урока: Формирования у учащихся правильного понимания алгоритмов, их свойств, видов и практических навыков составления алгоритмов.
Задачи урока:
Дидактические: Обеспечить условия:
Воспитательные: Обеспечить условия:
Развивающие: Обеспечить условия:
Демонстрационный материал к уроку:
Ход урока
Понятие алгоритма
Появление алгоритмов связывают с зарождением математики.
Более 1000 лет назад (825 г.)ученый из города Хорезма Абдулла (или Абу Ждафар) Мухаммед бен Мусса аль-Хорезми создал книгу по математике, в тором описал способы выполнения арифметических действий над многозначными числами.
Алгоритм – описание последовательности действий, исполнение которых приводит к решению поставленной задачи за конечное число шагов.
Алгоритм — понятное и точное предписание исполнителю выполнить конечную последовательность команд, приводящих от исходных данных к искомому результату.
Свойства алгоритма
Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении на естественном языке.
Пример: Алгоритм «Зарядка»
При словесно-формульном способе алгоритм записывается в виде текста с формулами по пунктам, определяющим последовательность действий.
Пусть, например, необходимо найти значение следующего выражения:
Словесно-формульным способом алгоритм решения этой задачи может быть записан в следующем виде:
При графическом представлении алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий.
Виды алгоритма
Линейный алгоритм – это такой, в котором все операции выполняются
последовательно одна за другой.
Пример: Алгоритм посадки дерева.
Разветвляющийся алгоритм – это алгоритм в котором выполняется либо одна, либо другая группа действий в зависимости от истинности или ложности условия.
Полная форма
Неполная форма
Пример: Если на улице дождь, то останемся дома, а если нет то идем гулять.
Циклический алгоритм – действия повторяются до тех пор, пока выполняется заданное условие.
Цикл с известным числом повторений
Цикл с известным числом повторений часто называют «циклом ДЛЯ»
Пример: Алгоритм «Упражнение для глаз»
Цикл с постусловием
Цикл с неизвестным числом повторений, в тором выход из цикла осуществляется при выполнении условия, принято называть «циклом с постусловием» или «циклом ПРИ»
Цикл с предусловием
Цикл с известным числом повторений, в котором цикл продолжается, пока выполняется условие, принято называть «циклом с предусловием» или «циклом ПОКА»
Основы алгоритмизации и программирования
8.1. Понятие алгоритма и свойства алгоритма
248.Суть такого свойства алгоритма как результативность заключается в том, что:
— алгоритм должен иметь дискретную структуру (должен быть разбит на последовательность отдельных шагов)
— записывая алгоритм для конкретного исполнителя, можно использовать лишь те команды, что входят в систему его команд
— алгоритм должен обеспечивать решение не одной конкретной задачи, а некоторого класса задач данного типа
— при точном исполнении всех команд алгоритма процесс должен прекратиться за конечное число шагов, приведя к определенному результату
249.Суть такого свойства алгоритма как массовость заключается в том, что:
— алгоритм должен иметь дискретную структуру (должен быть разбит на последовательность отдельных шагов)
— записывая алгоритм для конкретного исполнителя, можно использовать лишь те команды, что входят в систему его команд
— алгоритм должен обеспечивать решение не одной конкретной задачи, а некоторого класса задач данного типа при всех допустимых значениях исходных данных
— при точном исполнении всех команд алгоритма процесс должен прекратиться за конечное число шагов, приведя к определенному результату
250.Суть такого свойства алгоритма как дискретность заключается в том, что:
— алгоритм должен иметь дискретную структуру (должен быть разбит на последовательность отдельных шагов)
— записывая алгоритм для конкретного исполнителя, можно использовать лишь те команды, что входят в систему его команд
— алгоритм должен обеспечивать решение не одной конкретной задачи, а некоторого класса задач данного типа
— при точном исполнении всех команд алгоритма процесс должен прекратиться за конечное число шагов, приведя к определенному результату
251.Суть такого свойства алгоритма как понятность заключается в том, что:
— алгоритм должен иметь дискретную структуру (должен быть разбит на последовательность отдельных шагов)
— запись алгоритма не должна допускать неоднозначности толкования
— алгоритм должен обеспечивать решение не одной конкретной задачи, а некоторого класса задач данного типа
— при точном исполнении всех команд алгоритма процесс должен прекратиться за конечное число шагов, приведя к определенному результату
252.Алгоритм – это:
— правила выполнения определенных действий
— ориентированный граф, указывающий порядок исполнения некоторого набора команд
— понятное и точное предписание исполнителю совершить последовательность действий, направленных на достижение поставленных целей
— набор команд для компьютера
253.Укажите наиболее полный перечень способов записи алгоритмов:
— словесный, графический, псевдокод, программный
8.2. Основные алгоритмические конструкции
254.Алгоритм решения некоторой подзадачи, выполняющийся неоднократно, называется:
— циклическим
255.Алгоритм называется циклическим:
— если он составлен так, что его выполнение предполагает многократное повторение одних и тех же действий
— если ход его выполнения зависит от истинности тех или иных условий;
— если его команды выполняются в порядке их естественного следования друг за другом независимо от каких-либо условий
— если он представим в табличной форме
256.Алгоритм называется линейным:
— если он составлен так, что его выполнение предполагает многократное повторение одних и тех нее действий
— если порядок его выполнения зависит от истинности тех или иных условий
— если его команды выполняются в порядке их естественного следования друг за другом независимо от каких-либо условий
— если он включает в себя вспомогательный алгоритм
257.Алгоритм включает в себя ветвление, если:
— если он составлен так, что его выполнение предполагает многократное повторение одних и тех же действий
— если ход его выполнения зависит от истинности тех или иных условий
— если его команды выполняются в порядке их естественного следования друг за другом независимо от каких-либо условий
— если он включает в себя вспомогательный алгоритм
8.3. Примеры решения задач
258.Результатом выполнения алгоритма, представленного на рисунке, для значения переменной X=10 будет число…
259.Результатом выполнения алгоритма, представленного на рисунке, для значения переменной X=-10 будет число…
260.Результатом выполнения алгоритма, представленного на рисунке, для значения переменной X=0 будет число…
261.В приведенном фрагменте блок-схемы выполняется…
262.После выполнения следующего фрагмента алгоритма значение целочисленной переменной Х будет равно…
8.4. Системы программирования
263.Системы программирования:
— обеспечивают непосредственное решение пользовательских задач;
— позволяют создавать новые программы на языках программирования;
— обеспечивают работу всех аппаратных устройств компьютера и доступ пользователя к ним;
— обеспечивают защиту от компьютерных вирусов
264.Из нижеперечисленных программных продуктов системами программирования являются:
Б) Microsoft Windows
— В, Г, Д
265.Подпрограммой называют:
— независимый программный модуль
— произвольный фрагмент программы
— набор операторов, следующих в программе за оператором GOSUB
— часть программы, служащей для решения некоторой вспомогательной задачи
266.Языки программирования, наборы операторов и изобразительные средства которых существенно зависят от особенностей ЭВМ (внутреннего языка, структуры памяти и т.д.) называются…
— Машинно – ориентированными языками
— Языками программирования высокого уровня
— Встроенными языками программирования
267.К языкам программирования высокого уровня НЕ относятся:
— логические ( Prolog, Lisp),
— объектно-ориентированные (ObjectPascal, C++, Java)
— машинно – ориентированные языки
Базы данных
9.1. Основные понятия теории баз данных
268.Программа управления базами данных MSAccess представляет собой программный продукт, входящий в состав:
— системного программного обеспечения;
— систем программирования баз данных;
— прикладного программного обеспечения;
— уникального программного обеспечения.
269.Ввод, редактирование и оформление текстовых данных позволяет осуществлять ________ программное обеспечение.
270.Не существует _______ модель базы данных:
271.На рисунке приведена модель базы данных:
272.На рисунке приведена модель базы данных:
273.На рисунке приведена модель базы данных:
274.Программа MS Access представляет собой программный продукт, входящий в состав:
— системного программного обеспечения
— прикладного программного обеспечения
— уникального программного обеспечения
9.2. Объекты баз данных. Типы данных.
275.База данных не может существовать без объекта …
276.Выборка данных в системе управления базами данных Access осуществляется с помощью…
277.На рисунке приведена…
278.На рисунке приведена…
279.Объект базы данных «форма» предназначен для …
280.Для вывода результатов запроса на печать системе управления базами данных Accessиспользуется объект…
9.3. Информационно-логическая модель базы данных
281.Приведенное на рисунке диалоговое окно позволяет …
282.На рисунке показано отношение между объектами А и Б, при котором…
283.На рисунке показано отношение между объектами А и Б, при котором…
284.На рисунке показано отношение между объектами А и Б, при котором…
9.4. Практические задания по теме
285.Представлена база данных «Школа». Запрос для вывода списка учеников 11 классов, 1987 года рождения, имеющих оценки не ниже 4, содержит выражение…
§ (Оценка >=4) И (Год рождения =1987) И (Класс =11)
286.Представлена база данных «Волшебные страны». После проведения сортировки сведения о НАРНИИ переместятся на одну строку вниз. Это возможно, если сортировка будет проведена в порядке…
287.На рисунке показана схема данных:
Выберите правильные утверждения, характеризующие показанную схему данных…
288.На рисунке показано:
— формирование запроса с параметром в режиме конструктора
— формирования запроса на удаление записей в режиме конструктора
— отображение результата запроса на выборку
— формирование перекрестного запроса в режиме «Мастера запросов»
10. Локальные и глобальные сети ЭВМ.
10.1. Компьютерные сети: понятие, структура, характеристики.
— компьютерная сеть
290.Под аппаратным компонентом компьютерной сети подразумевают:
— программы, управляющие аппаратным устройством сети
— типы аппаратных соединений в сети
— компьютеры сети, сетевые устройства, линий связи
— только компьютеры сети (сервера и рабочие станции)
291.Клиент это:
— компьютер, содержащий базу данных
— компьютер (программа), использующая соответствующий ресурс
— компьютер, автономно использующий операционную систему
— программа для предоставления сетевых сервисов
292.Сервер это:
— персональный компьютер, подключенный к сети, предоставляющий пользователю доступ к ее ресурсам
— компьютер подключенный к локальной или глобальной сети
— персональный компьютер пользователя
— компьютер-программа, использующая соответствующий ресурс
293.Компьютер, предоставляющий часть своих ресурсов для клиентов сети, называют
— сервер
294.Технологический режим удаленного доступа к информационным ресурсам сети с отсроченной выдачей результата запроса называется:
— Off-line
295.Технологический режим удаленного доступа к информационным ресурсам сети в реальном времени называется:
— On-line
296.Компьютер, предоставляющий при совместной работе свои ресурсы, называется:
— сервером
297.Группа компьютеров, связанных каналами передачи информации и находящихся в пределах территории, ограниченной небольшими размерами: комнаты, здания, предприятия, называется:
— глобальной компьютерной сетью
— информационной системой с гиперсвязями
— локальной компьютерной сетью
— региональной компьютерной сетью
298.Вычислительная (компьютерная) сеть служит для …
299.Для хранения файлов, предназначенных для общего доступа пользователей сети, используется:
— файл-сервер
10.2. Виды компьютерных сетей и особенности сетевых информационных технологий.
300.Вычислительные системы по их территориальному принципу подразделяются на:
— локальные, региональные, глобальные
— терминальные, административные, смешанные
— цифровые, коммерческие, корпоративные
— одноранговые и с выделенным файловым сервером
301.По типу организации передачи данных различают компьютерные сети:
— локальные, региональные, глобальные
— вычислительные, информационные, смешанные
— с коммутацией каналов, с коммутацией сообщений, с коммутацией пакетов
— однородные и неоднородные
302.Сеть, где каждый компьютер может играть роль как сервера, так и рабочей станции, имеет___________ архитектуру
— серверную
303.По возможности доступа к информационным ресурсам компьютерные сети делятся на:
— специализированные (принадлежащие организациям и ведомствам) и общедоступные
— локальные и глобальные
— однородные и гибридные
— одноранговые и с выделенным файловым сервером
304.По размещению информационных ресурсов в сети компьютерные сети делятся на:
— специализированные (принадлежащие организациям и ведомствам) и общедоступные
— локальные и глобальные
— однородные и гибридные
— централизованным хранением информации и с распределенным хранением информации
10.3. Топология локальных компьютерных сетей.
305.Обобщенная геометрическая характеристика компьютерной сети называется ….
306.Топология сети определяется:
— способом соединения узлов сети каналами связи
— типом кабеля, используемого для соединения компьютеров в сети
— структурой программного обеспечения
— характеристиками соединяемых рабочих станций
307.Кольцевая, шинная, звездообразная – это типы:
— сетевого программного обеспечения
— сетевых топологий
308.Какое соединение компьютеров подразумевает топология локальной сети типа «звезда»?
— каждый компьютер с каждым по кольцу
— все компьютеры подсоединены к одной шине
— все перечисленные ответы верны
309.Конфигурация (топология) локальной компьютерной сети, в которой все рабочие станции соединены непосредственно с сервером, называется:
— радиально
10.4. Стандартизация компьютерных сетей.
310.Протокол компьютерной сети – это:
311.Эталонная модель OSIхарактеризует:
312.В базовой модели OSI используются следующие уровни передачи данных:
313.На рисунке показано:
— Эталонная модель OSI
— Типы протоколов глобальных компьютерных сетей