• Главная
• Контакты
• Нашёл ошибку
• Прислать материал
• Добавить в избранное

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

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

В качестве примера можно привести алгоритм прыжка в длину с разбега: разбег – отталкивание – полет – приземление. Из примера видно, что последовательность этапов прыжка в длину поменять местами невозможно, так как она разбита на элементарные фазы. В обычной жизни с алгоритмом решения какой-либо задачи мы можем столкнуться, например, при изготовлении различных кулинарных изделий и т. д.

Слово «алгоритм» происходит от «algorithmi» – латинской формы написания имени великого математика IX в. аль-Хорезми, который сформулировал правила выполнения арифметических действий. Первоначально под алгоритмами и понимали только правила выполнения четырех арифметических действий над многозначными числами. В дальнейшем это понятие стали использовать вообще для обозначения последовательности действий, приводящих к решению поставленной задачи.

Любой алгоритм обладает рядом свойств:

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

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

3. Результативность алгоритма. Выполнение алгоритма должно приводить к получению определенного результата после конечного числа шагов.

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

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

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

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

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

На примере квадратного уравнения рассмотрим процесс создания алгоритма.

Пусть есть квадратное уравнение:

ax² + bx + c = 0

1. Вычислим значение дискриминанта:

D = b²– 4ac

2. Если значение дискриминанта больше или равно нулю, то вычисляем корни уравнения:

3. Если дискриминант меньше нуля, то уравнение действительных корней не имеет.

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

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

Алгоритм может быть описан следующими способами:

• Словесно-формульное описание алгоритма, т. е. описание алгоритма с помощью слов или формул. Например, кулинарный рецепт.

• Графическое описание алгоритма, т. е. описание с помощью схем.

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

• Описание алгоритма на алгоритмическом языке.

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

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

Выделяют следующие виды алгоритмов:

– Линейный;

– Разветвляющийся;

– Циклический.

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

Блок-схема нахождения периметра прямоугольного треугольника при известных длинах его катетов имеет следующий вид (рис. 8.1):

Рисунок 8.1. Блок-схема линейного алгоритма

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

Блок-схема алгоритма решения квадратного уравнения выглядит следующим образом (рис. 8.2):

Рисунок 8.2. Блок-схема разветвляющегося алгоритма

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

Задача № 3. Построить блок-схему возведения числа a в степень n (рис. 8.3).

Рисунок 8.3. Блок-схема циклического алгоритма

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

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

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

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

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

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

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

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

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

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

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

К языкам программирования высокого уровня можно отнести следующие: Fortran, Cobol, Algol, Pascal, Basic, C, C++, Java, HTML, Perl и другие.

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

Существует два основных вида трансляторов (рис. 8.4): интерпретаторы, которые сканируют и проверяют исходный код в один шаг, и компиляторы, сканирующие исходный код для производства текста программы на машинном языке, которая затем выполняется отдельно.

Рисунок 8.4. Виды трансляторов

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

Одно, часто упоминаемое преимущество интерпретаторной реализации состоит в том, что она допускает «непосредственный режим». Непосредственный режим позволяет вам задавать компьютеру задачу и возвращает вам ответ, как только вы нажмете клавишу ENTER. Кроме того, интерпретаторы имеют специальные атрибуты, которые упрощают отладку. Можно, например, прервать обработку интерпретаторной программы, отобразить содержимое определенных переменных, бегло просмотреть программу, а затем продолжить исполнение. Однако интерпретаторные языки имеют недостатки. Необходимо, например, иметь копию интерпретатора в памяти все время, тогда как многие возможности интерпретатора, а следовательно, и его возможности могут не быть необходимыми для исполнения конкретной программы. При исполнении программных операторов интерпретатор должен сначала сканировать каждый оператор с целью прочтения его содержимого (что этот человек просит меня сделать?), а затем выполнить запрошенную операцию. Операторы в циклах сканируются излишне много.

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

Процесс создания программы называется программированием.

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

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

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

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

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

Возможность применения подпрограмм относит язык программирования к классу процедурных языков.

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

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

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

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

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

Подпрограммы решают три важные задачи:

• избавляют от необходимости многократно повторять в тексте программы аналогичные фрагменты;

• улучшают структуру программы, облегчая ее понимание;

• повышают устойчивость к ошибкам программирования и непредвидимым последствиям при модификациях программы.

В середине 80-х годов в программировании возникло новое направление, основанное на понятии объекта. До того времени основные ограничения на возможность создания больших систем накладывала разобщенность в программе данных и методов их обработки.

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

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

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

Объектно-ориентированный язык программирования характеризуется тремя основными свойствами:

1. Инкапсуляция – объединение данных с методами в одном классе;

2. Наследование – возможность создания на основе имеющегося класса новые классы с наследованием всех его свойств и методов и добавлением собственных;

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

1. Что такое алгоритм? Приведите пример.

2. Какими свойствами обладает алгоритм?

3. Какие способы используются для описания алгоритма?

4. Какие алгоритмы различают? Приведите примеры.

5. Что такое язык программирования?

6. В чем отличие языков программирования от естественных?

7. По какому принципу различаются языки программирования?

8. Охарактеризуйте машиннозависимые языки программирования.

9. Дайте характеристику машиннонезависимым языкам программирования.

10. Для чего используются трансляторы?

11. В чем отличие компилятора от интерпретатора?

12. Какие виды программирования выделяют?

13. Дайте характеристику алгоритмическому программированию.

14. В чем заключается особенность структурного программирования?

15. Для чего используются подпрограммы и какие они бывают?

16. Охарактеризуйте объектно-модульное программирование.

17. Какие основные свойства присущи объектно-ориентированному языку программирования?