Языки программирования

                                           Языки программирования

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

Язык программирования[programming language] - формализованный язык,предназначенный для описания алгоритмов решения задач на ЭВМ[20].

Программирование бывает логическое, параллелльное, функциональное, системное, процедурно-ориентированное, и т.д. Логическое(продукционное) программирование[logical programming] - программирование,состоящее в описании решаемой задачи на точном логическом языке,т.е. указании,что необходимо сделать,не уделяя существенного внимания тому,как это нужно сделать.Параллельное программирование [concurrent programming ]-  разработка программ,содержащих параллельно выполняемые секции или параллельная обработка.Объектно-ориентированное программирование[object - oriented programming] - решение задач пользователя  в диалоговом режиме в терминах объектов предметной области или систематическое применение  абстракции данных.Процедурно -ориентированное программирование [procedure - oriented programming] - программирование на процедурно-ориентированном языке. Системное программирование[system  programming] - разработка общего программного обеспечения - операционных систем,систем программирования,а также пакетов прикладных программ общего назначения. Функциональное  программирование[functional  programming] - метод программирования ,основанный  на разбиении алгоритма на отдельные функциональные модули и описании их связей и взаимодействия.В этом методе для каждого конкретного применения вводится класс абстрактных объектов(структур данных),множество операций (функций, преобразований) над абстрактными объектами и множество композиций над этими операциями.

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

 

 

1. Обзор языков программирования

 

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

I.Языки функционального и логического  программирования: FUN, LISP,Multilisp, ML, SML, Hope, Miranda,Alfl,ParAlfl,APL,PROLOG.

II.Языки процедурного программирования:Алгол,  Фортран, Кобол,Ада,Пл/1, Фокал,Бейсик  Паскаль, и т.д.

III.Языки системного программирования: Си,С++, Ассемблер.

Языки программирования   соответственно типу программирования  делятся на группы: языки  логического программирования,системного программирования, процедурно-ориентированного программирования, функционального программирования, проблемно- ориентированного  программирования. Язык  логического программирования (продукционный язык) [rule-oriented language]- язык программирования,основанный  на принципе задания совокупности правил без явного указания последовательности их применения.Системный язык [system language]- язык общения оператора ЭВМ с вычислительной системой,представляющий собой совокупность команд оператора и сообщений системы.Процедурно-ориентированный (процедурный) язык[procedure - oriented (procedural)language] - проблемно-ориенти-рованный язык, который облегчает выражение процедуры как точного алгоритма. Язык функционального программирования (функциональный язык)[functional  language] - декларативный язык программирования, основанный на понятии функции. Функции в языке задают зависимость,но не определяют порядок вычислений.Проблемно-ориентированный  язык [problem  - oriented    language] - язык программирования, предназначенный для решения определенного класса задач(проблем).

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

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

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

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

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

Для программирования  технических задач применяются такие языки программирования высокого уровня(машинно-независимые или проблемно-ориентированные ) как Алгол, Фортран, Кобол, Пл/1, ПЛ/М, Ада,Фокал, Бейсик, Паскаль, , Модула-2,Си и другие языки[ 2- 50 ].

Язык Бейсик и Фокал применяются для решения  научно-технических задач,экономических расчетов,в области автоматизации научного эксперимента,сфере обучения.Языки обладают одинаковыми вычислительными возможностями, однако язык Фокал имеет ряд преимуществ:он обладает большими возможностями для работы с периферийными оборудованиями,расширенными функциями отладки и редактирования,возможностью трассировки.Языки Фокал и Бейсик обладают всеми свойствами,которые присущи диалоговым языкам такого рода,т.е. простотой и легкостью для изучения;возможностью использования обозначений,подобным обычным математическим, способностью работать как в диалоговом,так и в программном режимах, наличием библиотеки стандартных математичесикх функций и возможностью ее расширения,средств для редактирования и отладки программ, команд для работы со стандартными периферийными оборудованиями; диагностикой ошибок. Яык Кобол применяется для решения экономических задач.Язык Паскаль имеет ряд преимуществ перед Бейсиком, и в первую очередь это касается его структурных свойств. Структурированные алгоритмы удобнее всего реализовывать на алголоподобных алгоритмических языках Пл/1,Паскаль,Ада и др. Структурированные программы на Фортране получаются длиннее, но  достоинства структурирования проявляются на больших,сложных программах. В языке Паскаль  присутствуют все необходимые управляющие конструкции для программирования структурным методом.Языки процедурного программирования используются для решения задач вычислительного характера.

 

 

 СОВРЕМЕННЫЕ  АЛГОРИТМЫ

 

1. Алгоритмы вида «разделяй  и властвуй» 

 

Алгоритмы вида «разделяй  и властвуй»  обеспечивают компактный  и мощный инструмент решения различных  задач.

Подсчет итераций  алгоритмов  вида «разделяй и властвуй»   не очень прост: он зависит от рекурсивных  вызовов, от подготовительных и завершающих действий. Рассмотрим следующий пример алгоритма вида «разделяй и властвуй» .

 

DivideAndConquer(data, N, solution)

Data           набор входных данных

N                количество значений в наборе

Solution      решение задачи

 

If(N<=SizeLimit) then

  DirectSolution(data, N, solution)

  Else

  DivideInput(data, N, smallerSets, smallerSizes, numberSmaller)

For i=1 to numberSmaller do

  DivideAndConquer(smallerSets[i], smallerSizes[i], smallSol[i])

end for

  CombineSolutions(smallSol, numberSmaller, solution)

end if

 

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

Ниже представлен алгоритм вычисления факторила.

Factorial(N)

N              число, факторил которого нам нужен

Factorial    возвращает целое число

 

If(N=1) then

  Return 1

Else

   Smaller = N-1

answer= Factorial(smaller)

return(N*answer)

  end if

 

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

 

 

2.  Алгоритмы  поиска и выборки

 

2.1. Последовательный  поиск

 

При последовательном поиске мы всегда будем предполагать, что список не отсортирован, поскольку некоторые  алгоритмы на отсортированных списках показывают лучшую производительность. Будем предполагать, что  элементы списка  имеют номера от 1 до N.

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

 

SequentialSearch(list, target, N)

List            список  для просмотра

Target        целевое значение

N                число элементов в списке

 

for i=1 to N do

  If(target=list[i])

   return i

      end if

end for

return o

 

 

 

2.2. Двоичный поиск

 

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

 

BinarySearch(list, target, N)

list                список для просмотра

target            целевое значение

N                    число элементов в списке

 

 

start=1

end=N

while start<=end do

       middle=(start+end)

      select(Compare(list[middle], target)) from

     case -1:start=middle+1

    case 0:return middle

     case 1: end=middle-1

end select

end while

return 0

 

Возвращает ли этот алгоритм правильный результат ?

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

 

 

 

 

2.3. Выборка

 

Иногда  вместо записи  с некоторым  конкретным   значением поля нас интересует запись с наибольшим,  наименьшим или средним значением этого поля.  То есть нас может интересовать запись  с К-ым по величине значением поля. Один из способов найти такую запись состоит в том, чтобы найти наибольшее значение   в списке  и поместить его в конец списка. Затем мы можем найти наибольшее значение в оставшейся части списка, исключая уже найденное . В результате имеем второе по величине значение списка, которое можно поместить на второе с конца место в списке. Повторив эту процедуру К раз, найдем К-ое по величине значение и имеем следующий алгоритм:

 

FindKthLargest(list, K, N)

List          список для просмотра

N             число элементов в списке

K             порядковый номер по величине требуемого элемента 

 

 

for i=1 to K do

   largest=list[i]