План: Общие понятия об алгоритме Способы записи алгоритмов История и классификация языков программирования Структура и способы описания языков программирования высокого уровня
| Вид материала | Лекция |
- Календарный план учебных занятий по дисциплине «Языки и технология программирования», 43.35kb.
- Введение Предмет "Программирование", 19.2kb.
- Рабочая программа по курсу "Программирование на языках высокого уровня" Факультет экономический, 113.19kb.
- Рейтинг-план дисциплины «Языки программирования в иит» в течение семестра Недели, 53.58kb.
- Пояснительная записка к курсовой работе по предмету «Языки и технологии программирования», 353.31kb.
- Лекция 3 Инструментальное по. Классификация языков программирования, 90.16kb.
- Программа дисциплины Языки и технологии программирования Семестры, 20.19kb.
- Существуют различные классификации языков программирования, 174.02kb.
- Эволюция языков программирования, 493.92kb.
- Программа курса «Программирование на языке высокого уровня», 126.66kb.
Лекция 1. ВВЕДЕНИЕ В ЯЗЫКИ ПРОГРАММИРОВАНИЯ
План:
1. Общие понятия об алгоритме
2. Способы записи алгоритмов
3. История и классификация языков программирования
4. Структура и способы описания языков программирования высокого уровня
1. Общие понятия об алгоритме
С точки зрения современной психологии задача в самом общем понимании — это некоторая цель, поставленная в конкретных условиях и требующая исполнения, решения. Примерами интеллектуальных задач являются следующие: 1) решить полное квадратное уравнение ах2 + bх + с = 0; 2) составить таблицу значений х2, х3 и 1/х величины х, меняющейся с некоторым шагом x от некоторого начального значения п до некоторого конечного значения т; 3) найти среди группы русских глаголов те, которые употреблены в инфинитиве; 4) составить реферат научного текста; 5) перевести текст с английского языка на русский и т. д.
Чтобы решить задачу, необходимо знать ее начальные условия, а также метод или способ ее решения. Так, чтобы решить полное квадратное уравнение, необходимо знать конкретные значения коэффициентов а, b и с (начальные условия). В качестве метода решения этого уравнения надо использовать правило вычисления значений х1 и х2:
Чтобы перевести текст на русский язык, необходимо иметь, как минимум, англо-русский словарь и знать английскую и русскую грамматики, лексикологию и еще многое другое. Все это начальные условия. В качестве метода решения этой задачи выступают те правила перевода текстов, которым обучают в вузе.
Таким образом, метод или способ решения некоторой задачи сводится к поиску определенных правил. Согласно «Словарю русского языка» С. И. Ожегова правило — это предписание, устанавливающее порядок чего-нибудь. Точное предписание о выполнении в определенном порядке некоторой последовательности действий (физических или умственных), приводящее к решению некоторой типовой задачи, называют алгоритмом. Например, при необходимости сварить кофе последовательность физических действий будет такой: вскипятить нужное количество воды, засыпать кофе в горячую воду (одну-две чайные ложки на стакан воды), нагреть воду до кипения (но не кипятить) и т.д. Определенные последовательности физических действий выполняются человеком и при решении таких задач, как «добраться из дома в университет», «найти в большом городе нужный дом», «изготовить на станке какую-то деталь» и т.п. Примеры задач, для решения которых необходимо выполнить определенную последовательность умственных действий, приведены выше.
Слово алгоритм происходит от слова algorithmi — латинской формы написания имени великого математика IX века аль-Хорез-ми. Он впервые четко сформулировал правила выполнения арифметических действий. Сейчас это понятие используется для обозначения последовательности любых действий (арифметических, логических, взятия логарифмов, вычисления синуса и т.п.).
Алгоритмы обладают следующими основными свойствами:
1. Дискретность алгоритма заключается в том, что он разбивается на конечное число действий-шагов (предписаний, команд), которые могут быть пронумерованы. Причем только после выполнения одного предписания можно перейти к выполнению другого.
2. Результативность алгоритма означает, что при всех начальных условиях число шагов алгоритма конечно, и он приводит к решению задачи.
3. Массовость алгоритма предполагает, что по данному алгоритму может быть решен целый ряд типовых задач (они отличаются лишь различными начальными условиями).
4. Детерминированность алгоритма заключается в том, что при многократном решении одной и той же задачи с одинаковыми начальными условиями всегда получается один и тот же результат.
5. Формализованность алгоритма состоит в том, что тот, кто его выполняет (человек, машина), может не вникать в смысл того, что он делает согласно предписаниям алгоритма, и все равно придет к верному результату.
Между задачей и ее алгоритмом соответствие неоднозначное. Очень мало задач имеют только один алгоритм решения. Например, задача «позвонить по междугороднему телефону» для данного типа телефонного автомата имеет единственный алгоритм, представленный в виде правила пользования этим телефонным аппаратом. Большинство задач могут иметь несколько алгоритмов решения. Так, есть несколько правил приготовления кофе, можно различными путями добраться из дома в университет, несколькими способами составить по тексту его реферат и т.д. В то же время есть задачи, алгоритм решения которых до сих пор неизвестен. Так, неясно, как человек пишет стихи, повесть или научную статью. Нет точных предписаний, как переводить текст с одного языка на другой и т.д.
^ 2. Способы записи алгоритмов
Существует несколько способов записи алгоритмов решения задач. Наиболее известны следующие: словесный, графический и табличный.
Словесное представление алгоритма решения задачи сводится к тому, что составляющие алгоритм шаги (предписания) записываются в виде слов и предложений естественного языка.
При графическом представлении алгоритма его шаги изображаются разными геометрическими фигурами (блоками), образующими блок-схему алгоритма. Связи между блоками обозначены стрелками, соединяющими соответствующие фигуры. Чаще всего в качестве таких геометрических фигур используются следующие:
| 1. Параллелограмм  | используется для обозначения действий ввода информации в компьютер и вывода информации из него. |
| 2  . Прямоугольник | используется для записи вычислительных и некоторых других действий. |
| 3  . Ромб | используется для проверки различных условий. |
| 4  . Овал | используется для обозначения начала и конца алгоритма. |
| 5  . Круг | служит для указания тех блоков алгоритма, на которые передается управление от блоков первых трех типов. |
При табличном представлении алгоритма его шаги записываются в графах специальных таблиц. Чаще всего такой способ записи алгоритма используется для выполнения различных вычислений по формулам.
Продемонстрируем три способа записи алгоритма на примере следующей задачи: «Решить полное квадратное уравнение ахг+ bх + с = 0 (1)» (слово «решить» в данном случае означает, что надо найти то значение х, при котором левая часть равенства обращается в нуль). Как было отмечено выше, способ решения этой задачи определяется равенством
(2),где величина b2 - 4ас называется дискриминантом. Тогда формула (2) может быть вычислена по следующему словесному алгоритму.
8. Закончить работу.
Запись процесса решения этой же задачи в виде блок-схемы (в графическом виде) может быть представлена следующим образом (схема 1).
Алгоритм решения того же уравнения в табличной форме может быть задан следующим образом (например, при значениях коэффициентов:
а=1, b=-7, с=12, т.е. для уравнения х2-7х+ 12 = 0).
^ Язык программирования, или алгоритмический язык (АЯ), — это искусственный язык, используемый для представления алгоритма решения задачи в виде, понятном компьютеру.
Программа – упорядоченная последовательность команд (инструкций) компьютера для решения задачи.
^ Система программирования (СП) (система разработки приложений, среда программирования) — это интегрированный набор средств разработки программ, обычно включающий язык программирования, средства компоновки и отладки программы, а также обширную библиотеку готовых к использованию программных модулей.
^ 3. История и классификация языков программирования
Существуют различные подходы к классификации языков программирования. Согласно одному из современных подходов языки программирования делятся на следующие четыре типа: 1) языки ассемблера; 2) языки системного уровня; 3) языки описания сценариев; 4) языки промежуточного типа.
Языки ассемблера представляют записанные в алгоритме действия в виде машинных кодов (например, 01 — сложить, 02 — вычесть и т.д.).
В языках системного уровня действия алгоритма записываются в виде отдельных английских слов или их частей. Существуют определенные правила (синтаксис) следования таких слов друг за другом. Подобные языки могут быть простыми и достаточно сложными. К числу простых можно отнести практически неиспользуемые сейчас языки программирования Algol, Fortran, Cobol, используемые — PL/1, Quick BASIC и др. Более сложными современными языками этого типа являются С, C++, Pascal, Turbo Pascal, Java и т.д.
Языки описания сценариев служат для связывания готовых программ в новые более сложные программы. В настоящее время к ним относятся такие языки программирования, как Perl, TCL, Visual BASIC, " onclick="return false">
К языкам промежуточного типа относится, например, язык Lisp. Он обладает свойствами и языков программирования системного уровня, и языков описания сценариев.
Процессор компьютера непосредственно понимает язык машинных команд (ЯМК). Программы на ЯМК программисты писали лишь для самых первых ламповых машин — ЭВМ первого поколения. Программист должен был: 1) знать числовые коды всех машинных команд; 2) распределять память под команды программы и данные.
В 1950-х гг. появляются первые средства автоматизации программирования — языки Автокоды. Позднее языки этого уровня стали называть «Ассемблеры». Появление языков типа Ассемблер облегчило программирование. В этих языках переменные величины стали изображаться символическими именами. Числовые коды операций заменились на мнемонические (словесные) обозначения, которые легче запомнить. Язык программирования стал понятнее для человека, но при этом удалился от языка машинных команд. Чтобы компьютер мог исполнять программы на Ассемблере, потребовалась специальная программа — транслятор.
Транслятор — это системная программа, переводящая текст программы на Ассемблере в текст эквивалентной программы на ЯМК.
Компьютер, оснащенный транслятором Ассемблера, понимает Ассемблер. В этом случае говорят о псевдо-ЭВМ (аппаратура плюс транслятор с Ассемблера), языком которой является Ассемблер. Языки типа Ассемблер являются машинно-ориентированными, т.е. они настроены на структуру машинных команд конкретного компьютера. Разные компьютеры с разными типами процессоров имеют разный Ассемблер.
Языки программирования высокого уровня (ЯПВУ) являются машинно-независимыми языками. Одна и та же программа на таком языке может быть выполнена на ЭВМ разных типов, оснащенных соответствующим транслятором. Форма записи программ на ЯПВУ по сравнению с Ассемблером еще ближе к традиционной математической форме, к естественному языку. ЯПВУ легко изучаются, хорошо поддерживают структурную методику программирования.
^ Структурное программирование – дисциплина, появившаяся в конце 60-х — начале 70-х гг. XX столетия. (Ее появление и развитие связаны с именами Э.В. Дейкстры, Х.Д. Милса, Д. Е. Кнута и других ученых). Структурное программирование до настоящего времени остается основой технологии программирования. Соблюдение его принципов позволяет программисту быстро научиться писать ясные, безошибочные, надежные программы. В основе структурного программирования лежит теорема, которая была строго доказана в теории программирования. Суть ее в том, что алгоритм для решения любой логической задачи можно составить только из структур «следование, ветвление, цикл». Их называют базовыми алгоритмическими структурами.
Первыми популярными языками высокого уровня, появившимися в 1950-х гг., были Фортран, Кобол (в США) и Алгол (в Европе). Языки Фортран и Алгол были ориентированы на научно-технические расчеты математического характера. Кобол — язык для программирования экономических задач. В Коболе по сравнению с двумя другими названными языками слабее развиты математические средства, но хорошо развиты средства обработки текстов, организация вывода данных в форме требуемого документа. Для первых ЯПВУ предметная ориентация языков была характерной чертой.
Большое количество языков программирования появилось в 1960 —1970-х гг. За всю историю ЭВМ их было создано более тысячи. Но распространились, выдержали испытание временем немногие.
В 1965 г. в Дартмутском университете был разработан язык Бейсик. По замыслу авторов это простой язык, легко изучаемый, предназначенный для программирования несложных расчетных задач. Наибольшее распространение Бейсик получил на микроЭВМ и персональных компьютерах. На некоторых моделях школьных компьютеров программировать можно только на Бейсике. Однако Бейсик — неструктурный язык, и потому он плохо подходит для обучения качественному программированию. Последние версии Бейсика для ПК (например, QBasic) стали структурными и по своим возможностям приближаются к таким языкам, как Паскаль.
В эпоху ЭВМ третьего поколения получил большое распространение язык PL/1 ^ Program Language One, разработанный фирмой IBM. Это был первый язык, претендовавший на универсальность, т. е. на возможность решать любые задачи: вычислительные, обработки текстов, накопления и поиска информации. Однако PL/1 оказался слишком сложным языком. Для машин типа IBM 360/370 транслятор с него не мог считаться оптимальным, содержал ряд невыявленных ошибок. На ЭВМ класса мини и микро он вообще не получил распространения. Однако тенденция к универсализации языков оказалась перспективной. Старые языки были модернизированы в универсальные варианты — Алгол-68, Фортран-77.
Значительным событием в истории языков программирования стало создание в 1971 г. языка Паскаль. Его автор — швейцарский профессор Н.Вирт — разрабатывал Паскаль как учебный язык структурного программирования.
Наибольший успех в распространении этого языка обеспечили персональные компьютеры. Фирма ^ Borland International, Inc (США) Разработала систему программирования Турбо Паскаль для ПК.
Турбо Паскаль — это язык программирования, транслятор с него и среда программирования, обеспечивающая пользователю удобство работы. Турбо Паскаль вышел за рамки учебного предназначения и стал языком профессионального программирования с универсальными возможностями. Транслятор с Турбо Паскаля по оптимальности создаваемых им программ близок наиболее удачному в этом отношении транслятору — транслятору с Фортрана. В силу названных достоинств Паскаль стал основой многих современных языков программирования, например, таких как Ада, Модула-2 и др.
Язык программирования Си (английское название — С) создавался как инструментальный язык для разработки операционных систем, трансляторов, баз данных и других системных и прикладных программ. Так же как и Паскаль, Си — это язык структурного программирования, но, в отличие от Паскаля, в нем заложены возможности непосредственного обращения к некоторым машинным командам, к определенным участкам памяти компьютера. Дальнейшее развитие Си привело к созданию языка объектно-ориентированного программирования Си++.
Модула-2 — это еще один язык, предложенный Н.Виртом, основанный на языке Паскаль и содержащий средства для создания больших программ.
Для ЭВМ будущего, пятого поколения, которые называют машинами «искусственного интеллекта» и которые еще не созданы, были разработаны языки программирования ЛИСП и Пролог.
ЛИСП появился в 1965 г. Язык ЛИСП основан на понятии рекурсивно определенных функций. А поскольку доказано, что любой алгоритм может быть описан с помощью некоторого набора рекурсивных функций, то ЛИСП, по сути, является универсальным языком. С его помощью на ЭВМ можно моделировать достаточно сложные процессы, в частности интеллектуальную деятельность людей.
Язык Пролог разработан во Франции в 1972 г. также для решения проблемы «искусственного интеллекта». Пролог позволяет в формальном виде описывать различные утверждения, логику рассуждений и заставляет ЭВМ давать ответы на заданные вопросы.
Реализовать тот или иной язык программирования на ЭВМ — это значит создать транслятор с этого языка для данной ЭВМ. Существуют два принципиально различных метода трансляции. Они называются соответственно компиляция и интерпретация.
Транслятор, работающий по принципу компиляции, называется компилятором; транслятор, работающий методом интерпретации, — интерпретатором.
При компиляции в память ЭВМ загружается программа-компилятор. Она воспринимает текст программы на ЯПВУ как исходную информацию. После завершения компиляции получается программа на языке машинных команд. Затем в памяти остается только программа на ЯМК, которая выполняется, и получаются требуемые результаты.
Интерпретатор в течение всего времени работы программы находится во внутренней памяти. В ОЗУ помещается и программа на ЯПВУ. Интерпретатор в последовательности выполнения алгоритма «читает» очередной оператор программы, переводит его в команды и тут же выполняет эти команды. Затем переходит к переводу и выполнению следующего оператора. При этом результаты предыдущих переводов в памяти не сохраняются. При повторном выполнении одной и той же команды она снова будет транслироваться. При компиляции исполнение программы разбивается на два этапа: трансляцию и выполнение. При интерпретации, поскольку трансляция и выполнение совмещены, программа на ЭВМ проходит в один этап. Однако откомпилированная программа выполняется быстрее, чем интерпретируемая. Поэтому использование компиляторов удобнее для больших программ, требующих быстрого счета. Программы на Паскале, Си, Фортране всегда компилируются. Бейсик чаще всего реализован через интерпретатор.
^ 4. Структура и способы описания языков программирования
высокого уровня
Во всяком языке программирования определены способы организации данных и способы организации действий над данными. Кроме того, существует понятие «элементы языка», включающее в себя множество символов (алфавит), лексемы и другие изобразительные средства языка программирования. Несмотря на разнообразие указанных языков, их изучение происходит приблизительно по одной схеме. Это связано с общностью структуры различных языков программирования высокого уровня, которая схематически можно представить на рис. 1.
Рис. 1. Структура языков программирования высокого уровня.
Изложение языков Паскаль и Си в учебниках, как правило соответствует этой схеме.
В изучении естественных языков и языков программирования есть сходные моменты. Во-первых, для того чтобы читать и писать на иностранном языке, нужно знать алфавит этого языка. Во-вторых, следует знать правописание слов и правила записи предложений, т.е. то, что называется синтаксисом языка. В-третьих, важно понимать смысл слов и фраз, чтобы адекватно реагировать на них: ведь из грамотно написанных слов можно составить абсолютно бессмысленную фразу. Смысловое содержание языковой конструкции называется семантикой.
Всякий язык программирования имеет три основные составляющие: алфавит, синтаксис и семантику.
Соблюдение правил в языке программирования более строгое, чем в разговорном языке. В текстах программ нет избыточности, компьютер сам не исправит даже очевидной (с точки зрения человека) ошибки. Он может лишь указать на место, которое «не понял», и вывести замечание о предполагаемом характере ошибки. Исправить же ошибку должен программист.
Для описания синтаксиса языка программирования требуется язык, который называют метаязык «надъязык». Наиболее распространенными метаязыками в литературе по программированию являются металингвистические формулы Бекуса-Наура (язык БНФ) и синтаксические диаграммы. В дальнейшем мы будем использовать язык синтаксических диаграмм и отдельные элементы языка БНФ.
В БНФ всякое синтаксическое понятие описывается в виде формулы, состоящей из правой и левой части, соединенных знаком ::=, смысл которого эквивалентен словам «по определению есть». Слева от знака ::= записывается имя определяемого понятия (метапеременная), которое заключается в угловые скобки < >, а в правой части записывается формула или диаграмма, определяющая все множество значений, которые может принимать метапеременная.
Синтаксис языка описывается путем последовательного усложнения понятий: сначала определяются простейшие (базовые), затем все более сложные, включающие в себя предыдущие понятия в качестве составляющих.
В такой последовательности, очевидно, конечным определяемым понятием должно быть понятие программы.
В записях метаформул приняты определенные соглашения. Например, формула БНФ, определяющая понятие «двоичная цифра», выглядит следующим образом:
<двоичная цифра>::=0|1
Значок | эквивалентен слову «или». Это определение можно представить на языке синтаксических диаграмм (рис. 2).
Рис. 2. Формула БНФ, определяющая понятие «двоичная цифра»
В диаграммах стрелки указывают на последовательность расположения элементов синтаксической конструкции; кружками обводятся символы, присутствующие в конструкции.
Понятие «двоичный код» как непустую последовательность двоичных цифр БНФ описывает так:
<двоичный код>::=<двоичная цифра>|<двоичный код> <двоичная цифра>
Определение, в котором некоторое понятие определяется само через себя, называется рекурсивным. Рекурсивные определения характерны для БНФ.
Синтаксическая диаграмма двоичного кода представлена на рис. 3.
Рис. 3. Синтаксическая диаграмма двоичного кода
Возвратная стрелка обозначает возможность многократного повторения. Очевидно, что диаграмма более наглядна, чем БНФ.
Синтаксические диаграммы были введены Н. Виртом и использованы для описания созданного им языка Паскаль.
- Назовите основные свойства алгоритмов
- В чем различие компиляторов и интерпретаторов?