Алгоритмы и их свойства

Современный человек использует компьютер для решения разнообразных задач — от выполнения простых арифметических действий к моделированию атмосферных явлений и управление полетами в космос. На самом деле, все, что «умеет» компьютер, -это выполнения программ. Чтобы компьютер мог решать нужную задачу, необходимо сначала создать соответствующую программу, а потом запустить ее на выполнение.

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

[smszamok]

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

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

Примеры. Слово НЕБО записано четырьмя буквами. Содержание, которое обозначено ими, не является четким, но для каждого человека это что-то большое над главой, голубое днем и черное ночью. Уточнять дальше не будем.

Запись 1001 представляет числ-мысленное понятие, которое выражает количество. Мы воспринимаем эти данные как «тысяча и один» (предмет, год и т.п.) или «тысяча и одна» (ночь, мелочь и т.п.).

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

Итак, представление объектов реального мира с помощью данных является основой любого взаимодействия, в частности и компьютера с «внешним» миром.

Компьютер должен решать задачи для человека. В этих задачах фигурируют разнообразные объекты реального мира — картинки, физические явления, лица, технологические процессы и т.п.. Чтобы запрограммировать обработку данных, связанных с этими объектами, надо сначала представить об ‘єктиу виде данных.

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

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

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

Чтобы решить квадратное уравнение вида ах2 + Ьх + с = 0, нужны лишь его коэффициенты — числа а, Ь, с, т.е. тройка этих чисел (данные) представляет уравнение. Формулы корней, в сущности, описывают действия из решение уравнения (вычислить дискриминант и т.п.).

Каждое современное предприятие имеет программные системы, которые автоматизируют учет кадров, заработного жалованья, финансового и производственной деятельности. Каждая из этих систем имеет «свои» данные, связанные с предприятием, которые используются и обрабатываются только в ней. Эти данные составляют часть соответствующей (кадровой, финансовой и т.п.) модели предприятия. Другая часть модели описывает, как присутствуют в модели данные используются и обрабатываются. В

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

Как правило, в алгоритме указано некоторые входные, результатные (исходные) и промежуточные данные, которые не является ни входными, ни исходными.
Последовательность действий, которую выполняют за алгоритмом, называется процессом. Алгоритм, как правило, определяет не один процесс, а некоторое их множество.
Пример. Рассмотрим задачу «вычислить действительные корни квадратного
уравнение ах2 + Ьх + с = 0, заданного коэффициентами а, Ь, с (при условии а < 0)». Алгоритм решения этой задачи, т.е. описание определения корней, может иметь такой вид: Прочитать коэффициенты а, Ь, с. Вычислить дискриминант d = b*b — 4*а*с. Если d > 0, то вычислить хі = ,
2а
-b + 4d
х2 = и написать эти числа;
2а иначе, если d = 0, то вычислить
-Ь „ х = — и написать это число;
2а
иначе написать «действительных корней нет».
В этом алгоритме входными данными являются коэффициенты а, Ь, с, промежуточными — дискриминант d, исходными — два корня (возможно, один) или текст «действительных корней нет».
За этим алгоритмом, в зависимости от конкретных входных данных, возможное выполнение одной из трех таких последовательностей действий.
1. Прочитать коэффициенты, вычислить d, проверить, что d > 0 (и это так), вычислить хі, х2 и написать эти числа.
2. Прочитать коэффициенты, вычислить d, проверить, что d > 0 (и это не так), проверить, что d = 0 (и это так), вычислить х и написать это число.
3. Прочитать коэффициенты, вычислить d, проверить, что d > 0 (и это не так), проверить, что d = 0 (и это не так), и написать, что действительных корней нет.
Очень часто алгоритм создается путем постепенного уточнения понятий, связанных с объектом, и нужных действий.
Пример. Рассмотрим алгоритм облачения ребенка. Сначала нам известно, что есть верхняя и нижняя одежда, и на первом шаге описание облачения имеет такой вид.
Надеть нижнюю одежду.
Надеть верхнюю одежду.

Потом уточняем, что такое нижняя одежда и что надо сделать, чтобы его надеть.
Надеть трусики.
Надеть майку.
Надеть носки.
Дальше уточняем, что такое верхняя одежда и в чем разность в одежде мальчиков и девушек. Упоминаем об обуви.
Надеть рубашку.
Если ребенок является мальчиком, то надеть штанишки,
иначе надеть юбочку.
Обуть сандалии.
Алгоритм облачения ребенка имеет такой окончательный вид.
Надеть трусики.
Надеть майху.
Надеть носки.
Надеть рубашку.
Если ребенок является мальчиком, то надеть штанишки,
иначе надеть юбочку.
Обуть сандалии.
Очевидно, что этот алгоритм задает два возможных процесса, которые отличаются надеванием штанишек или юбочки. В
Алгоритмы должны иметь несколько общих свойств: понятность, результативность, однозначность, дискретность, массовость и виконуваність. Рассмотрим их.
Понятность. Для выполнения алгоритма всегда нужный исполнитель. Это может быть человек или некоторая техническая система, в частности и компьютер. Например, выполнять арифметические действия, чтобы решить квадратное уравнение (и не только), может человек. Но она может перевести эту работу на компьютер, если создаст соответствующую программу и принудит компьютер ее выполнить. Действия из облачение ребенка способна выполнять человек, а с собирание приборов — специальная автоматическая линия.
Понятность алгоритма заключается в том, что исполнитель может правильно понять и выполнить команды, записанные в алгоритме. Но команды всегда записываются согласно некоторой системе обозначений.
Система обозначений некоторого содержания называется языком. Язык содержит элементарные обозначения, правила образования более сложных обозначений из более простых и правила, за которыми содержание и обозначения отвечают одно одному.
Итак, исполнитель должен понимать язык записи алгоритма.

Результативность. Выполнение любого алгоритма должно приносить его исполнителю или другому лицу ощутимые результаты. Например, «корни уравнение определено», «ребенок одет», «прибор собран» и т.п..
Однозначность. Алгоритм не должен содержать команд, содержание которых можно воспринять неоднозначно. Например, если бы в алгоритме облачения ребенка была команда «надеть штанишки или юбочку», исполнитель не знал бы, что же именно ему делать. Кроме того, после выполнения каждой команды исполнитель должен точно знать, что ему делать дальше.
Дискретность. Дискретность алгоритма заключается в том, что он задает последовательность действий, четко отделенных одна от одной. Итак, действия, заданные командой, должны начинаться лишь после окончания действий за предыдущей командой. Кроме того, выполнение каждой команды должно занимать ограниченный промежуток времени.

[/smszamok]

Массовость. Конкретные объекты, к которым применяются действия во время выполнения алгоритма, определяют конкретные задачи, которые часто называются экземплярами задачи. Например, конкретная тройка чисел 3,10,2, соответствующая квадратному уравнению, которое надо решить, или конкретный мальчик Вася, которого надо одеть. Массовость алгоритма заключается в том, что он описывает не один, а некоторое множество процессов, которые происходят при решении всех возможных экземпляров задачи. Подавляющее большинство алгоритмов являются массовыми, хотя существуют и алгоритмы, которые задают только один процесс.