Главная Случайная страница


Полезное:

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


Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






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





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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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

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

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

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

15 0049 2376

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

Date: 2015-06-07; view: 465; Нарушение авторских прав; Помощь в написании работы --> СЮДА...



mydocx.ru - 2015-2024 year. (0.005 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию