Алгоритмы; эволюция и классификация языков программирования

Лекция № 1 Алгоритм и его свойства. Способы записи алгоритмов. Эволюция и классификация языков программирования Понятие алгоритма такое же основополагающее для информатики, как и понятие информации. Именно поэтому важно в нем разобраться. Название "алгоритм" произошло от латинской формы имени величайшего среднеазиатского математика Мухаммеда ибн Муса ал-Хорезми (Alhorithmi), жившего в 783—850 гг. Алгоpитм — заранее заданное понятное и точное пpедписание возможному исполнителю совеpшить определенную последовательность действий для получения решения задачи за конечное число шагов. Понятие алгоритма является не только одним из главных понятий математики, но одним из главных понятий современной науки. Более того, с наступлением эры информатики алгоритмы становятся одним из важнейших факторов цивилизации. Исполнитель алгоритма — это некоторая абстрактная или реальная (техническая, биологическая или биотехническая) система, способная выполнить действия, предписываемые алгоритмом. Исполнителя хаpактеpизуют: • сpеда; • cистема команд; • элементаpные действия; • отказы. 1. Сpеда (или обстановка) — это "место обитания" исполнителя. Напpимеp, для исполнителя человека – это общество или природа, для робота – помещение, в котором он функционирует. 2. Система команд. Каждый исполнитель может выполнять команды только из некотоpого, стpого заданного списка — системы команд исполнителя. Для каждой команды должны быть заданы условия пpименимости (в каких состояниях сpеды может быть выполнена команда) и описаны pезультаты выполнения команды. Напpимеp, команда Pобота "идти" может быть выполнена, если перед Pоботом нет стены или иных препятствий. Человек-водитель может вести общественный транспорт только в соответствии с дорожными знаками и отсутствии препятствий на дорогах. 3. После вызова команды исполнитель совеpшает соответствующее элементаpное действие. 4. Отказы исполнителя возникают, если команда вызывается пpи недопустимом для нее состоянии сpеды. Например, робот не может идти, так как перед ним стена. Водитель не может ехать, так как на дороге пробка из-за аварии. В информатике универсальным исполнителем алгоритмов является компьютер Определение алгоритма Происхождение слова «алгоритм» связано со словом «algorithmi» - латинским написанием имени аль-Хорезми, под которым в средневековой Европе знали величайшего математика из Хорезма (город в современном Узбекистане) Мухаммеда бен Мусу, жившего в 783-850 гг. В своей книге «Об индийском счете» он сформулировал правила записи натуральных чисел с помощью арабских цифр и правила действий над ними столбиком. Поэтому и наполнение термина «алгоритм» было следующим: операции над числами. Через века старое, прежнее понимание этого термина утратилось. Алгоритм – это одно из фундаментальных понятий математики и вычислительной техники. Под алгоритмом понимают точное предписание, определяющее содержание и порядок действий, которые необходимо выполнить над исходными и промежуточными данными для получения конечного результата при решении всех задач определенного типа. Значение слова «алгоритм» очень схоже со значением слов «рецепт», «метод», «процесс». Однако, в отличие от рецепта или процесса, алгоритм характеризуется следующими свойствами: дискретностью, массовостью, определенностью, результативностью, формальностью. Дискретность – это свойство алгоритма, характеризующее его структуру: каждый алгоритм состоит из отдельных законченных действий, говорят: «Делится на шаги». Массовость – применимость алгоритма ко всем задачам рассматриваемого типа, при любых исходных данных. Например, алгоритм решения квадратного уравнения в области действительных чисел должен содержать все возможные исходы решения, т.е. рассмотрев значения дискриминанта, алгоритм находит либо два различных корня уравнения, либо два равных, либо делает вывод о том, что действительных корней нет. Определенность (детерминированность, точность) – свойство алгоритма, указывающее на то, что каждый шаг алгоритма должен быть строго определен, и не допускать различных толкований; также строго должен быть определен порядок выполнения отдельных шагов. Помните сказку про Ивана – царевича? « Шел Иван-царевич по дороге, дошел до развилки. Видит большой камень, на нем надпись: « прямо пойдешь- голову потеряешь, направо пойдешь – жену найдешь, налево пойдешь – разбогатеешь». Стоит Иван и думает, что дальше делать» Таких инструкций алгоритм содержать не может. Результативность – свойство, состоящее в том, что любой алгоритм должен завершаться за конечное (может быть очень большое) число шагов. Вопрос о рассмотрении бесконечных алгоритмов остается за рамками теории алгоритомов. Формальность – это свойство указывает на то, что любой исполнитель, способный воспринять и выполнить инструкции алгоритма, действует формально, т.е. отвлекается от содержания поставленной задачи и лишь строго выполняет инструкции. Рассуждать «что, как и почему?» должен разработчик, а исполнитель формально (не думая) поочередно исполняет предложенные команды и получает необходимый результат. Для записи алгоритмов существует множество способов, отличающихся по простоте, наглядности и т.д. В практике программирования наибольшее распространение получили блок-схемы и алгоритмические языки. Применяются также словесное описание и псевдокод. Словесное описание представляет структуру алгоритма на естественном языке. Например, инструкция для любого бытового прибора. Этот способ не имеет широкого распространения, т.к. строго не формализуем, страдает многословностью. Псевдокод – описание структуры алгоритма на естественном, частично формализованном языке, позволяющее выявить основные этапы решения задачи, перед точной его записью на языке программирования. В псевдокоде используются некоторые формальные конструкции и общепринятая математическая символика. Единых правил для записи псевдокода не существует, поэтому возможны различные псевдокоды, отличающиеся набором используемых слов и конструкций. Пример: 1)Ввод чисел а, в. 2)Вычисляем сумму а+в. 3)Вывод. 4) Конец. Блок –схема – это графическое представление алгоритма, дополненное элементами словесной записи. Каждый пункт алгоритма отображается на блок-схеме некоторой геометрической фигурой-блоком. Символика блок-схем: Операторы ввода-вывода. В операторах ввода – вывода записываются имена тех переменных, значения которых должны вводиться в оперативную память или выводиться из нее. Ввод А, В, С Если в программе встречается этот оператор, то процессор переходит в режим ожидания до тех пор, пока через клавиатуру не будут введены три числа, разделенные запятыми или пробелами. После ввода последнего числа надо нажать . Числа кодируются, т.е. переводятся из обычного вида во внутренний код ЭВМ. Закодированные числа помещаются в ячейки памяти с символическими именами А, В, С. Печать ‘x = ’ Печатаются символы x =. Печать x, y Из ячеек с именами x и y выбираются числа. Они преобразуются из машинного кода к обычному виду (декодируются и выводятся на экран монитора). Печать ‘x = ‘, x Если x имеет значение, равное 5, то на экран выводится строка x = 5 Операторы присваивания. С = А+В Содержимое ячеек памяти с символическими адресами A и Β суммируются. Результат записывается в ячейку с символическим адресом C. X = X+DX Содержимое ячеек памяти с символическими адресами X и DX суммируется. Старое значение ячейки X будет стерто, будет записано новое значение переменной X. I = I+1 Говорят, что значение переменной I увеличилось на 1 Y = sin(x) В ячейке с символическим адресом x записано значение угла, по которому вычисляется значение синуса и результат записывается в ячейку Y 5 = 2+3 Ошибка, т.к. слева от символа = не может стоять константа. А+В=С Ошибка, т.к. слева от знака = может находиться только переменная Разветвление В блоке стоит логическое выражение, значением которого может быть истина или ложь. В зависимости от значения выражения, дальнейший ход выполнения программы развивается в одном из двух направлений. Подпрограмма Группа операторов, которые решают часть задачи, объединяются в подпрограмму. Алгоритм решения описывается в виде отдельной блок-схемы. Разделение программ на подпрограммы играет важную роль в структурном программировании. Соединитель В нем записывается любой символ. Им пользуются в том случае, если соединительная линия не может быть доведена до следующего блока. Продолжением этой линии является соединитель с тем же символом. Комментарии можно записывать возле любого блока. Рассмотрим пример алгоритма – алгоритм отыскания минимума и максимума в любой конечной последовательности из n вещественных случайных чисел а1, а2, а3, а4, ….,аn. При небольшом количестве чисел достаточно беглого взгляда, чтобы указать максимум и минимум. Однако, если n велико, задача усложняется. Поэтому необходимо придерживаться определенной системы. Например, взять в качестве начального значения как для максимума, так и для минимума первое число, далее последовательно перебирать числа и сравнивать каждое из них с установленным к текущему моменту значением максимума. Если очередное число превышает максимум, считать его новым значением максимума (прежнее значение «забыть»), после чего можно переходить к новому числу. Если анализируемое число не больше максимума, то сравнить его с установленным е текущему моменту значением минимума. Если число оказывается меньше минимума, считать его новым значением минимума и перейти к следующему числу; если число не меньше минимума, просто перейти к анализу следующего числа. Перебрав таким образом все числа, получим окончательное значение максимума и минимума. Блок – схему этого алгоритма можно представить следующим образом. Элементарные шаги алгоритма можно объединить в следующие алгоритмические конструкции: линейные, разветвленные, циклические и рекурсивные. Из рассмотренных выше блоков можно собирать различные алгоритмы (структуры). Основные понятия и правила построения структур не зависят от конкретного содержания программы. Структурная блок-схема – это блок-схема, которая может быть выражена как композиция из четырех элементарных блок-схем: композиции (линейный алгоритм), выбора (разветвление), цикл с предусловием, цикл с постусловием (циклический алгоритм). Рекурсивным называется алгоритм, организованный таким образом, что в процессе выполнения команд на каком-либо шаге он прямо или косвенно обращается сам к себе. В более широком плане структурное программирование допускает большое разнообразие элементарных структур управления, чем предложенные четыре: оператор CASE, выполнение одной альтернативы, преждевременное окончание цикла: При решении задач на компьютере в первую очередь необходимо знание методов решения задач, а уже во вторую очередь умение составлять алгоритмы, пользуясь приведенными выше понятиями и конструкциями. Сущность алгоритмизации не в том, что решение задачи представляется в виде набора элементарных операций, а в том, что процесс решения задачи разбивается на два этапа: составление алгоритма плюс кодирование программы и ее выполнение. Первый этап осуществляет человек, второй – компьютер. Методы разработки алгоритма Существует весьма большое количество всевозможных приемов и методов разработки алгоритмов. Однако среди имеющегося разнообразия этих методов можно выделить небольшой набор основных, в том смысле, что методы из такого набора применяются часто и лежат в основе многих процедур и алгоритмов. К основным методам можно отнести: 1. метод частных целей – сложная задача сводится к последовательности более простых задач. 2. метод подъема – начинается с принятия начального предположения или построения начального решения задачи. Затем начинается (насколько возможно) быстрое движение «вверх» от начального уровня по направлению к лучшим решениям. Когда алгоритм достигает точки, из которой больше невозможно двигаться «наверх», он останавливается. 3. программирование с отходом назад – Основой программ искусственного интеллекта, независимо от того, к чему он прилагается – программирование игр, выбору решений, распознование образов и т.п., - является программирование перебора вариантов. Программирование перебора вариантов – это сложная задача, т.к. алгоритмы перебора ищут решения не по заданным правилам вычислений, а путем проб и ошибок, и схема не укладывается в схемы циклов, имеющихся в языках программирования. Ситуация зачастую осложняется тем, что прямыми методами перебор всех возможных вариантов невозможно осуществить из-за их огромного количества. Метод программирования с отходом назад позволяет осуществить организованный исчерпывающий поиск требуемого решения задачи. При этом часто удается избежать перебора всех возможных вариантов 4. алгоритмы ветвей и границ – применяются для решения переборных задач и ориентированы на поиск оптимального решения из конечного множества возможных решений – вариантов. Языки программирования Язык программирования служит двум связанным между собой целям: он дает программисту аппарат для записи (кодирования) действий, которые должны быть выполнены, и формирует концепции, которыми пользуется программист, размышляя о том, что делать. Первой цели отвечает язык близкий к машине, который позволяет программисту легко оперировать основными машинными ресурсами. Второй цели отвечает язык близкий к решаемой задаче, который позволяет выражать просто и коротко любые концепции ее решения. Каждый конкретный компьютер способен работать с программами, написанными на его собственном машинном языке. Существует почти столько же разных машинных языков, сколько и компьютеров, но все они суть разновидности одной идеи: простые операции в двоичных числах производятся с максимально высокой скоростью. Можно писать программы непосредственно на машинном языке, хотя это и сложно. На заре вычислительной техники (в начале 1950-х г.г.), машинный язык был единственным языком. Для спасения программистов от сурового машинного языка программирования, были созданы языки высокого уровня (немашинные языки), которые стали своеобразным связующим звеном между человеком и машинным языком компьютера. Языки высокого уровня работают при помощи трансляционных программ, которые вводят исходный код (гибрид английских слов и математических выражений), и заставляет компьютер выполнять соответствующие команды, которые даются на машинном языке. Классификация языков программирования Машинно–ориентированные языки – это языки, наборы операторов и изобразительные средства которых существенно зависят от особенностей ЭВМ (внутреннего языка, структуры памяти и т. д.). Эти языки обладают всеми возможностями и особенностями машинно–зависимых языков: • высокое качество создаваемых программ (компактность и скорость выполнения); • возможность использования конкретных аппаратных ресурсов; • предсказуемость объектного кода и заказов памяти; • для составления эффективных программ необходимо знать систему команд и особенности функционирования данной ЭВМ; • трудоемкость процесса составления программ, плохо защищенного от появления ошибок; • низкая скорость программирования; • невозможность непосредственного использования программ, составленных на этих языках, на ЭВМ других типов. Машинно-ориентированные языки по степени автоматического программирования подразделяются на классы: • Машинные языки обеспечивают выполнение команд (операций над соответствующими операндами). В новых моделях ЭВМ для упрощения программирования сложные команды, приближающиеся по своим функциональным действиям к операторам алгоритмических языков программирования, реализуются аппаратным путем. • Языки символического кодирования так же являются командными. Однако двоичные коды операций и адреса в машинных командах заменены на идентификаторы, форма написания которых помогает программисту запоминать смысловое содержание операции. Это существенно уменьшает число ошибок при составлении программ. • Автокоды - это языки, включающие в себя все возможности языков символического кодирования, посредством введения макрокоманд (часто используемых последовательностей команд). Развитые автокоды получили название Ассемблеры. • Макросы или макроязыки - это языки, являющиеся средством для замены последовательности символов описывающих выполнение требуемых действий ЭВМ. В основном, макросы предназначены для сокращения записи исходной программы. Т.к. разные типы процессоров имеют разные системы команд, то и программы, написанные на машинном языке, или языке ассемблера, ориентированы на конкретный тип процессора. С этой точки зрения эти языки называются языками низкого уровня. С помощью языков низкого уровня создаются очень эффективные и компактные программы, т.к. разработчик получает доступ ко всем возможностям процессора. С другой стороны, при этом требуется очень хорошо понимать устройство компьютера, программа не может быть перенесена на компьютер с другим типом процессора. Подобные языки обычно применяют для написания небольших системных приложений, драйверов устройств, модулей стыковки с нестандартным оборудованием и др. Машинно–независимые языки – это средство описания алгоритмов решения задач и данных, подлежащих обработке. Они удобны в использовании для широкого круга пользователей и не требуют от них знания особенностей организации функционирования ЭВМ. Подобные языки получили название высокоуровневых языков программирования. Программы, составляемые на таких языках, представляют собой последовательности операторов, структурированные согласно правилам языка. Операторы языка описывают действия, которые должна выполнять ЭВМ после трансляции программы на машинный язык. Командные последовательности (процедуры, подпрограммы), часто используемые в машинных программах, представлены в высокоуровневых языках отдельными операторами. Программист получил возможность не расписывать в деталях вычислительный процесс на уровне машинных команд, а сосредоточиться на основных особенностях алгоритма. Проблемно-ориентированные языки - это языки программирования, ориентированные на решение задач в конкретной области применения ЭВМ. Их операторы, функции и структуры данных согласованы с обозначениями и терминологией данной области. Таких языков очень много, например: • Симула, Модула-2 - для моделирования; • Лисп, Снобол – для работы со списочными структурами; • Пролог. Процедурно-ориентированные или алгоритмические языки предназначены для решения научно-технических задач пользователями, которые в состоянии самостоятельно разработать алгоритм решения конкретной задачи или разобраться в известном алгоритме. Первый такой язык ПЛ/1 (PL/1 - Programing Language) был разработан фирмой IBM. Второй по мощности алгоритмический язык называется Алгол-68 (ALGOL - ALGOrihtmic Language). Он позволяет работать с символами, разрядами, числами с фиксированной и плавающей запятой. ПЛ/1 имеет развитую систему операторов для управления форматами, для работы с полями переменной длины, с данными организованными в сложные структуры, и для эффективного использования каналов связи. Язык учитывает включенные во многие машины возможности прерывания и имеет соответствующие операторы. Предусмотрена возможность параллельного выполнения участков программ. Программы в ПЛ/1 компилируются с помощью автоматических процедур. Допускается динамическое, управляемое и статистическое выделение памяти. Диалоговые языки. Появление новых технических возможностей поставило задачу перед системными программистами – создать программные средства, обеспечивающие оперативное взаимодействие человека с ЭВМ их назвали диалоговыми языками. Необходимость обеспечения оперативного взаимодействия с пользователем потребовала сохранения в памяти ЭВМ копии исходной программы даже после получения объектной программы в машинных кодах. При внесении изменений в программу с использованием диалогового языка система программирования с помощью специальных таблиц устанавливает взаимосвязь структур исходной и объектной программ. Это позволяет осуществить требуемые редакционные изменения в объектной программе. Одним из примеров диалоговых языков является Бэйсик. Он использует обозначения подобные обычным математическим выражениям. Многие операторы являются упрощенными вариантами операторов языка Фортран. Поэтому этот язык позволяет решать достаточно широкий круг задач. Непроцедурные языки составляют группу языков, описывающих организацию данных, обрабатываемых по фиксированным алгоритмам (табличные языки и генераторы отчетов), и языков связи с операционными системами. Позволяя четко описывать как задачу, так и необходимые для ее решения действия, таблицы решений дают возможность в наглядной форме определить, какие условия должны выполняться, прежде чем переходить к какому-либо действию. Одна таблица решений, описывающая некоторую ситуацию, содержит все возможные блок-схемы реализаций алгоритмов решения. Языки описания сценариев, в отличие от других языков программирования, предназначенных для построения структур данных и алгоритмов «с нуля», создавались для связывания готовых программ. Их применение подразумевает наличие достаточного ассортимента мощных компонентов, которые требуется только объединить друг с другом. Набор этих компонентов создается заранее при помощи других языков. Языки описания сценариев часто применяются и для дополнения готовых компонентов новыми возможностями; однако эта деятельность редко охватывает создание сложных алгоритмов или структур данных, которые уже обычно бывают уже заложены в компоненты. Иногда языки описания сценариев даже называют связующими или языками системной интеграции. Синтаксис и семантика языков программирования Сегодня практически все программы создаются с помощью языков программирования. Языки программирования – искусственные языки. От естественных они отличаются ограниченным числом «слов», значение которых понятно транслятору, и очень строгими правилами записи команд (операторов). Совокупность подобных требований образует синтаксис языка программирования, а смысл каждой команды и других конструкций языка – его семантику. Нарушение формы записи программы приводит к тому, что транслятор не может понять назначение оператора и выдает сообщение о синтаксической ошибке, а правильно написанное, но не отвечающее алгоритму использования команд языка приводит к семантическим ошибкам (называемые еще логическими ошибками или ошибками времени выполнения). Итак: Синтаксис – система правил, определяющих допустимые конструкции языка программирования из букв алфавита. Семантика – система правил однозначного толкования каждой языковой конструкции, позволяющих производить процесс обработки данных. Процесс поиска ошибок в программе называется тестированием, процесс устранения ошибок - отладкой. С помощью языка программирования создается не готовая программа, а только ее текст, описывающий ранее разработанный алгоритм. Чтобы получить работающую программу, надо этот текст либо автоматически перевести в машинный код (для этого служат программы-компиляторы) и затем использовать отдельно от исходного текста, либо сразу выполнять команды языка, указанные в тексте программы (этим занимаются программы-интерпретаторы). Поколения языков программирования Языки программирования принято делить на пять поколений. В первое поколение входят языки, созданные в начале 50-х годов прошлого столетия, когда первые компьютеры только появились на свет. Это был первый язык ассемблера, созданный по принципу «одна инструкция – одна строка». Второе поколение языков программирования (конец 50-х – начало 60-х) связывают с разработкой символического ассемблера, в котором появилось понятие переменной, при этом заметно возросли скорость разработки и надежность программ. Третье поколение (60-е) годы – это создание универсальных языков высокого уровня, с их помощью удается решать задачи из любых областей. Относительная простота, независимость от конкретного компьютера, возможность использования мощных синтаксических конструкций позволили резко повысить производительность труда программистов. Понятная большинству пользователей структура этих языков привлекла к написанию небольших программ (как правило, инженерного или экономического характера) значительное число специалистов из некомпьютерных областей. С начала 70-х по настоящее время продолжается период языков четвертого поколения. Эти языки предназначены для реализации крупных проектов. Они обычно ориентированы на специализированные области применения, где хороших результатов можно добиться, используя не универсальные, а проблемно-ориентированные языки, оперирующие конкретными понятиями узкой предметной области. Как правило, в эти языки встраиваются мощные операторы, позволяющие одной строкой описать такую функциональность, для реализации которой на языках младших поколений потребовались бы тысячи строк исходного кода. Рождение языков пятого поколения произошло в середине 90-х годов. К ним относятся также системы автоматического создания прикладных программ с помощью визуальных средств разработки, без знания программирования. Главное в этих языках – возможность автоматического формирования результирующего текста программы на универсальных языках программирования ( который потом требуется откомпилировать). Инструкции же вводятся в компьютер в максимально наглядном виде с помощью методов, наиболее удобных для человека, незнакомого с программированием. Краткий обзор языков программирования Язык Ассемблера – это символическое представление машинного языка. Он облегчает процесс программирования по сравнению с программированием в машинных кодах. Программисту не обязательно употреблять настоящие адреса ячеек памяти с размещенными в них данными, участвующими в операции, и вычисляемые результаты, а также адреса тех команд, к которым программа не обращается. С помощью ассемблерных вставок в текст программы на языке программирования высокого уровня можно решить задачи, например, обмен данными с нестандартными устройствами ввода-вывода, которые невозможно решить с помощью используемого языка программирования высокого уровня. Язык Лисп. Фортран и подобные ему языки программирования (Алгол, ПЛ/1) предназначались для решения вычислительных задач, возникающих в математике, физике, инженерных расчетах, экономике и т. п. Эти языки в основном работают с числами. Второй старейший язык программирования Лисп (LISP - List Information Symbol Processing) Дж. Маккарти создал в 1962 г. скорее для работы со строками символов, нежели для работы с числами. Это особое предназначение Лиспа открыло для программистов новую область деятельности, известную, как «искусственный интеллект». В настоящее время Лисп успешно применяется в экспертных системах, системах аналитических вычислений и т. п. Первоначально Лисп был задуман как теоретическое средство для рекурсивных построений, а сегодня он превратился в мощное средство, обеспечивающее программиста разнообразной поддержкой, позволяющей ему быстро строить прототипы весьма и весьма серьезных систем. Обширность области возможных приложений Лиспа вызвала появление множества различных диалектов Лиспа. В качестве основного диалекта языка с 1985 г. был принят диалект Common LISP. Язык Фортран. Одним из первых и наиболее удачных компиляторов стал язык Фортран (FORTRAN), разработанный фирмой IBM. Профессор Дж. Бэкус и группа американских специалистов в области программирования в 1954 году опубликовали первое сообщение о языке. Дословно, название языка FORmula TRANslation –преобразование формул. Среди причин долголетия Фортрана (а он один из самых распространенных языков в мире), можно отметить простую структуру, как самого Фортрана, так и предназначенных для него трансляторов. Программа на Фортране записывается в последовательности предложений или операторов (описание некоего преобразования информации), и оформляется по определенным стандартам. Эти стандарты накладывают ограничения, в частности, на форму записи и расположения частей оператора в строке бланка для записи операторов. Программа, записанная на Фортране, представляет собой один или несколько сегментов (подпрограмм), состоящих из операторов. Сегмент, управляющий работой всей программы в целом, называется основной программой. Фортран был задуман для использования в сфере научных и инженерно-технических вычислений. Однако на этом языке легко описываются задачи с разветвленной логикой (моделирование производственных процессов, решение игровых ситуаций и т. д.), некоторые экономические задачи и особенно задачи редактирования (составление таблиц, сводок, ведомостей и т. п.). К 1962 году относится появление языка, известного под именем Фортран IV и ставшего наиболее употребительным в настоящее время. Язык Фортран до сих пор продолжает развиваться и совершенствоваться, оказывая влияние на создание и развитие других языков. Например, Фортран заложен в основу диалогового языка Бейсик, очень популярного для решения небольших задач и обучения алгоритмическим навыкам в практике программирования. Язык Бейсик (BASIC - Beginner's All-purpose Symbolic Insruction Code) создан в 1964 г. Томасом Куртом и Джоном Кемени как язык для начинающих, облегчающий написание программных кодов или просто программ. Интересно, что спустя 40 лет после изобретения, Бейсик и сегодня самый простой для освоения из десятков языков общецелевого программирования. Бейсик считается деловым языком, снабженным мощными средствами решения специфических задач, которые обычно большинство пользователей решают при помощи компьютеров, а именно: работая с файлами и выводя текстовое и графическое изображение на экране дисплея. Исторически Бейсик обычно реализовался как интерпретатор. Многочисленные расширения классической версии языка: возможность отключения нумерации строк, структурированные программные конструкции, поименованные подпрограммы с параметрами и локальные переменные, стали причинами перехода от любительского уровня к профессиональному. Более того, с появлением транслятора QuickBasic фирмы Microsoft разработчики получили возможность строить на Бейсике приложения из раздельно откомпилированных модулей, некоторые из которых могут быть написаны на других языках. Теперь, как и в случае других ведущих языков программирования, разработчик имеет выбор из нескольких промышленных библиотек подпрограмм, которые содержат готовые решения для распространенных задач программирования. Широкие возможности графической среды программирования Visual Basic и другие достоинства языка послужили основной причиной для выбора его в качестве языка программирования для создания Windows-приложений. Pascal(Паскаль). Создан в конце 70-х годов основоположником множества идей современного программирования Никлаусом Виртом, во многом напоминает Алгол, но в нем ужесточен ряд требований к структуре программы. Он был назван в честь французского математика и философа Блеза Паскаля. В основу разработки языка Паскаль был положен Алгол-60. Паскаль был создан как язык для обучения программированию. Не нашел широкого практического применения. Язык Рефал. Несомненно, следует рассказать и о языках программирования, созданных у нас на родине. Одним из таких языков является Рефал, разработанный в 1966г. ИПМ АН СССР. Этот язык прост и удобен для описания манипуляций над произвольными текстовыми объектами. Рефал широко применяется при разработке трансляторов с алгоритмических языков как универсальных и проблемно-ориентированных, так и автокодов. Кроме использования в задачах трансляции, Рефал имеет такие важные сферы применения, как машинное выполнение громоздких аналитических выкладок в теоретической физике и прикладной математике; проектирование «умных» информационных систем, осуществляющих нетривиальную логическую обработку информации; машинное доказательство теорем; моделирование целенаправленного поведения; разработка диалоговых обучающих систем; исследования в области искусственного интеллекта и т.п. Языки Пролог и Пролог++. Пролог - это декларативный язык, предназначенный для поиска решений, в котором постановка задачи может быть использована для ее решения. Пролог (PROLOG - PROgramming in LOGic - программирование в терминах логики) определяет логические отношения в задаче, отличные от пошагового решения этой задачи. Центральной частью Пролога являются средства логического вывода, решающие запросы, используя заданное множество фактов и правил, к которым обращаются как к утверждениям. Пролог также не имеет деления переменных на типы и может динамически добавлять правила и факты к средствам вывода. Пролог++ представляет собой дополнение к стандартному Прологу. Пролог++ можно отнести к группе гибридных объектно-ориентированных языков, поддерживающих концепции объектов и классов, единичного и многократного наследования, разбиения на подклассы и передачу сообщений. Интересным свойством является поддержка программирования, «управляемого событиями», которое используется в компьютерах с интерфейсом, управляемым «мышью». Объектно-ориентированная программа реагирует на события, которые определяют поток управления. В Прологе++ программирование с управлением данными достигается при помощи концепции демонов. Демон представляет собой объект, методы которого вызываются в случае определенных событий. Язык Cи – это язык программирования общего назначения, известный своей эффективностью, экономичностью, и переносимостью. Он был изобретен в 1972 г. Денисом Ричи для использования при написании весьма популярной операционной системы Unix. Си соединяет свойства языка высокого уровня с возможностью эффективного использования ресурсов компьютера, которое обычно обеспечивается только при программировании языке Ассемблера. Си не очень прост при обучении и требует тщательности в программировании, но позволяет писать сложные и высокоэффективные программы. Указанные свойства Си обеспечивают хорошее качество разработки почти любого вида программных продуктов. Использование Си в качестве инструментального языка позволяет получать быстрые и компактные программы. Во многих случаях программы, написанные на Си, сравнимы по скорости с программами, написанными на языке ассемблера. При этом они имеют лучшую наглядность и их проще сопровождать. Си сочетает эффективность и мощность в относительно малом по размеру языке. Этот язык создан программистом для использования другими программистами, чего о других языках программирования сказать нельзя. Си обеспечивает полный набор операторов структурного программирования. Си предлагает необычно большой набор операций. Многие операции Си соответствуют машинным командам, и поэтому допускают прямую трансляцию в машинный код. Разнообразие операций позволяет выбирать их различные наборы для минимизации результирующего кода. Язык Си предъявляет достаточно высокие требования к квалификации использующего его программиста. При изучении Си желательно иметь представление о структуре и работе компьютера. Большую помощь и более глубокое понимание идей Си, как языка системного программирования, обеспечат хотя бы минимальное знание языка ассемблера. Уровень старшинства некоторых операторов не является общепринятым, некоторые синтаксические конструкции могли бы быть лучше. Тем не менее, как оказалось Си – чрезвычайно эффективный и выразительный язык, пригодный для широкого класса задач. Язык Си++ был разработан Бьярном Страустрапом как расширение языка Си, реализующее популярные в последнее время концепции объектно-ориентированного программирования и облегчающее создание сложных программ. Название Си++ - изобретение лета 1983 г. его выдумал Рик Масситти. Название указывает на эволюционную природу перехода к нему от Cи. «++» - это операция приращения в Cи. Си++ - это универсальный язык программирования, за исключением второстепенных деталей являющийся надмножеством языка Cи. Помимо возможностей, которые дает Cи, Си++ предоставляет гибкие и эффективные средства определения новых типов - классов. Используя определения классов, точно отвечающих концепциям приложения, программист может разделять разрабатываемую программу на легко поддающиеся контролю части. Такой метод построения программ часто называют абстракцией данных. Информация о типах содержится в некоторых объектах типов, определенных пользователем. Такие объекты просты и надежны в использовании в тех ситуациях, когда их тип нельзя установить на стадии компиляции. Программирование с применением таких объектов часто называют объектно-ориентированным. При правильном использовании этот метод дает более короткие, проще понимаемые и легче контролируемые программы. Особое внимание, уделенное при разработке Си++ структуре, отразилось на возрастании масштаба программ, написанных со времени разработки Cи. Маленькую программу (меньше 1000 строк) не трудно заставить работать, даже нарушая все правила хорошего стиля программирования. Для программ больших размеров это не совсем так. Если программа в 10000 строк имеет плохую структуру, то обнаруживается, что новые ошибки появляются так же быстро, как удаляются старые. Си++ дает возможность разумным образом структурировать масштабные программы, состоящие из большого числа почти независимых частей небольшого размера. Cobol(Кобол). Это компилируемый язык для применения в экономической области и решения бизнес - задач, разработанный в начале 60-х годов. Он отличается большой «многословностью» – его операторы иногда выглядят как обычные английские фразы. На этом языке создано очень много приложений, которые активно эксплуатируются и сегодня. Достаточно сказать, что наибольшую зарплату в США получают программисты на Коболе. Algol(Алгол). Компилируемый язык, созданный в 1960 году. Он был призван заменить Фортран, но из-за более сложной структуры не получил широкого распространения и сошел «со сцены». Java ( Джава, Ява). Этот язык был создан компанией Sun в начале 90-х годов на основе Cи++. Он призван упростить разработку приложений на основе Си++ путем исключения из него всех низкоуровневых возможностей. Но главная особенность языка – компиляция не в машинный код, а в платформно-независимый байт-код (каждая команда занимает один байт). Этот байт-код может выполняться с помощью интерпретатора – виртуальной Java- машины JVM(Java Virtual Machine), версии которой созданы для любых платформ. Благодаря наличию множества Java- машин программы на Java можно переносить не только на уровне исходных текстов, но и на уровне двоичного байт-кода, поэтому по популярности язык Ява сегодня занимает второе место в мире после Бейсика. Пока основной недостаток этого языка – невысокое быстродействие, т.к. язык Ява интерпретируемый. Языки программирования баз данных. Первые базы данных появились очень давно, как только появилась потребность в обработке больших массивов информации и выборки групп записей по определенным признакам. Для этого был создан структурированный язык запросов SQL. Для управления большими базами данных и их эффективной обработки разработаны СУБД. Практически в каждой СУБД помимо поддержки языка SQL имеется также свой уникальный язык, ориентированный на особенности этой СУБД и не переносимый на другие системы. Сегодня в мире насчитывается пять ведущих производителей СУБД: Microsoft (SQL Server), IBM(DB2), Oracle, Software AG (Adabas), Informix и Sybase. Их продукты нацелены на поддержку одновременной работы тысяч пользователей в сети, а базы данных могут храниться в распределенном виде на нескольких серверах. С появлением персональных компьютеров были созданы так называемые настольные СУБД. Родоначальником современных языков программирования баз данных для ПК принято считать СУБД dBase||, язык которой был интерпретируемым. Затем для него были созданы компиляторы, появились СУБД FoxPro и Clipper, поддерживающие диалекты этого языка. Сегодня похожие, но несовместимые версии языков семейства dBase, реализованы в продуктах Visual FoxPro фирмы Microsoft и Visual dBase фирмы Inprise. Языки программирования для Интернета. С активным развитием глобальной сети было создано немало реализаций популярных языков программирования, адаптированных специально для Интернета. Все они отличаются характерными особенностями: языки являются интерпретируемыми, интерпретаторы для них распространяются бесплатно, а сами программы в исходных текстах. Такие языки называются скрипт-языками. HTML - общеизвестный язык для оформления документов. Он очень прост и содержит элементарные команды форматирования текста, добавления рисунков, задания шрифтов и цветов, организации ссылок и таблиц. Все Web-страницы написаны на языке HTML или используют его расширения. Также к языкам программирования для Интернет относятся языки Perl, Tcl/Tk, VRML. Perl – предназначен для эффективной обработки больших текстовых файлов, создания текстовых отчетов и управления задачами. В его состав входят многочисленные функции работы со строками, массивами, всевозможные средства преобразования данных, управления процессами и др. Tcl/Tk – в конце 80-х гг. Джон Аустираут придумал скрипт-язык Tcl и библиотеку Tk. Он ориентирован на автоматизацию рутинных операций и состоит из машинных команд, выполняющих обработку нетипизированных объектов. VRML – создан для организации виртуальных трехмерных интерфейсов в Интернете. Прочие языки программирования. PL/1(ПЛ/1)-в середине 60-х годов компания IBM решила взять все лучшее из языков Фортран, Кобол и Алгол. В результате в 1964 г. на свет появился новый компилируемый язык программирования, который получил название Programming Language One. По своим возможностям ПЛ/1 значительно мощнее многих других языков (Си, Паскаля). Этот язык и сегодня продолжает поддерживаться компанией IBM.Можно также перечислить языки – Smalltalk(Смолток), Ada(Ада), Forth(Форт). Ada. Период с конца 60-х до начала 80-х характеризуется бурным ростом числа различных языков программирования, сопровождавшим, как это ни парадоесально, кризис программного обеспечения. В январе 1975 г. Пентагон решил навести порядок среди бесчисленного множества трансляторов и создал комитет для разработки одного универсального языка. На конкурсной основе комитет рассмотрел сотни проектов и выяснил, что ни один из существующих языков не может удовлетворить их требованиям, для окончательного рассмотрения было составлено два проекта. В мае 1979 г. был объявлен победитель – группа ученых во главе с Жаном Ихбиа. Победивший язык назвали АДА, в честь Ады Лавлейс. Язык Ада – прямой наследник Паскаля. Он предназначен для создания и длительного сопровождения больших программных систем, управления процессами в реальном масштабе времени. Язык Ада сложен для изучения. Языки моделирования. При моделировании систем применяются формальные способы их описания – формальные нотации, с помощью которых можно представить объекты и взаимосвязи между ними в системе, имеющей специализированный редактор и генератор исходных тестов программ на основе созданной модели. Такие системы называют CASE – системами. В них активно применяются нотации IDEF, а в последнее время все большую популярность завоевывает язык графического моделирования UML. Вопросы к лекции №1 1. Какова история определения понятия «алгоритм»? 2. Какие способы описания алгоритма вы знаете? 3. Перечислите символику блок-схем. Дайте краткое объяснение каждому блоку и соответствующему ему оператору программирования. 4. Опишите с помощью блок-схемы алгоритм нахождения максимума и минимума из последовательности случайных вещественных чисел 5. Что такое структурная блок-схема? Кратко опишите четыре элементарные структуры. 6. Что такое язык программирования? 7. В чем различие компиляторов и интерпретаторов? 8. Объясните термины «язык низкого уровня» и «язык высокого уровня». 9. Расскажите о поколениях языков программирования. 10. Какие языки программирования активно используются сегодня?