Программирование. Основы
Алгоритмизация и программирование
Основные этапы решения задачи
- Постановка задачи. Задача формулируется на естественном языке
- Разработка мат. модели.
- Выбор численного метода решения задачи.
- Разработка алгоритма.
- Составление программы на выбранном языке программирования.
- Тестирование и отладка программы. (Отладка — это устранение ошибок. Тестирование- проверка правильности работы.) Разработка тестов и контрольных примеров.
- Оценка полученных результатов. Сопоставление реальных и ожидаемых результатов. Если результаты неудовлетворительны, возврат к некоторым предыдущим этапам.
- Разработка документации. Текстовое описание программы. Разработка инструкций пользователю — лицу, применяющему разработанную программу в своей работе.
Жизненным циклом программы называют весь период ее разработки и эксплуатации.
Что такое алгоритм
Алгоритм — однозначная последовательность действий, приводящая к требуемому результату.
Свойства алгоритма
- Определенность. Каждый шаг точно определяет какое-либо действие. Не допускается двусмысленность, аппеляции к «здравому смыслу» и т.п.
- Детерминированность. После окончания выполненного шага должно быть однозначно определено какой шаг будет следующим.
- Конечность (или результативность). Алгоритм должен (для корректно заданных исходных данных) приводить к решению задачи за конечное число шагов.
- Массовость. Один и тот же алгоритм можно применять к различным исходным данным. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма.
Не всегда выполняется свойство конечности. Например, некоторые диалоговые алгоритмы строятся как бесконечные, работу которых можно прекратить лишь внешним воздействием: нажатием некоторых клавиш, перезагрузкой компьютера. Такой подход считается непрофессиональным.
Свойство массовости может нарушаться, если алгоритм используется для получения одного конкретного результата или в демонстрационных целях. В этом случае алгоритм использует только данные, определяемые самим алгоритмом и не использует исходных данных, вводимых пользователем при запуске программы.
Способы описания алгоритмов
- Блок-схемы. Детальное описание таким методом каждого оператора используется только для коротких алгоритмов, умещающихся в 1 страницу. Для больших алгоритмов блок-схема получается громоздкой, объем ее бывает больше самой программы, и переход с одной страницы на другую очень усложняет ее чтение. Часто применяется при укрупненном представлении алгоритма, когда одной фигурой изображается какая-то выделенная часть программы, а не отдельный оператор.
- Псевдокод. Способ точного описания алгоритма предложениями на естественном языке. Применяется наиболее часто.
Системы программирования
Система программирования это комплекс программных средств, предназначенных для кодирования, тестирования и отладки программного обеспечения. Имеет интерфейс, удобный пользователю.
Такие комплексы, как правило, включают следующие программные модули.
- Текстовые редакторы, служащие для создания текстов исходных программ.
- Компиляторы, предназначенные для перевода исходного текста на входном языке в язык машинных кодов. В результате создаются объектные модули. Это программы на машинном языке, они записываются на диск с расширением .exe.
- Компоновщики, позволяющие объединять несколько объектных модулей, порождаемых компилятором, в одну программу. В результате создается загрузочный модуль.
- Загрузчики, обеспечивающие подготовку готовой программы к выполнению.
- Библиотеки прикладных программ, содержащие в себе наиболее часто используемые подпрограммы в виде готовых объектных модулей.
- Отладчики, выполняющие программу в заданном режиме (например, пошаговом) с целью поиска, обнаружения и локализации ошибок. Используются на этапе компиляции.
Основным модулем системы программирования всегда является компилятор. Именно технические характеристики компилятора, прежде всего, влияют на эффективность результирующих программ, порождаемых системой программирования. Напомним основные термины и понятия.
- Транслятор — это программа, которая переводит входную программу на исходном (входном) языке в эквивалентную ей выходную программу на результирующем (выходном) языке. Близко по смыслу к этому понятию понятие компилятор.
- Компилятор — это транслятор, который осуществляет перевод исходной программы в эквивалентную ей объектную программу на языке машинных команд или языке ассемблера (.exe файл). Таким образом, компилятор отличается от транслятора тем, что его результирующая программа написана обязательно на языке машинных команд или языке ассемблера. Результирующая программа транслятора в общем случае может быть написана на любом языке (например, транслятор с языка Pascal на язык С). Таким образом, компиляторы — это вид трансляторов. Напомним также, что существует еще принципиально отличное понятие: интерпретатор.
- Интерпретатор – это программа, которая воспринимает входную программу на исходном языке, переводит каждый оператор или строку в машинный язык и выполняет их. Интерпретатор не порождает результирующую программу и никакого результирующего кода. Интерпретаторы удобны для быстрой отладки программ, тем самым укорачивая обычный цикл разработки. Однако с другой стороны, интерпретаторы в сравнении с компиляторами обычно проигрывают по скорости выполнения в несколько раз.
Языки программирования
Самым первым языком программирования был язык машинных кодов (двоичный язык). Программа записывалась как элементарные машинные действия: сложение, сравнение двух величин, пересылка по заданному адресу, извлечение из ячейки памяти с заданным адресом. Причем все команды и числа записывались в двоичном коде. В настоящее время практически не применяется.
Следующий этап - язык Ассемблер (мнемокод) — это тот же язык процессора, но адреса и команды в двоичной системе заменены символьными именами. Он позволяет программисту присваивать удобные имена ячейкам и областям памяти, а также задавать наиболее удобные схемы адресации.
Язык Макроассемблер является расширением языка Ассемблера.
Программирование становилось более продуктивным, да и вообще, более привлекательным. Но даже на ассемблере программировать было не очень-то приятно, кроме того, ассемблеры аппаратно зависимы - то есть, если планировалось использовать программы на компьютере от Dec, а не Intel, их приходилось переписывать заново. Почему же ассемблер используется до сих пор?
Языки Ассемблера и Макроассемблера применяются системными программистами-профессионалами с целью использования всех возможностей оборудования ЭВМ и получения эффективной по времени выполнения и по требуемому объему памяти программы. На этих языках обычно разрабатываются относительно небольшие программы, входящие в состав системного программного обеспечения: драйверы, утилиты и другие. В программу, написанную на языке высокого уровня, можно делать вставки на ассемблере для повышения быстродействия программы.
Пожалуй, наиболее важной вехой в истории программирования, сравнимой по значимости разве что с изобретением письменности, можно считать переход от машинных кодов и ассемблера к языкам высокого уровня. Это языки, приближенные к естественному языку, в частности, к английскому.
К настоящему времени создано около 3 000 языков. Сейчас в практической деятельности применяются не более двух десятков языков. Некоторые известны узкому кругу специалистов определенной области. Другие, ранее широко известные, стали очень редко применяться в связи с созданием новых технологий (например, язык Кобол — язык экономических расчетов).
Языки высокого уровня не зависят от архитектуры компьютера. Чем более язык ориентирован на человека, тем выше его уровень.
Существуют различные классификации языков высокого уровня. Можно предложить следующую.
- процедурные
- объектно-ориентированные
- декларативные
Процедурное программирование
Программа на процедурном языке программирования состоит из последовательности операторов (инструкций), задающих ход решения задачи. Основным является оператор присваивания, служащий для изменения содержимого областей памяти. Выполнение программы сводится к последовательному выполнению операторов с целью преобразования исходного состояния памяти, то есть значений исходных данных, в заключительное, то есть в результаты. Таким образом, с точки зрения программиста имеются программа и память, причем первая последовательно обновляет содержимое последней.
Классическое процедурное программирование требует от программиста детального описания того, как решать задачу, т.е. формулировки алгоритма и его специальной записи. При этом ожидаемые свойства результата обычно не указываются. Основные понятия языков этих групп — оператор и данные (переменные).
Переменная на языке процедурного типа получает атрибуты: имя, тип, значение.
При процедурном подходе операторы объединяются в группы — процедуры.
Первым был Fortran. Он появился в 1957 году. Fortran - это сокращение от двух английских слов FORmula TRANslator - что переводится как "транслятор формул". Как видно из названия, первоначально язык создавался с целью использования при математических расчетах. Он предназначался для написания программ, используемых при решении прикладных технических задач. Для него за время его существования было написано множество удобных и полезных библиотек, он до сих пор иногда используется при программировании сложных вычислений. К тому же Fortran до сих пор продолжают изучать при подготовке по некоторым физико-математическим специальностям во многих университетах, где он остается профилирующим языком программирования.
Basic (Beginners All-purpose Symbolic Instruction Code) —представляет собой простой язык программирования, разработанный в 1964 году для использования новичками. Он был разработан как простейший язык для непосредственного общения человека с вычислительной машиной. Поэтому первоначально работа велась в интерактивном режиме с использованием интерпретаторов. В настоящее время для этого языка имеются также и компиляторы.
Согласно концепциям, заложенным в Basic, этот язык в смысле строгости и стройности является антиподом языка Pascal. В частности, в нем широко распространены различные правила умолчания, что считается плохим тоном в большинстве языков программирования подобного типа. Basic широко распространен на ЭВМ различных типов и очень популярен в среде программистов, особенно начинающих. Существует множество диалектов этого языка, мало совместимых между собой. Basic активно использует многие концепции и новинки из других языков. Поэтому он достаточно динамичен, и нельзя однозначно определить его уровень.
Язык Си. Большой отпечаток на современное программное обеспечение наложил язык Си (первая версия — 1972г.), являющийся очень популярным в среде разработчиков систем программного обеспечения (включая и ОС). Си сочетает в себе черты, как языка высокого уровня, так и машинно-ориентированного языка, допуская программиста ко всем машинным ресурсам, что не обеспечивают другие языки.
Pascal является одним из наиболее популярных среди прикладных программистов процедурным языком программирования. Разработанный в 1970 году швейцарским специалистом в области вычислительной техники профессором Н. Виртом, язык назван в честь французского математика и по замыслу автора предназначался для обучения программированию. Однако язык получился настолько удачным, что стал одним из основных инструментов прикладных и системных программистов при решении задач вычислительного и информационно-логического характера. В языке Pascal реализован ряд концепций, рассматриваемых как основа «дисциплинированного» программирования и заимствованных впоследствии разработчиками многих языков.
Одним из существенных признаков языка Pascal является последовательная и достаточно полная реализация концепции структурного программирования. Кроме того, в языке реализована концепция определения новых типов данных на основе уже имеющихся.
Pascal реализован на компьютерах различных типов, но наиболее распространен и развит для персональных компьютеров.. В настоящее время широко используются такие версии этого языка для ПЭВМ, как BorlandPascal и TurboPascal.
Объектно-ориентированное программирование
Принципиально иное направление в программировании связано с методологиями непроцедурного программирования. К ним можно отнести объектно-ориентированное программирование. Программы стали строиться не из процедур и функций, а из сравнительно простых кирпичиков-объектов, в которых были упрятаны данные и подпрограммы их обработки. Программирование рассматриваемого стиля заключается в выборе имеющихся или создании новых объектов и организации взаимодействия между ними.
Определения
Объект – это то, чем вы управляете с помощью программы ( например в Excel - ячейка, диапазон, диаграмма и т.п. В БД- это таблицы, формы, запросы). Каждый объект имеет свой тип (класс). Класс представляет собой тип данных, имеющий в составе данный объект.
Свойства - Параметры объекта (конечно, не все, а только необходимые в программе).
Методы - Действия, которые можно выполнять над объектом данного типа, или которые сам объект может выполнять. Это процедуры и функции.
Инкапсуляция. Инкапсуляция — это объединение данных и действий над ними. Это принцип, согласно которому любой класс должен рассматриваться как чёрный ящик — пользователь класса должен видеть и использовать только интерфейс (от английского interface — внешнее лицо, т. е. список декларируемых свойств и методов) класса и не вникать в его внутреннюю реализацию. Это свойство объектов, заключающееся в сокрытии информации о внутренней "жизни" объекта. Т.е. внешний пользователь объекта может использовать его возможности посредством определенного интерфейса, а непосредственно работа с данными и детали ее реализации от него скрыты. Так, в примере с жестким диском, нам для работы с ним достаточно знать, что он может хранить информацию, и позволяет записывать и считывать ее. При этом вовсе необязательно разбираться в том, каким образом хранится информация и как протекают процессы ее записи и чтения. Свойство инкапсуляции облегчает написание программ, и, что самое главное, их модификацию.
Наследование. Наследованием называется возможность порождать один класс от другого с сохранением всех свойств и методов класса-предка и добавляя, при необходимости, новые свойства и методы. Наследование призвано отобразить такое свойство реального мира, как иерархичность.
Полиморфизм Полиморфизмом называют явление, при котором для различных родственных объектов можно задать одинаковое название функции, но действия функция будет выполнять разные, в зависимости от конкретного объекта. Например, надо нарисовать прямоугольник или круг, в зависимости от типов: «прямоугольник», «круг». Но в обоих случаях функция будет иметь имя «Нарисовать». Т.е. действия с одинаковым именем вызывает различное поведение, в зависимости от типа данных.
К наиболее современным объектно-ориентированным языкам программирования относятся C++ и Java.
Языки C++ и Java. За основу языка С++ был взят язык С, дополненный элементами языков BCPL,Simula-67 и Algol-68.
Новая интегрируемая в Internet версия языка, получила название Java. С января 1995 года Java получает распространение в Internet. Принципиальной разницей между Java и C++ является то, что первый из них является интерпретируемым, а второй — компилируемым. Синтаксис языков практически полностью совпадает. С точки зрения возможностей собственно объектно-ориентированных средств язык Java обладает рядом преимуществ перед языком C++. Так, язык Java демонстрирует более гибкую и мощную систему, кроме того, он проще и надежнее.
В силу своей конструктивности идеи объектно-ориентированного программирования используются во многих универсальных процедурных языках, в которые входит специальная библиотека объектно-ориентированного программирования. Это системы программирования TurboVision, VisualBasic, Delphi и др.
Visual Basic подходит для написания небольших и нетребовательных к ресурсам программ. А так как он является языком создания приложений Microsoft Office, то он получил самое широкое распространение.
Delphi является очередным шагом в эволюции компиляторов Паскаля. Среда Delphi стала, по сути, лучшим средством программирования для операционной системы Windows. У языка Delphi есть еще одно очень важное преимущество перед остальными коммерчески успешными языками — он великолепно подходит для обучения программированию. Поэтому его рекомендуют в качестве первого языка для всех учеников и студентов, собирающихся стать профессиональными программистами.
Delphi, Java применяются для создания программ , используемым в Интернете.
Визуальное программирование
В последнее время многие программы, в особенности объектно-ориентированные, реализуются как системы визуального программирования. Отличительной особенностью таких систем является мощная среда разработки программ из готовых «строительных блоков», позволяющая создать интерфейсную часть программного продукта в диалоговом режиме, практически без кодирования программных операций. К числу объектно-ориентированных систем визуального программирования относятся; Visual Basic, Delphi, Visual C++.
Раньше, создание пользовательского интерфейса требовало уйму времени и сил, особенно когда программа должна была работать под управлением операционной системы Windows и иметь графический пользовательский интерфейс. Визуальное программирование сделало эту задачу доступной и начинающему программисту.
Декларативное программирование
Такие языки еще называют языками символьной обработки. Языки символьной обработки сыграли важную роль в программировании. Программист указывает исходные информационные структуры, взаимосвязи между ними и то, какими свойствами должен обладать результат. При этом процедуру его получения («алгоритм») программист не строит (по крайней мере, в идеале). В этих языках отсутствует понятие «оператор» («команда»). Декларативные языки можно подразделить на два семейства — функциональные (Лисп) и логические (типичный представитель — Пролог).
Функциональные языки. ЛИСП, Haskell
Логические языки. Пролог
Языки декларативного программирования могут претендовать на роль языков сверхвысокого уровня.
В последнее время в связи развитием Интернет-технологий получили распространение так называемые скриптовые языки. Скрипт — это набор команд на максимально понятном языке для человека, который может не знать стандартных языков программирования, но нуждается в автоматизации процесса работы с определенной программой. Программы такого типа существовали и раньше, они назывались командными файлами (файлами с расширением .bat).
Характерными особенностями данных языков являются, во-первых, их интерпретируемость (компиляция либо невозможна, либо нежелательна), во-вторых, простота синтаксиса. Было создано достаточно большое количество таких языков, наиболее часто используемые: PHP, TCL, JavaScript, Perl, Python.
Язык HTML (язык разметки Wed страниц в итернете) предоставляет авторам Web-страниц большие возможности для отображения текстовой и графической информации. Но создаваемые с помощью языка HTML страницы остаются статическими - пользователи не могут изменить информацию, расположенную на странице, а так же использовать большинство интерфейсных элементов. Для того чтобы сделать страницу по-настоящему интерактивной, нам нужен еще один язык, выполняемый в контексте браузера, - скриптовый язык.
Скриптовый язык используется для создания интерактивных страниц. Этот язык программирования предоставляет средства для управления браузером. Обычно он не содержит всех возможностей настоящих языков программирования, таких, например, как работа с файлами или управление графикой. Созданные с помощью скриптовых языков программы не могут выполняться самостоятельно - они работают только в контексте браузера, поддерживающего выполнения скриптовых программ. К таким браузерам относятся Microsoft Internet Explorer и Netscape Navigator. Создаваемые на скриптовых языках программы, называемые сценариями или скриптами, включаются в состав Web-страниц и распознаются и обрабатываются браузером отдельно от остального HTML - кода.
Отметим общую тенденцию в развитии языков программирования. Языки развиваются в сторону все большей и большей абстракции. И это сопровождается падением эффективности. Вопрос: а стоит ли этого абстракция? Ответ: стоит. Стоит, так как повышение уровня абстракции влечет за собой повышение уровня надежности программирования. С низкой эффективностью можно бороться путем создания более быстрых компьютеров. Если требования к памяти слишком высоки, можно увеличить ее объем. Это, конечно, требует времени и средств, но это решаемо. А вот с ошибками в программах можно бороться только одним способом: их надо исправлять. А еще лучше — не совершать. А еще лучше максимально затруднить их совершение. И именно на это направлены все исследования в области языков программирования. А с потерей эффективности придется смириться. Но это пока не относится к системному программированию, где эффективность программы важна.
При обучении программированию в настоящее время чаще всего используют универсальные процедурные языки, в которые входят специальные библиотеки объектно-ориентированного и визуального программирования. Это системы программирования TurboVision, VisualBasic, Delphi и др.
Поэтому важно рассмотреть правила разработки программ с использованием процедурных языков.
Требования к программе
- Правильность. Программа должна соответствовать алгоритму, а значит — приводить к правильному результату.
- Надежность — безотказная работа при различных исходных данных, для того диапазона, для которого составлена программа.
- Эффективность. Под эффективностью понимают время выполнения программы и требуемый объем оперативной памяти. Чем эти величины меньше, тем эффективнее программа.
- Удобство пользования. Удобство ввода исходных данных и чтения результатов. Читаемость программы.
Первые два пункта должны безусловно выполняться. А 3-й и 4-й пункты иногда приходят в противоречие. Что из них должно приоритетным?
На начальном этапе программирования старались получить наиболее эффективную программу, не заботясь об удобстве пользования. Этому способствовали очень слабые ресурсы вычислительной техники и отсутствие опыта. Это приводило к тому, что программой мог пользоваться только ее автор, да и тот через некоторое время с трудом мог это делать. Использовать и модифицировать чужую программу иногда было сложнее, чем составить новую. Практически все профессиональные программисты в настоящее время согласились с тем, что к созданию программы надо относиться так же, как к созданию любого товара. Поэтому в настоящее время эффективность уступает удобству пользования. (Конечно все это делается в разумных пределах. Кроме того, бывают исключения, когда главной становится эффективность). Возникли специальные методы и правила составления программ. К этим методам относится:
- Структурное программирование.
- Модульне программирование.
- Программирование сверху-вниз.
Структурное программирование
Это понятие относится к процедурному программированию. В широком смысле — структурное программирование — создание удобных в пользовании программ. В узком смысле — программирование в соответствии со структурной теоремой. Ее доказали итальянцы Бом и Якопини.
Теорема: Всякая программа может быть составлена из 3-х основных блоков: функционального блока, развилки и обобщенного цикла.
Основное свойство этих конструкций — 1 вход и 1 выход. Кроме того, две последние конструкции можно представить как обобщенный функциональный блок. Эти блоки в программе не будут пересекаться. Поэтому программа будет читаться свеху-вниз, без переходов. Основой структурного программирования является отказ от оператора GO TO — оператора безусловного перехода. Программа становится легко читаемой. Если нет переходов, то отпадает необходимость рисовать блок-схемы. Алгоритмы пишут на псевдокоде. Блок-схемы рисуют лишь укрупнено, изображая лишь отдельные модули, чтобы показать связи.
Жесткое требование структурного программирования — использовать только эти 3 конструкции. Более мягкое — разрешается использовать оператор выбора и другие операторы, не нарушающие свойство блоков: «1 вход — 1 выход». Оператор GO TO разрешается использовать в исключительных случаях, и только вперед. Обычно исключительными случаями бывают досрочный выход из цикла и досрочное окончание выполнения программы. В современных языках программирования есть для этого специальные операторы.
Модульное программирование
Модулем, в данном случае, будем называть отдельные, особо оформленные части программы (процедуры и функции). Модули имеют 1 точку входа и 1 точку выхода.
Исторически эта технология возникла из-за того, что в программах часто встречаются одни и те же повторяющиеся действия. Для того, чтобы не писать одно и тоже несколько раз, такой блок стали оформлять отдельно, а затем просто вызывать в нужных местах.
Дальнейшее развитие этой технологии привело к тому, что модульная программа — это такая программа, в которой изменения в любом модуле не вызывает изменений в остальных частях программы. Значит, главная особенность — это независимость модулей. Каждый модуль, в свою очередь, может быть разделен на несколько модулей. В результате программа будет иметь иерархическую структуру.
Преимущества:
- Отдельные модули можно изменять, заменять их на другие - это не вызовет изменения в других частях программы. Это делает программу более гибкой и уменьшает количество ошибок. Такую программу легче составлять и отлаживать.
- Отдельные модули могут программировать разные люди, причем им необязательно знать, как работает вся программа. Позволяет использовать коллективный труд, и необязательно все программисты должны иметь высокую квалификацию. Это повышает производительность и уменьшает стоимость программы.
- Позволяет более рационально использовать память.
Программирование сверху-вниз
Его называют иногда нисходящим программированием. Существует такое определение: это проектирование программ путем последовательного разбиения большой задачи на меньшие подзадачи. Но это общее определение.
Это понятие относится к технологии разработки программы. Эта технология возникла при разработке больших программ, над которыми работали несколько программистов. Каждый разрабатывал и отлаживал свои модули. Затем все это надо было соединить и провести отладку и тестирование всей системы. Обычно этот процесс занимает длительное время. Каждый модуль работает правильно, а система неработоспособна и ошибку найти трудно. Испытание систем в некоторых разработках длилось от 2 до 3 лет, что иногда вызывало отказ от проекта.
Так возникла следующая технология, которая теперь используются даже для небольших задач, состоящих из отдельных модулей.
Сначала проектируется главная программа. Обычно она содержит ввод исходных данных, вызов подпрограмм первого уровня иерархии и вывод результатов.
Отладка главной программы начинается до того, как разработаны подпрограммы, которые на этом этапе заменяются фиктивными подпрограммами ( называются заглушками), они содержат только вход и выход. На этом этапе производятся только связи между главной программой и подпрограммами первого уровня (обычно через формальные и фактические параметры). Далее разрабатываются сами подпрограммы первого уровня, а подпрограммы более низкого уровня заменяются заглушками и т.д.
На каждом этапе основное внимание уделяется связям. К отладке приступают до того, как завершена вся программа.
Основная идея — на каждом уровне не обращают внимания на описания модулей нижних уровней.
При отладке на каждом уровне разработанные модули добавляют в программу по одному.
Основное достоинство — упрощает отладку и тестирование. Исключает отладку на уровне системы.
Иногда сочетают нисходящее (сверху - вниз) и восходящее (снизу-вверх) программирование. Бывает так, что уже имеются ранее разработанные и отлаженные модули или стандартные модули. В этом случае поступают в соответствии с порядком нисходящего программирования, т.е. включают модули по одному на нужном уровне.