Понятие алгоритма. Принципы алгоритма.

⇐ ПредыдущаяСтр 3 из 11Следующая ⇒

Под этим интуитивно понятным на первый взгляд словом кроется огромная теория и годы усиленных трудов многих математиков. Казалось бы, сформулировать определение алгоритма проще простого: алгоритм — четкое и понятное исполнителю указание выполнить последовательность действий, направленных на получение какого-то результата. Однако, существуют такие задачи, решение которых опирается на некую последовательность действий, которая укладывается в данное определение, но говорят, что для решения этой задачи не существует алгоритма. Например, знаменитая задача коммивояжера, в которой имеется таблица стоимости проезда из одного города в другой. Требуется посетить все города, но по такому маршруту, чтобы стоимость путешествия была наименьшей. Единственным решением на сегодняшний день является перебор всевозможных маршрутов с замером стоимости. Всего таких маршрутов будет n!, где n — число городов. Если число городов будет 100, то перебрать нужно будет 100! вариантов, а это число больше, чем количество частиц во всей Вселенной. Понятно, что решить эту задачу невозможно, хотя для того, чтобы ее решить, нужно выполнять последователь действий, похожих по определению на алгоритм.

Для того, чтобы утверждать, что задача имеет алгоритм, достаточно просто предъявить его; а для того, чтобы утверждать, что задача не имеет решения, необходимо это доказать. Для доказательства используют специальные теории (для этого используется абстрактная машина Тьюринга или абстрактная машина Поста).

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

1. Если мы ему скажем «пойди в магазин и купи чего-нибудь», то в итоге мы не получим результата, потому что нарушается свойство определенности. Алгоритм не должен содержать команды, смысл которых может быть понятен неоднозначно.

2. Если мы скажем ребенку «go to the shop and buy a bread», то он вряд ли вообще что-то сделает, так как скорее всего он не поймет наших слов. Алгоритм должен быть понятен исполнителю, то есть команды должны содержаться в системе команд исполнителей (СКИ).

3. Мы можем сказать «пойди в магазин и купи хлеба». А если в магазине хлеба нет, то мы останемся без хлеба. Значит, алгоритм должен выдавать результат.

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

5. Если мы скажем ребенку «понимаешь, нет хлеба, поэтому было бы неплохо, если бы ты сходил в этот магазин или какой-то другой, если считаешь, что тот, куда ты пошел в первый раз по каким-то причинам тебе не подходит. Только не ходи в те, где ты уже был», то получится, что мы рассказали ребенку целую историю и в итоге в нем не содержится именно последовательности действий. Алгоритм должен содержать именно последовательность действий, то есть быть дискретным.

6. Наконец, наши команды должны «посылать» ребенка не только за хлебом, но, например, и за молоком, то есть для любых входных данных мы должны получить требуемый результат.

Итак, свойства алгоритма:

1) определенность;

2) понятность;

3) результативность;

4) конечность;

5) дискретность;

6) массовость.

Языки программирования: назначение, виды. Компиляция, интерпретация, трансляция.

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

Первые программы появились едва ли позже создания компьютера. Первым программистом принято считать знаменитую Аду Лавлейс, дочь лорда Байрона, которая так была сильно увлечена математикой и трудами Чарльза Бэббиджа. Чарльз Бэббидж вошел в историю благодаря конструированию «Аналитической машины», которая, исходя из ее проектирования, должна была быть очень похожа по своей структуре на современный компьютер. Она должна была иметь устройство для ввода и вывода данных, «накопитель», в которых должны были размещаться промежуточные результаты, «мельницу» для вычислений, управляющее устройство. Юная Ада буквально подхватила идею создания этой машины и помимо новых идей по конструированию узлов и механизмов, она занималась разработкой программ к еще не существующей машине. Надо отметить, что после себя эти два замечательных человека оставили только гору чертежей и схем. Сама же машина была построена много позже, в XX века группой студентов в дань уважения «отцу компьютерной техники».

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

15 0049 2376

Здесь первое число означает код операции, а два других — номера ячеек памяти, откуда нужно взять значения. Например, если «15» - код операции сложения, то запись означает, что нужно было взять число, лежащее в ячейке с номером 0049 и сложить с числом, лежащем в ячейке с номером 2376 и положить результат в ячейку с номером 0049. Понятно, что в этих числах легко можно было запутаться. Разобраться в таких записях иногда просто невозможно. Нужно помнить все коды операций, кроме того, нужно помнить все адреса ячеек, где лежат данные. Кроме того, все эти команды записывались в двоичной системе счисления. Конечно же, ни о каком удобстве программирования говорить в этом случае не приходится. Зато процессору такие команды не просто понятны, но и являются единственно возможными. Процессору команды понятны, а человеку совершенно нет. Чтобы как-то приблизить программирование к человеку, были созданы специальные языки с транслятором^{^[1]} типа Ассемблер (англ. assembler — сборщик). Такие языки назывались языками Ассемблера. Эти языки имели общую структуру, которая состояла из метки, кода и комментария. Код состоял из так называемой мнемоники и списка аргументов. Мнемоника — трех-, четырехбуквенное сокращение команды, аналог кода операции. Список аргументов записывался через запятую, их количество зависело от конкретной операции. В этом случае команды могли выглядеть так:

MOV a, 15

MOV b, 35

Эти команды означают, что переменной «а» нужно присвоить значение 15, а переменной «b» - значение 35. Аналогом команды из вышеобозначенного примера могла бы быть команда

ADD a, b

что означало бы, «сложить число, лежащее в ячейке «а» с числом в ячейке «b», а результат положить в ячейку «а».

Как видно из примера, язык очень сильно напоминает машинный, но здесь имеются некоторые «человеческие» элементы: например, команда «MOV» созвучна с английским словом «move», что означает «передвинуть», а команда «ADD» созвучна со словом «add» (прибавить). Во-вторых, здесь уже нет адресов ячеек, а есть переменные. Дать переменной конкретный адрес ячейки уже не задача программиста, а задача программы-транслятора. Таким образом, программист избавлен от проблемы поиска свободных ячеек памяти, за него это делает машина. Отметим, что в этом случае язык уже не совсем машинный, и для компьютера эти команды незнакомы, ему их нужно переводить (транслировать). Но все же этот язык очень похож на машинный. Такие языки называют языками программирования низкого уровня.

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

If n< 15 then n: =n+3 else n: =n-2,

в переводе с английского звучит так: «если n < 15, то n: =n+3, иначе n: =n-2». На языке программирования Pascal эта фраза означает «если n < 15, то к n прибавать 3, иначе от n отнять 2». Почти как на английском. Очевидно, что с помощью этого языка можно писать программы легче, такие программы легко понимаемы. Кроме того, языки программирования высокого уровня позволяют работать с любыми данными, а не только с числами. Еще стоит отметить, что если языки Ассемблера были предназначены для процессора определенного типа (поэтому неверно говорить «язык Ассемблер», так как ассемблер — это только программа-транслятор), то языки программирования высокого уровня не зависят от типа компьютера.

Языки программирования высокого уровня делятся на 2 типа:

императивные

декларативные

Программа представляет собой алгоритм решения какой-то задачи. Алгоритм описывается пошагово. Например, «для того, чтобы перейти дорогу, нужно:

Подойти к проезжей части;
Посмотреть на светофор;
Если светофор зеленый,

посмотреть по сторонам и

если нет автомобилей, пересекающих проезжую часть, то перейти проезжую часть
иначе подождать, пока машины проедут;

перейти проезжую часть.

иначе подождать одну секунду вернуться к пункту 2;
перейти проезжую часть.»

Примерами могут служить такие языки, как

Pascal
BASIC
Delphi
C++, C#

В них по сути нет алгоритма, есть только описание данных в их взаимосвязи. На основании полученных данных компьютер должен сформулировать ответ. Например: «на проезжей части 3 автомобиля: красный, синий и зеленый; светофор стоит в пяти метрах, на нем горит красный свет; 2 автомобиля движутся, один стоит. Можно ли мне перейти через проезжую часть? » Примерами декларативных языков программирования служат:

Prolog
Lisp
SQL

Транслятор

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

1) интерпретатор;

2) компилятор.

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

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

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

Принципы Фон-Неймана.

Уже при конструировании первой настоящей ЭВМ перед математиками встал вопрос: а что же такое ЭВМ собственно? Какое устройство является ЭВМ, а какое может называться только лишь вычислителем? Ответ на этот вопрос дал американский математик, венгр по происхождению Джон фон Нейман.

В 1946 году вместе с Г.Гольдстейном и А.Берксом фон Нейман написал и выпустил отчет " Предварительное обсуждение логической конструкции электронной вычислительной машины" (исследовательская группа занималась разработкой машины EDVAC). Поскольку имя фон Неймана как выдающегося физика и математика было уже хорошо известно в широких научных кругах, все высказанные положения в отчете приписывались ему.

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

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

2. ЭВМ работает только с двоичной системой счисления. Машина MarkI использовала электромеханические реле на 10 положений и работала в десятичной системе счисления. Такая архитектура не может быть удачной. Самый надежный способ работы с информацией – использовать только 2 сигнала: включено и выключено.

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

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

5. ЭВМ укладывается в схему

УСТРОЙСТВО ВВОДА-ВЫВОДА

⇐ Предыдущая 1 234 5 6 7 8 9 10 Следующая ⇒