Контрольные вопросы

1. Каковы возможные подходы к определению понятия алгоритм?

2. Кто (что) может быть исполнителем алгоритма?

3. В чем особенности графического способа представления алгоритмов?

4. Каковы основные алгоритмические структуры?

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

6. Что такое алгоритмический язык?

§7. Формализация понятия «алгоритм»

7.1. Постановка проблемы

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

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

Известно несколько подходов к формализации понятия «алгоритм»:

• теория конечных и бесконечных автоматов;

• теория вычислимых (рекурсивных) функций;

• λ-исчисление Черча.

Все эти возникшие исторически независимо друг от друга подходы оказались впоследствии эквивалентными. Главная цель формализации понятия алгоритма такова: подойти к решению проблемы алгоритмической разрешимости различных математических задач, т.е. ответить на вопрос, может ли быть построен алгоритм, приводящий к решению задачи. Мы рассмотрим постановку этой проблемы и некоторые результаты теории алгоритмической разрешимости задач, но вначале обсудим формализацию понятия алгоритма в теории автоматов на примере машин Поста, Тьюринга, а также нормальных алгоритмов Маркова, а затем - основы теории рекурсивных функций. Идеи λ-исчислений Черча реализованы в языке программирования LISP (глава 3).

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

Билет №16.

Основные алгоритмические конструкции.

Элементарные  шаги  алгоритма  можно  объединить  в  следующие алгоритмические конструкции:

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

- линейная алгоритмическая конструкция.

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

- разветвляющаяся алгоритмическая конструкция.

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

- алгоритмическая конструкция «Цикл».

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

- рекурсивный алгоритм.

Рекурсивным называется алгоритм, организованный таким образом, что в процессе выполнения команд на каком-либо шаге он прямо или косвенно обращается сам к себе.

АЛЬТЕРНАТИВА

Линейный алгоритм Линейный алгоритм – описание действий, которые выполняются однократно в заданном порядке. Исполнитель выполняет действия последовательно, одно за другим в том порядке в котором они следуют. Блок-схема линейного алгоритма:

Циклический алгоритм

Циклический алгоритм – описание действий, которые должны повторяться указанное число раз или пока не выполнено заданное условие. Перечень повторяющихся действий называют телом цикла. Циклические алгоритмы бывают двух типов: Циклы со счетчиком, в которых какие-то действия выполняются определенное число раз; Циклы с условием, в которых тело цикла выполняется, в зависимости от какого-либо условия. Различают циклы с предусловием и постусловием. Циклы со счетчиком используют когда заранее известно какое число повторений тела цикла необходимо выполнить. Например, на уроке физкультуры вы должны пробежать некоторое количество кругов вокруг стадиона.

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

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

В общем случае схема циклического алгоритма с условием будет выглядеть так: Пока условие повторять действие.

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

Разветвляющийся алгоритм Во многих случаях требуется, чтобы при одних условиях выполнялась одна последовательность действий, а при других – другая. Если пошел дождь, то надо открыть зонт. Если прозвенел будильник, то надо вставать. Если встречу Сашу, то скажу ему … Если встречу Сашу, то скажу ему …, иначе зайду к нему сам. Разветвляющийся алгоритм - алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий.

Эти предложения начинаются с проверки какого-либо условия: пошел дождь, прозвенел будильник, встретил Сашу… Далее в зависимости мы либо вылиняем какое-либо действие, либо не выполняем его (или выполняем какое-то другое действие). Компьютер тоже в зависимости от какого-либо условия может выполнять или не выполнять те или иные действия. Алгоритм, в котором используется условие, получил название разветвляющегося, так как в зависимости от значения условия выбираются те или иные действия. В общем случае схема разветвляющегося алгоритма будет выглядеть так: «если условие, то действие 1, иначе действие 2» (Если встречу Сашу, то скажу ему …, иначе зайду к нему сам.). Так же можно использовать неполную форму: «если условие, то действие» (Если встречу Сашу, то скажу ему ). В этом случае не предусматривается действий на случай невыполнения условия.

 

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

Билет №20.

Киберне́тика (от др.-греч. κυβερνητική — «искусство управления»^[1]) — наука об общих закономерностях процессов управления и передачи информации в различных системах, будь то машины, живые организмы или общество.

Кибернетика  → общие закономерности управления и передачи информации

Термин «кибернетика» в современном понимании как наука об общих закономерностях процессов управления и передачи информации в машинах, живых организмах и обществе впервые был предложен Норбертом Винером в 1948 году^[2].

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

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

Более философское определение кибернетики, предложенное в 1956 году Л. Куффиньялем (англ.), одним из пионеров кибернетики, описывает кибернетику как «искусство обеспечения эффективности действия» ^[4]. Новое определение было предложено Льюисом Кауфманом (англ.): «Кибернетика — исследование систем и процессов, которые взаимодействуют сами с собой и воспроизводят себя».

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

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

Другие области исследований, повлиявшие на развитие кибернетики или оказавшиеся под её влиянием, — теория управления, теория игр, теория систем (математический эквивалент кибернетики), психология (особенно нейропсихология, бихевиоризм, познавательная психология) и философия.