Файл: Классификация языков программирования высокого уровня (Обзор и характеристика языков программирования высокого уровня).pdf

1. Пролог (PROgramming in LOGic - логическое программирование). Главное назначение языка - разработка интеллектуальных программ и систем. Пролог - это язык программирования, созданный специально для работы с базами знаний, основанными на фактах и правилах (одного из элементов систем искусственного интеллекта). В языке реализован механизм возврата для выполнения обратной цепочки рассуждений, при котором предполагается, что некоторые выводы или заключения истинны, а затем эти предположения проверяются в базе знаний, содержащей факты и правила логического вывода. Если предположение не подтверждается, выполняется возврат и выдвигается новое предположение. В основу языка положена математическая модель теории исчисления предикатов. [5]

Центральной частью Пролога являются средства логического вывода, которые решают запросы, используя заданное множество фактов и правил, к которым обращаются как к утверждениям. Пролог также не имеет деления переменных на типы и может динамически добавлять правила и факты к средствам вывода. [10]

Пролог является родоначальником большинства языков логического программирования. У него есть ряд потомков – Parlog (1983, ориентирован на параллельные вычисления), Delta Prolog и др. [10]

Пролог – это язык, предназначенный для поиска решений. Это декларативный язык, т.е. формальная постановка задачи может быть использована для ее решения. Пролог определяет логические отношения в задаче как отличные от пошагового решения этой задачи. [10]

1. HTML (HyperText Markup Language). Общеизвестный язык для оформления документов. Не является алгоритмическим языком программирования, а язык разметки гипертекста. Очень прост, содержит элементарные команды форматирования текста, добавления рисунков, задания шрифтов и цветов, организации ссылок и таблиц. Все Web-страницы написаны на языке HTML или используют его расширения. [5]
2. PHP - скриптовый язык программирования, применяющийся для создания сайтов. Важное его достоинство языка php - это создания динамических веб-сайтов, работа с базами данных (mysql). [5]

Во второй главе были рассмотрены самые распространённые языки программирования высокого уровня.

Глава 3. Понятие об алгоритме

Слово «Алгоритм» происходит от algorithmi – латинского написания имени аль-Хорезми, под которым в средневековой Европе знали величайшего математика из Хорезма (город в современном Узбекистане) Мухаммеда бен Мусу, жившего в 783-850 гг. В своей книге «Об индийском счете» он сформулировал правила записи натуральных чисел с помощью арабских цифр и правила действий над ними столбиком. В дальнейшем алгоритмом стали называть точное предписание, определяющее последовательность действий, обеспечивающую получение требуемого результата из исходных данных. Алгоритм может быть предназначен для выполнения его человеком или автоматическим устройством. Создание алгоритма, пусть даже самого простого, - процесс творческий. Он доступен исключительно живым существам, а долгое время считалось, что только человеку. Другое дело – реализация уже имеющегося алгоритма. Ее можно поручить субъекту или объекту, который не обязан вникать в существо дела, а возможно, и не способен его понять. Такой субъект или объект принято называть формальным исполнителем. [9]

Примером формального исполнителя может служить стиральная машина-автомат, которая неукоснительно исполняет предписанные ей действия, даже если вы забыли положить в нее порошок. Человек тоже может выступать в роли формального исполнителя, но в первую очередь формальными исполнителями являются различные автоматические устройства, и компьютер в том числе. [9]

Каждый алгоритм создается в расчете на вполне конкретного исполнителя. [9]

Те действия, которые может совершать исполнитель, называются его допустимыми действиями. Совокупность допустимых действий образует систему команд исполнителя. Алгоритм должен содержать только те действия, которые допустимы для данного исполнителя. [9]

Свойства алгоритма.

1. Дискретность. Алгоритм должен представлять процесс решения задачи как последовательность выполнения простых действий (шагов, этапов). При этом для выполнения каждого действия алгоритма требуется время. [8]
2. Детерминированность (Однозначность). Каждое действие (шаг, этап) должно быть четким, однозначным, исключающим произвольное толкование и не оставляющим места для двусмысленности. Выполнение алгоритма носит, по сути, механический характер и не требует никаких дополнительных указаний. [8]
3. Результативность. Алгоритм должен приводить к решению задачи или сообщению, что задача решений не имеет за конечное число шагов. [8]
4. Конечность. Каждое отдельное действие, как и весь алгоритм должны иметь возможность реального исполнения. Поэтому алгоритм имеет придел, т. е. конечен. [8]
5. Массовость. Алгоритм разрабатывается в общем виде так, чтобы его можно было применять для класса задач, различающихся только исходными данными. При этом исходные данные выбираются из некоторой области, которая называется областью применяемости алгоритма. Например, для решения квадратного уравнения ax+bx+c=0, коэффициенты действительные числа, а ≠ 0, и а, в, с – различные. [8]

Способы записи алгоритмов.

I. Словесный способ.

Словесный способ записи алгоритмов представляет собой последовательное описание основных этапов обработки данных и задается в произвольном изложении на естественном языке. [1]

В качестве примера рассмотрим запись алгоритма нахождения наибольшего общего делителя двух натуральных чисел (т и п). Алгоритм может быть записан в следующем виде [1]:

• если числа равны, то необходимо взять любое из них в качестве ответа, в противном случае - продолжить выполнение алгоритма;
• определить большее из чисел;
• заменить большее число разностью большего и меньшего чисел;
• повторить алгоритм сначала.

Способ основан на использовании общепринятых средств общения между людьми и с точки зрения написания трудностей не представляет. Такой способ записи удобно использовать на начальном этапе алгоритмизации задачи. К недостаткам словесного способа записи можно отнести следующее [1]:

1) полное подробное словесное описание алгоритма получается очень громоздким;

2) естественный язык допускает неоднозначность толкования отдельных инструкций;

3) при переходе к этапу программирования требуется дополнительная работа по формализации алгоритма, так как словесное описание может быть понятно человеку, но "непонятно" ПК.

Поэтому словесный способ записи алгоритмов не имеет широкого распространения.

II. Графический способ (блок-схем).

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

Запись блоков [7]:

1. Начало и конец алгоритма (программы):

1. Блок присваивания:

1. Ввод данных с клавиатуры:

1. Вывод информации на экран (на печать):

1. Блок ветвления (проверки условия):

1. Блок цикла с параметром:

1. Нумерация блоков, значок перехода на блок с указанным номером:

III. Запись с помощью псевдокода.

Псевдокод - это система обозначений, предназначенная для неформального представления идей в процессе разработки алгоритмов. [6]

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

Альтернатива выражается на псевдокоде следующей структурой: if (условие) then (действие) else (действие).

Сокращенный синтаксис этого конструкта, когда не предусмотрено действие для варианта else выглядит так [6]:

if (условие) then (действие).

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

Эта инструкция предписывает проверить условие и, если оно верно, выполнить действие, а затем вновь проверить условие. Если при очередной проверке условие оказывается неверным, следует перейти к инструкции, следующей за данной структурой [6]:

while (условие) do (действие).

Цикл-do на псевдокоде имеет следующий вид: repeat (действие) until (условие)

Оператор присваивания. Часто желательно ссылаться на некоторые значения с помощью описательных имен. Для установки подобных связей будет использоваться следующая конструкция присваивания [6]:

assign имя the value выражение,

здесь параметр имя - это описательное имя, а параметр выражение описывает значение, связываемое с этим именем. Например: assign Итог the value Цена + Налог

При ее выполнении результат суммирования значений переменных Цена и Налог будет связан с именем Итог .

Процедуры. Используются для описания действий, которые могут выступать в роли вспомогательных программ в других приложениях. Такие программные элементы имеют несколько различных названий, а именно: подпрограммы, процедуры и функции. [6]

В псевдокоде для обозначения заголовка, по которому можно распознать данный блок псевдокода используется термин procedure: procedure имя,

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

Процедуры должны разрабатываться так, чтобы быть как можно более общими. Например, процедура сортировки списков имен должна быть способна сортировать любой список, а не какой-то один определенный. Поэтому она должна быть написана таким способом, чтобы подлежащий сортировке список не определялся в самой процедуре, а передавался ей в качестве входных данных, представленных некоторым обобщенным именем. [6]

Такие обобщенные имена в псевдокоде выделяют угловыми скобками и указывают их в круглых скобках, а той же строке, в которой определяется имя данной процедуры. В частности, процедура Сортировка, предназначенная для сортировки произвольных списков имен, будет начинаться следующей инструкцией: procedure Сортировка(<список>). [6]

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

Виды алгоритмов.

1. Алгоритм последовательного поиска.

Этот алгоритм решает задачу поиска в списке некоторого заданного значения. Он позволяет установить, есть ли заданное значение в списке. Если это значение в списке присутствует, поиск будет считаться успешным, в противном случае - неудачным. [6]

При этом считается, что список отсортирован согласно некоторому правилу, позволяющему упорядочить его элементы. Например, если это список имен, то имена в нем расположены в алфавитном порядке. Если же это список числовых значений, то его элементы расположены в порядке возрастания. В результате получается процедура, текст которой приведен ниже. [6]

procedure Поиск (<список>, <искомое значение>) if (список пуст)

then (объявить поиск неудачным)

else

(выбрать как <проверяемое значение> первый

элемент списка)

while (<искомое значение> > <проверяемое значение> и есть непроверенные элементы) do

(выбрать следующий элемент списка как <проверяемое значение>) if (<искомое значение> =

<проверяемое значение>)

then (объявить поиск успешным) else (объявить поиск неудачным)

По окончании выполнения структуры while искомое значение либо будет найдено, либо выяснится, что его нет в списке. В любом случае успешность поиска можно установить, сравнивая искомое значение с проверяемым. Если они эквивалентны, поиск объявляется успешным. Для полной уверенности в правильности программы она помещается в предложение else инструкции if. [6]

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

Таким образом, алгоритм последовательно рассматривает все элементы списка. В силу своей простоты он часто применяется к коротким спискам или когда это необходимо. Однако в случае длинных списков этот метод оказывается менее эффективным, чем другие. [6]

2. Алгоритм двоичного поиска.

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