Алгоритмизация и программирование. 7.Алгоритмизация и программирование. Алгоритмизация и программирование. Алгоритмизация. Эволюция языков программирования. Алгоритмы и способы их описания. Классификация языков программирования. Элементы языков программирования
 Скачать 89.21 Kb.
|
|
Алгоритмизация и программирование. Алгоритмизация. Эволюция языков программирования. Алгоритмы и способы их описания. Классификация языков программирования. Элементы языков программирования. Алгоритмизация — процесс составления алгоритмов для решения поставленных прикладных задач. Алгоритм — это точный набор инструкций, описывающих порядок действий некоторого исполнителя для достижения результата, решения некоторой задачи за конечное число шагов. Основные свойства алгоритмов: Понятность для исполнителя — исполнитель алгоритма должен понимать, как его выполнять. Иными словами, имея алгоритм и произвольный вариант исходных данных, исполнитель должен знать, как надо действовать для выполнения этого алгоритма. Дискретность (прерывность, раздельность) — алгоритм должен представлять процесс решения задачи как последовательное выполнение простых (или ранее определенных) шагов (этапов). Определенность — каждое правило алгоритма должно быть четким, однозначным и не оставлять места для произвола. Благодаря этому свойству выполнение алгоритма носит механический характер и не требует никаких дополнительных указаний или сведений о решаемой задаче. Результативность (или конечность) состоит в том, что за конечное число шагов алгоритм либо должен приводить к решению задачи, либо после конечного числа шагов останавливаться из-за невозможности получить решение с выдачей соответствующего сообщения, либо неограниченно продолжаться в течение времени, отведенного для исполнения алгоритма, с выдачей промежуточных результатов. Массовость означает, что алгоритм решения задачи разрабатывается в общем виде, т.е. он должен быть применим для некоторого класса задач, различающихся лишь исходными данными. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма. Элементы алгоритма. Блоки  Языки программирования низкого уровня Язык программирования, ориентированный на конкретный тип процессора, и, операторы которого близки к машинному коду, называется языком программирования низкого уровня. Термин «низкий уровень» не обозначает плохое качество языка, таким образом подчеркивается его неразрывная связь с аппаратной частью компьютера. Машинный язык Первые ЭВМ появились в 1940-х годах и программировались с помощью машинных языков. Машинный код состоял из последовательностей нулей и единиц. Каждая элементарная операция имела свой код, необходимо было явно указывать адреса ячеек памяти, в которых хранились данные, или куда их необходимо было сохранять. Такой подход содержал ряд неудобств, основными среди которых являлись: программа была машинно-зависимой, т. к. различные типы процессоров отличались друг от друга архитектурой и системой команд; чтение программы, а также изменение, отладка и поиск ошибок в ней вызывали огромные трудности. Ассемблер В начале 1950-х годов была осуществлена идея использования символьных имен вместо адресов данных и замены цифровых кодов операций на мнемонические (словесные) обозначения. Язык программирования, реализующий данный подход, получил название Ассемблер (от англ. assembler — сборщик). Программа, записанная на Ассемблере, не может обрабатываться непосредственно процессором. Возникла необходимость преобразования текста программы, записанной на данном языке, в машинный код. Для решения этой задачи были созданы трансляторы. Транслятор - это программа, преобразующая текст, представленный на одном из языков программирования, в эквивалентную программу на машинном языке. Использование символьных имен вместо числовых кодов операций и адресов данных существенно упростило процесс программирования, однако, по-прежнему сохранялась зависимость программы от типа процессора. Необходимо отметить, что во многих сегодняшних задачах, где качество машинного кода ставится выше удобства программирования (например, при разработке ядра операционной системы), по-прежнему используется Ассемблер. Вместо этого эволюция пошла по пути машинного языка. Он был удобен для компьютеров, но не очень удобен для программистов. Это была буквально работа с железом вручную: были лишь те команды, которые были зашиты в процессор, все остальные операции приходилось реализовывать вручную. Прямым развитием машинного языка стал язык ассемблера. Это был первый размен скорости на удобство: ассемблер был чуть менее нативным, но гораздо более дружелюбным к программисту. До языков высокого уровня, комфортных для программиста, было еще далеко. Качественный скачок произошёл после изобретения транзистора и первых доступных компьютеров. Это побудило в период с 1954-1957 году компанию IBM активно работать над разработкой популярного коммерчески языка Fortran (от англ. Formula и Translation). Fortran — язык для научных и инженерных вычислений. Считается, что именно он стал первым реализованным языком высокого уровня. Благодаря большому количеству математических библиотек Fortran был и остается важным языком для разного рода научных изысканий. Далее началось бурное развитие программирования: практически одновременно появились Algol, алгоритмический высокоуровневый язык, активно использовавшийся в СССР и Европе, LISP и COBOL. Языки для народа Но по-настоящему массовым программирование стало с появлением языка BASIC в 1964 году. Преподаватели Дартмутского Колледжа Джон Кемени и Томас Курц разработали его для обучения студентов основам программирования ЭВМ. BASIC был алгоритмическим языком, для его создателей было важно не быстродействие и эффективность, а легкое понимание. Тем не менее BASIC быстро обрёл популярность в реализациях от Microsoft и Apple. Но не все были им довольны. По мнению противников языка простота и бесструктурность ранних версий BASIC поощряли применение порочных и опасных методик разработки. Кайнозой В 1960-х годах компания Bell Labs всерьёз взялась за разработку операционной системы Unix для своих миникомпьютеров. Первые ОС были написаны на ассемблере, но эксперимент оказался неудачным. Потом в алфавитном порядке Кеном Томпсоном и Деннисом Ритчи был специально разработан интерпретируемый язык B (Би), но и в этот раз результат оставлял желать лучшего. Всё изменилось с третьей попыткой в 1972 году и языком C, который оказался настолько успешным, что и спустя 40 лет занимает важное место в разработке ПО. Например, по данным IEEE Spectrum, с в 2015 году стоял на втором месте: «The 2015 Top Ten Programming Languages». В другом полушарии на останках языка Algol-68 Никлаус Вирт разработал Pascal. Цель он преследовал ту же самую, что и BASIC — простота в обучении и наглядность выполняемых операций. Несмотря на внешнюю незамысловатость, Pascal оказался крайне эффективным языком не только в деле обучения, но и в серьезной разработке. Он остаётся крайне востребованным как в школах, так и в мире больших приложений: Total Commander, WinRAR, ранние версии Skype и Nero Burning ROM были написаны на Pascal. В конце 1970-х были сформированы принципы ООП, на основе которых был доработан язык C, получив сперва название «С with classes», а потом более привычное взгляду C++. Отчасти из-за совершенства творения, отчасти из-за славы одного из первопроходцев, C++ долгое время оставался самым востребованным языком. На нём были написаны операционные системы Symbian, Windows и OS X, браузеры Google Chrome и Mozilla, и ещё тысячи популярных приложений. Через четыре года после появления первой версии C++ Ларри Уолл разработал Perl — «практичный язык для извлечения данных и составления отчётов» (Practical Extraction and Report Language). Изначально язык обрёл популярность благодаря функциям, заложенным в названии, однако позднее расширил свои возможности и аудиторию. Сегодня Perl по-прежнему активно используется в качестве удобного средства обработки текста в командной строке, но не меньше востребован и в системном администрировании, веб-разработке и даже играх. Современность В статье об истории эволюции языков просто обязан упоминаться Python, горячо любимый не только преподавателями GeekBrains, но и, судя по широте использования, многими иностранными университетами и крупными зарубежными компаниями. Его структура и философия направлены на то, чтобы ускорить разработку готового продукта программистом. С точки зрения развития, это куда более совершенный язык, нежели все существовавшие до 1991 года. Он минималистичен, но при этом более читабелен, достаточно часто обновляется и прекрасен по соотношению «скорость — качество разработки». Впрочем, теми же самыми характеристиками можно описать и Ruby, увидевший свет в 1995 году, с поправкой на то, что у Юкихиро Мацумото было 2 года, чтобы подумать, чем его язык может стать лучше современников. Развитие интернета в конце XX века требовало более качественных языков обработки текста и данных. Так на свет появились HTML, PHP, CSS и JavaScript, без которых сегодня очень трудно представить веб-разработку. Вместе с этим появился и Java — объектно-ориентированный язык, использующий виртуальную машину JVM. Это обеспечивает языку практически полную независимость от машины, на которой производится запуск. Совокупность этих факторов и популярность смартфонов c ОС Android позволяет Java возглавлять список самых популярных языков по версии Tiobe, а нам — рекомендовать его начинающим разработчикам в качестве первого или основного. Если взглянуть на этот же самый рейтинг, в конце второго десятка можно отыскать современные языки программирования. Например, Swift — продукт компании Apple, популярный не только за счет своих качеств, но и благодаря громкому имени производителя. Будущее Уже сейчас появляются языки программирования, которые можно назвать языками сверхвысокого уровня. Они предназначены не для написания прикладных программ, а для обработки больших массивов данных и статистики. В их числе R, MATLAB и Julia. Можно предполагать, что в будущем появятся человекоориентированные языки, на которых написать программу будет не сложнее, чем пост в ЖЖ. С другой стороны, квантовые компьютеры потребуют свой особый, квантовый ассемблер. Элементы ЯП могут рассматриваться на следующих уровнях: • алфавит — совокупность символов, отображаемых на устройствах печати и экранах и/или вводимых с клавиатуры терминала. Обычно это набор символов Latin-1 с исключением управляющих символов. Иногда в это множество включаются неотображаемые символы с указанием правил их записи (комбинирование в лексемы); • лексика — совокупность правил образования цепочек символов (лексем), образующих идентификаторы (переменные и метки), операторы, операции и другие лексические компоненты языка. Сюда же включаются зарезервированные (ключевые) слова ЯП, предназначенные для обозначения операторов, встроенных функций и пр. Иногда эквивалентные лексемы, в зависимости от ЯП, могут обозначаться как одним символом алфавита, так и несколькими. Например, операция присваивания значения в ЯП Basic обозначается как «=», а в языке Pascal — «:=». Операторные скобки в Си задаются символами «{» и «}», а в Pascal — Begin и End. Граница между лексикой и алфавитом, таким образом, является весьма условной, тем более что компилятор обычно на фазе лексического анализа заменяет распознанные ключевые слова внутренним кодом (например, Begin — 512, End — 513) и в дальнейшем рассматривает их как отдельные символы; • морфология — совокупность правил и возможностей варьирования написания лексических единиц, в пределах которых они будут правильно распознаны компилятором. Например, для оператора перехода в некоторых реализациях Basic записи go, goto, до to эквивалентны, а в ЯП FoxPro наименования команд и ключевые слова могут быть сокращены вплоть до 4-х начальных букв (например, эквивалентны команды report, repor, repo); • синтаксис — совокупность правил образования языковых конструкций или предложений ЯП — блоков, процедур, составных операторов, условных операторов, операторов цикла и пр. Особенностью синтаксиса является принцип вложенности (рекурсивность) правил построения конструкций. Это значит, что элемент синтаксиса языка в своем определении прямо или косвенно в одной из его частей содержит сам себя. Например, в определении оператора цикла телом цикла является оператор, частным случаем которого является все тот же оператор цикла; • семантика — смысловое содержание конструкций, предложений языка. Семантический анализ — это проверка смысловой правильности конструкции. Например, если мы в выражении используем переменную, то она должна быть определена ранее по тексту программы, а из этого определения может быть получен ее тип. Исходя из типа переменной, можно говорить о допустимости операции с данной переменной. Семантические ошибки возникают при недопустимом использовании операций, массивов, функций, операторов и пр. • зарезервированные (служебные) слова, имеющиеся в каждом ЯП, могут быть использованы только по своему специальному назначению (как имена функций, операторов, операций и пр.). В табл. 1.19 в качестве примера приводится список зарезервированных слов Basic. |