Понятие алгоритма

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

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

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

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

Проблемами алгоритмизации при решении вычислительных задач занимались Паскаль, Декарт, Лейбниц, Лаплас и многие другие ученые. В XX в. бурно развивалась формальная теория алгоритмов. Среди ученых, внесших в эту теорию наиболее значительный вклад, можно назвать Геделя, Клини, Черча, Тьюринга, Поста, Маркова, Петера.

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

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

1.4. Методы обработки данных. Элементарные методы (команды)

Мы выяснили, как представляются любые данные в виде двоичной последовательности. Может быть, эта последовательность и есть информация, и мы, таким образом, определили основной предмет изучения информатики? Оказывается – нет. Информация содержит кроме данных еще один очень важный компонент – методы обработки данных.

Рассмотрим, например книгу, написанную на каком-либо языке. Для человека – носителя языка в книге может содержаться много полезной информации. Для человека, плохо владеющего языком, информации там содержится гораздо меньше. Если язык книги человеку неизвестен вообще – он не получит никакой информации (здесь используется понятие «информация» в интуитивном смысле, строгое определение будет дано позже).

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

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

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

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

Однако задача информатики не стоит так широко. Для нас достаточно понять, как строятся методы обработки данных в компьютерных системах. Эта задача значительно проще. Оказывается, все компьютерные методы обработки данных строятся по общим законом.

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

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

Команды процессора реализуются аппаратно, т.е. заданы при изготовлении процессора.

Каждая команда процессора имеет свой код, т.е. число, которое необходимо загрузить в специальную ячейку (регистр) процессора, для того, чтобы команда выполнилась. Большинство команд выполняются над данными и без данных теряют смысл. Например, чтобы сложить 2 числа A и B, нужно загрузить в один из регистров код команды сложения, но в другие регистры при этом должны быть загружены сами числа A и B, иначе команда сложения не будет иметь смысла.

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

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

Если компьютерная программа записана и хранится на каком-либо носителе данных (на жестком диске, сменном носителе и т.п.), то он ничем не отличается от простого набора данных, т.к. записанные коды команд – данные. Но любая программа обладает одной особенностью – ее можно активизировать (запустить). Для этого программу нужно сначала загрузить в оперативную память компьютера, а затем загрузить в регистр процессора адрес первой команды программы. После этого все команды программы начнут выполняться последовательно. Строгая последовательность выполнения команд программы может нарушаться специальными командами перехода. Это позволяет организовывать ветвление по условию, циклическое многократное выполнение некоторых блоков в программе и в результате – реализовывать алгоритмы любой степени сложности.

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

1.5. Информационные объекты. Свойства и примеры

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

1) Технократический или энтропийный подход, которого придерживались родоначальники кибернетики и информатики К.Шеннон, Д. фон Нейман и Н. Винер заключается в отождествлении информации с данными. При этом игнорируется субъективный компонент информации, связанный с разными результатами обработки одних и тех же данных разными методами. Недостатки такого подхода обсуждались в предыдущей теме.

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

3) Агностический подход, объявляющий информацию фундаментальной категорией, которая не требует определения и не может быть определена. Такой подход, по сути, приводит к отказу от анализа проблемы. Хотя он отражает важную часть истины – действительно понятие информации – одно из самых фундаментальных в современной системе знаний.

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

Для введения этого понятия сделаем несколько замечаний.

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

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

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

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

Представление объекта в виде иерархии его свойств будем называть информационным образом объекта.

Аналогично мы можем определить информационный образ процесса.

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

Отметим теперь, что можно создать объект, похожий на информационный образ реального объекта, но не являющийся таковым. Например, документ Microsoft Word похож на информационный образ реальной книги, но может не иметь никакого реального прототипа. Окно программы в Windows не имеет реального прототипа, но строится по тем же принципам, что и информационный образ реального объекта.

Все объекты такого типа мы будем называть информационными объектами. Любая компьютерная информация существует в виде тех или иных информационных объектов.

Теперь мы можем дать следующее определение информации.

1) Информация существует в виде информационных объектов.

2) Информационный объект включает данные и из методы обработки этих данных.

3) Информационный объект имеет, как правило, иерархическую структуру.

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

Запись любого информационного объекта на любом носителе информации представляет собой совокупность данных, т.е. набор бит или байт. В этом смысле можно говорить, что на носителе записана некоторая информация. Однако в действительности информация существует только во время реализации методов, которые заложены в объекте. Например, документ MS Word существует только во время обработки соответствующего файла программой Microsoft Word. То же самое можно сказать про электронную таблицу, про мультимедийный или графический документ – информационный объект возникает только в тот момент, когда файлы документов начинают обрабатываться соответствующими программами.

Главная цель дальнейшего изучения курса – знакомство с основными информационными объектами и изучение их свойств. Следует помнить, что все документы, программы, окна, ярлыки, меню, панели инструментов и т.д. – это все различные информационные объекты.

Перечислим некоторые основные свойства информации, сформулировав их как свойства информационных объектов.

Подводя итог данного раздела, можно дать следующую формулировку.

Основная задача информатики - изучение и разработка методов создания и изменения различных информационных объектов при помощи компьютерных средств.

Дата добавления: 2014-01-05