Мои Конспекты
Главная | Обратная связь

...

Автомобили
Астрономия
Биология
География
Дом и сад
Другие языки
Другое
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Металлургия
Механика
Образование
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Туризм
Физика
Философия
Финансы
Химия
Черчение
Экология
Экономика
Электроника

АЛГОРИТМИЗАЦИЯ И ПРОГРАММИРОВАНИЕ





Помощь в ✍️ написании работы
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

6.1.Классификация языков программирования

 

Языки программирования являются искусственными языками, в них синтаксис и семантика строго определены. Поэтому языки программирования, в отличие от естественных языков, не допускают многозначных и произвольных толкований.

Синтаксис – это набор правил, которые определяют основные внутренние структуры и последовательности символов, допустимых в языке программирования. Семантика – это значения языковых единиц (слов, словосочетаний, предложений).

Составление программ для ЭВМ первого поколения велось исключительно на машинном языке, который представляет собой свод правил кодирования действий ЭВМ с помощью чисел. Для всех ЭВМ «понятна» только двоичная система счисления (СС), которая для сокращения записи часто заменяется восьмеричной или шестнадцатеричной СС.

Более высоким уровнем, по сравнению с машинными языками, являются машинно-ориентированные языки символического кодирования. Основной принцип при создании языков символического кодирования состоит в замене машинных кодов на их буквенные обозначения, а также в автоматизации процесса распределения памяти и диагностики ошибок. Такой машинно-ориентированный язык получил название языка Ассемблера.

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

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

Недостатком машинно-ориентированных языков является невозможность выполнения программы, составленной для процессора одного типа, на ЭВМ, которая построена на процессоре другого типа. Другими словами вид программы зависит от типа машины.

На следующем уровне развития языков находятся процедурно-ориентированные языки. В отличие от машинно-ориентированных языков, синтаксис и семантика этих языков не зависят от состава имеющихся команд конкретной ЭВМ (конкретного процессора). Привязку составленной программы к конкретному типу ЭВМ осуществляет транслятор (программа-переводчик).

После ввода в ОЗУ исходной программы, составленной на языке высокого уровня, осуществляется ее трансляция. В результате создается программа на машинном языке, т.е. программа, состоящая из команд того процессора (той машины), с помощью которого будет решаться задача.

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

Второй способ – интерпретация – предполагает, что отдельные операторы (или другие части исходной программы) сразу после трансляции выполняются, после чего та же процедура совершается над другими операторами и т.д. При интерпретации во время выполнения рабочей программы транслятор находится в ОЗУ, т.е. занимает дополнительный объем оперативной памяти. Кроме того, процесс решения задачи замедляется, т.к. между отдельными этапами выполнения рабочей программы управление передается транслятору.

Интерпретатор как бы «переводчик устной речи». Переводит и выполняет программу последовательно, строку за строкой.

Компилятор как бы «письменный переводчик». Перед выполнением программы переводит весь текст полностью.

Интерпретатор работает медленнее, чем компилятор, занимает больше места в оперативной памяти. Однако при отладке новых программ удобнее работать с интерпретатором, так как он позволяет после исправления ошибки продолжить выполнение программы с места остановки. При работе с компилятором после устранения ошибки необходимо повторно компилировать программу и запустить ее с самого начала, а не с места расположения обнаруженной ошибки.

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

Запись программы на процедурно-ориентированном языке достаточно близка к общепринятой математической записи, компактна и удобна для восприятия.

Рассмотрим, как выглядит операция суммирования двух чисел, например 7 и 5, запрограммированная на различных языках:

a) на машинном языке:

 

Адрес Команда
1101 0001 0011 1111
1101 0010 0000 0101
1101 0011 0000 0110
1101 0100 0000 0111
1101 0101 1000 0000

 

b) на машинно-ориентированном языке (микропроцессорный комплект 580-й серии) MVI A,5 MVI B,7 ADD B;

c) на процедурно-ориентированном языке A = 7 + 5.

Из приведенных примеров видно, что наиболее проста для понимания последняя запись.

Одним из первых процедурно-ориентированных языков стал язык Фортран (FORmula TRANslation – преобразование формул). Фортран является компилирующим языком. Он не только просуществовал до наших дней, но и удерживает одно из первых мест в мире по распространенности. Среди причин такого долголетия можно отметить простую структуру как самого Фортрана, так и предназначенных для его преобразования в машинные коды трансляторов. Фортран используется в сфере научных и инженерно-технических вычислений.

Язык Фортран продолжает развиваться и совершенствоваться, оказывая сильное влияние на создание и развитие других языков программирования, например, Фортран заложен в основу диалогового языка Бейсик (Basic – многоцелевой язык символических команд для начинающих).

Язык Бейсик позволил привлечь к изучению технологии программирования большое число людей из различных предметных областей (непрофессионалов программистов). В момент его создания он предназначался в основном для обучения программированию. Современные версии языка Бейсик позволяют решать сложные задачи на профессиональном уровне.

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

Алгол-60(ALGOritmic Language – алгоритмический язык) – это более совершенный язык, чем Фортран. Он обладает большей гибкостью и надежностью программ.

Решение экономических задач (учет материальных ценностей, выпущенной предприятием продукции, личного состава) в 60-х годах ХХ столетия удобно было выполнять на языке Кобол.

Языки Лисп и Пролог были разработаны для решения задач, относящихся к искусственному интеллекту. Эти языки позволяют обрабатывать текстовую (символьную) информацию, решать логические и математические задачи. Например, на базе языка Лисп разработана известная математическая система Derive.

Язык Пролог является непроцедурным языком логического программирования. Он выбран основным языком при разработке ЭВМ пятого поколения, которые будут обладать искусственным интеллектом.

Язык Лого используется для обучения детей основам программирования.

Обилие алгоритмических языков, появившихся в период разработки и внедрения второго поколения ЭВМ, объясняется невозможностью ни одним из существовавших языков удобно описывать разнообразные задачи. Третье поколение ЭВМ поставило на повестку дня вопросы поиска нового подхода к созданию универсального алгоритмического языка. Одной из попыток такого родя является создание фирмой IBM языка ПЛ/1. Он основан на языках Фортран, Алгол и Кобол.

В 1971 г. появилась публикация с описанием языка Паскаль, который является преемником Алгола-60. Он имеет конструкции, аналогичные существующим в ПЛ/1 и Алголе-60, однако более лаконичные. В Паскале проводятся идеи структурного программирования. Благодаря хорошей структурированности программ, написанных на языке Паскаль, над разработкой сложных проектов могут одновременно работать несколько программистов.

На основе Паскаля в конце 70-х годов ХХ века по заказу Министерства обороны США во Франции был разработан язык Ада. Язык Ада используется при разработке программного обеспечения для компьютерных систем, встроенных в самонаводящиеся ракеты, космические объекты, самолеты. Эти системы работают в реальном масштабе времени, где накладываются жесткие требования на быстродействие. Язык Ада поддерживает параллельное выполнение задач в многомашинных и в многопроцессорных вычислительных системах. В этом случае программа распараллеливается и выполняется на нескольких процессорах.

Язык СИ достаточно полно отражает возможности современных компьютеров, позволяя писать весьма эффективные программы, не прибегая к сложным языкам Ассемблера. На этом языке написана популярная операционная система UNIX.

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

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

Кроме языков Ада и Линда, существуют и другие языки параллельного программирования, например, Erlang, Modula, Occam.

Перспективным направлением дальнейшего развития технологии программирования явилось создание объектно-ориентированныхязыков.

Объекты представляют собой многократно используемые программные модули. Структурно объекты состоят из двух частей: методов и переменных.

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

Однотипные объекты объединяются в классы.

Объектно-ориентированное программирование (ООП) характеризуется следующими тремя признаками: инкапсуляцией, наследованием и полиморфизмом.

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

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

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

Полиморфизм – присвоение единого имени процедуре, которая передается по иерархии объектов, с выполнением этой процедуры способом, соответствующим каждому объекту в иерархии.

Первым объектно-ориентированным языком программирования был Simula 67 (Симула). Он разработан в конце 60-х годов ХХ столетия в Норвегии, для решения задач моделирования. Он был реализован как интерпретируемый язык.

Типичные современные объектно-ориентированные языки – это Си++ или Smaltalk, содержащие инструменты, которые максимально облегчают повторное использование созданных програм-мных модулей, имеют все основные признаки объектно-ориентированных языков, в том числе наследование, полиморфизм и инкапсуляцию данных.

Дельфи (Delphi) разработан фирмой Borland на базе языка Турбо-Паскаля. Чаще всего этот язык программирования используется для работы с базами данных по технологии клиент-сервер. Основной упор в Дельфи делается на максимальном повторном использовании имеющихся программ. Это позволяет разработчикам строить приложения из уже существующих объектов, а также дает им возможность создавать свои собственные объекты.

Первая версия Visual Basic появилась в 1991 г. Он близок к объектно-ориентированным языкам, но по-прежнему остается процедурным языком.

Этот язык широко распространен, он интегрирован в пакеты Microsoft Office: СУБД MS Access, электронные таблицы MS Excel, текстовый редактор MS Word.

Язык гипертекстовой разметки HTML (Hyper Text Markup Language) был предложен Тимом Бернерсом-Ли в 1989 г. в качестве основного компонента технологии распределенной гипертекстовой системы Word Wide Web (WWW).

Результирующий документ, составленный на языке HTML, кроме текста, может содержать иллюстрации, аудио- и видеофрагменты. В основу гипертекстовой разметки положена теговая модель описания документа.

Теги (иногда таги или тэги) – это скобки, между которыми записаны команды, указывающие, как отображать данный фрагмент текста Web-страницы.

Язык DHTML (Dynamic Hyper Text Markup Language) является расширением, развитием языка HTML. Он позволяет создавать динамические, движущиеся объекты, подсвечивающиеся кнопки, бегущие строки и др.

Для придания Web-страницам интерактивности используется язык PERL. Язык является интерпретируемым. Он создан программистом Лари Уоллом (Larry Wall) для обработки текстов и файлов. С помощью PERL Web-дизайнеры реализуют интерактивные средства Интернет: гостевые книги, чаты, поисковые системы, доски объявлений, службы рассылок виртуальных открыток и др. Пользователь имеет возможность заполнить соответствующие формы на Web-странице, и введенная информация будет обработана с по-мощью программ, написанных на PERL.

Язык моделирования виртуальной реальности Virtual Reality Modeling Language (VRML), предложенный консорциумом W30, предназначен для описания сред, имитирующих трехмерное пространство. Он является расширением гипертекстового языка разметки HTML, используемого для описания плоских изображений.

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

Чаще всего язык VRML применяется в архитектуре для моделирования и проектирования зданий и помещений, в торговле – для выбора вариантов удобной компоновки мебели и оборудования, в химии – для визуализации молекул в процессе синтеза.

Язык Java (джава или ява) предназначен для составления программ (приложений), которые работают в сетях. Программы, написанные на языке Java, часто используются для создания динамической рекламы в глобальной сети (анимация, телетайпные ленты, мерцающие надписи). Java-приложения «оживляют» статические картинки Web-страниц и тем самым привлекают внимание пользователей.

Язык Java является объектно-ориентированным языком. Java позволяет разрабатывать и настраивать приложения (программы). В то же время Java во многом сохраняет синтаксис и стиль программирования языков С и С++.

Достоинством языка является то, что он независим от конкретной архитектуры ЭВМ, и Java-приложения могут работать на различных типах ЭВМ (на различных процессорах), под управлением различных операционных систем: Windows, UNIX, Macintosh и др. Такое свойство особенно привлекательно при работе в глобальной сети, состоящей из множества ЭВМ, реализованных на различных платформах.

Язык поддерживает технологию клиент-сервер. С помощью языка Java сложные приложения разбиваются на небольшие модули, которые называются компонентами (приложениями) или апплетами (applets). Компоненты располагаются на сервере и при работе передаются по сети на ЭВМ клиента (пользователя), где и исполняются.

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

Программный эмулятор виртуальной Java-машины включен в состав распространенных программ-исследователей глобальных сетей (браузеров), таких, как Microsoft Интернет Explorer и Netscape Navigator.

Корпорация SUN Microsystems и Netscape Communications создали язык JavaScript.

JavaScript относится к языкам сценариев, которые позволяют «склеивать» готовые компоненты (вызывать подпрограммы при совершении каких-то событий). JavaScript не единственный язык управления сценариями просмотра документов. Язык VBScript, созданный на основе языка Visual Basic, используется для решения таких же задач.

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

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

Сведения о некоторых языках программирования приведены в табл. 6.1.

Таблица 6.1

Основные языки программирования

 

Язык Годы разработки Автор Фирма, организация
Ada Ада 1979-1980 Jean Ichbiah Cil-Honeywell Bull (Франция)
Algol Алгол   International committee
APL АПЛ 1961-1962 Kenneth Iverson, Adin Falkoff IBM
DELPHI Дельфи   Borland
BASIC Бейсик 1964-1965 John Kemeny, Thomas Kurtz Dartmouth College
C СИ 1972-1973 Dennis Ritchie Bell Laboratories

Продолжение табл. 6.1

 

Язык Годы разработки Автор Фирма, организация
C++   Bjarne Stroustrup Bell Laboratories
COBOL Кобол 1959-1961 Grase Murray Hopper  
FORTRAN Фортран 1950-1958 John Backus IBM
HTML Тим Бернерс-Ли CERN (Женева)
LISP Лисп 1956-1960 John McCarthy  
LOGO ЛОГО 1968-1970 Seymour Papert Massachusetts Institute of Techn.
Pascal Паскаль 1967-1971 Niklaus Wirth Federal Institute of Technology (Швейцария)
Turbo-Pas-cal Турбо-Паскаль Андерс Хейлсберг Borland
PERL Larry Wall  
PL/1 ПЛ/1 1964-1966   IBM
PROLOG Пролог Алан Калмероэ  
SIMULA Симула Оле-Йохан Дал, Кристен Нигаард Норвежский ВЦ
Java Джава Джеймс Гослинг Sun Microsystems

 

 

6.2.Основные типы и способы представления алгоритмов

 

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

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

Существуют следующие формы представления алгоритмов: словесная; графическая.

Словесная форма представления алгоритма используется для описания очень простых задач и на начальных стадиях разработки алгоритма. Словесная форма представления алгоритма имеет ряд недостатков. Для достаточно сложных алгоритмов описание становится слишком громоздким и ненаглядным.

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

Условные графические обозначения символов, используемых для составления структурной схемы алгоритма, стандартизированы. Некоторые часто используемые обозначения приведены в табл. 6.12.

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

 

 

Таблица 6.2

Блоки структурной схемы

  Процесс (вычисления) а   Решение (проверка условия)   a   b  
  Предопределенный процесс (подпрограмма) 0.15a   а     b   Ввод-вывод   a   b 0.25a  
  Соединительные линии       Модификация (начало цикла) a   a     b  
  Начало-конец     0.5a     b   Комментарии     a    
Внутри-страничный соединитель   0.5a     Межстраничный соединитель 0.5a   0.5a    

 

Примечание. Значение a принимается из ряда чисел 10; 15; 20… мм; b = 1,5 a.

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

Алгоритм, записанный на языке программирования, называется программой.

Алгоритм любой сложности может быть представлен комбинацией трех базовых структур:

  • линейные (следование);
  • разветвляющиеся;
  • циклические (повторение).

В линейном вычислительном процессе операторы выполняются в той последовательности, в которой они записаны (рис. 6.1).

Под оператором понимается формальная запись предписания для выполнения некоторой последовательности действий.

Вход

 

 

Выход

 

Рис. 6.1. Линейная структура (общий вид)

Разветвляющимися называются такие вычислительные процессы, в которых имеет место разветвление выполняемой последовательности действий в зависимости от результата проверки какого-либо условия. Альтернативные пути алгоритма помечаются соответствующими метками: истина/ложь, да/нет и ведут к общему выходу (рис. 6.2). В частном случае может оказаться, что для одного из выбранных путей действий предпринимать не нужно. Такая структура получила название «обход» или структура «если – то» (рис. 6.3).

 

 
 


Вход

 

Да Нет

 

 

Выход

 

Рис. 6.2. Разветвляющаяся структура ЕслиТо - Иначе

 
 


Вход

Да Нет

Выход

 

 

Рис. 6.3. Разветвляющаяся структура ЕслиТо(обход)

Циклические алгоритмы – это алгоритмы, в которых происходит повторение некоторой последовательности действий. Циклы бывают арифметические (число повторений заранее известно) и итерационные (число повторений неизвестно, выход их цикла осуществляется при выполнении некоторого условия). Итерационные циклы имеют две разновидности: «цикл – пока» и «цикл – до».

Группа операторов, повторяющихся в цикле, называется телом цикла. В арифметическом цикле задается управляющая переменная, которая изменяется от начального значения до конечного с определенным шагом (рис. 6.4).

Вход

 

Выход

 

 

Рис. 6.4. Арифметический цикл (цикл с параметром)

Основное отличие структуры «цикл – пока» от структуры «цикл – до» заключается в том, что в первой структуре проверка выхода из цикла производится до выполнения операторов тела цикла, а во втором случае – после.

 

Вход

 

 

Рис. 6.5. Цикл – пока

 

 

 
 

 


Рис. 6.6. Цикл – До

 

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

 

6.3. Технология программирования

 

Технология программирования определяет правила разработки и эксплуатации программных продуктов.

В технологии программирования жизненный цикл програм-много обеспечения разделяется на следующие этапы:

1) анализ требований;

2) проектирование;

3) кодирование (программирование);

4) отладка и тестирование;

5) эксплуатация и сопровождение.

Последний этап составляет 50 % жизненного цикла (первые три этапа – по 10 % жизненного цикла, четвертый – 20 %).

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

Этап анализа требований может состоять из следующих фаз:

1) фаза формулирования целей – получить от заказчика постановку задачи в виде описания задачи, проанализировать текст и определить цели, которые ведут к решению задачи;

2) фаза анализа – задача разбивается на подзадачи, между которыми определяются связи;

3) фаза формирования требований – определение конкретных требований для каждой подзадачи и для связей между подзадачами; формирование общего задания и его согласование с заказчиком.

В конце этапа анализа требований вырабатывается техническое задание.

Проектирование – на этом этапе определяется метод решения задачи. Исследуется структура программной системы и взаимодействие ее элементов. Можно выделить два этапа проектирования:

1) проектирование архитектуры программной системы;

2) детальное проектирование – проектирование структуры и интерфейсов компонентов, согласований их функций и технических требований, разработка описания программной системы.

Результатом этого этапа является логическая модель программной системы, основной частью которой является алгоритм решения задачи.

Доверь свою работу ✍️ кандидату наук!
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой



Поиск по сайту:







©2015-2020 mykonspekts.ru Все права принадлежат авторам размещенных материалов.