Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
тех прог / Лекция 2. Парадигмы программирования.docx
Скачиваний:
30
Добавлен:
09.02.2016
Размер:
73.54 Кб
Скачать

11

ЛЕКЦИЯ 2. Парадигмы программирования 1.Понятие парадигмы программирования 2. Императивное программирование 3. Параллельное и событийно-управляемое программирование 4. Объектно-ориентированное программирование 5. Функциональное программирование 6. Логическое программирование 7. Структурное программирование   8. Модульное программирование Сортировка 1.1. Сортировка методом простого выбора 1.2. Сортировка методом простого обмена 1.3. Сортировка методом прямого включения 1.4. Сортировка методом слияний 1.5. Обменная сортировка с разделением (сортировка Хоара) Алгоритмы поиска информации Линейный поиск Линейный поиск с использованием барьера Бинарный поиск Поиск подстроки в строке Прямой поиск Понятие парадигмы программирования

Парадигма – базоая модель конкретного способа организации информации. Например, ОО-парадигма делает упор на поведении и обязанностях.

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

Парадигма – методологияметоднотацияструктура - средство

Парадигмы программирования – это лишь различные инструменты, которые можно использовать при программировании. Каждый из этих инструментов по-своему хорош. Но это не значит, что они "эффективно универсальны". То есть, на самом деле, различные методики программирования дают разный выигрыш для решения задач разных классов. Этот выигрыш можно мерить по двум параметрам:

  • эффективность программного обеспечения на современных ЭВМ

  • общие затраты на разработку программного обеспечения

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

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

Структурированность программы позволяет повысить уровень декларативности, то есть, еще сильнее оторваться от деталей архитектуры конкретного компьютера и программировать практически в терминах предметной области задачи. В алгоритмической части многие современные языки на самом деле поддерживают в явном виде несколько парадигм программирования. Для описания синтаксиса программы используется грамматика в расширенной форме Бекуса-Науэра. В правой части таких грамматик допускается использование следующих "регулярных операций": A B - последовательно А, затем В. A | B - альтернатива. Читается: "A или B". A* - произвольное количество повторений (в том числе - 0 раз) А. Читается: "последовательность А". A # B - эквивалентно A ( B A )*. Читается: "последовательность А через В". Терминальные символы выделяются подчеркиванием.

  1. Императивное программирование

Автомат, последовательно изменяющий свои состояния под управлением некоторой схемы, наиболее просто реализуется технически. Поэтому первые компьютеры были императивными. И остались такими и в наши дни, несмотря на все эксперименты с оригинальными вычислительными устройствами. Даже типичное определение алгоритма, как описание последовательности действий для решения какой-либо задачи, несет на себе сильнейший отпечаток императивного подхода. Стоит ли говорить о том, почему императивное программирование - практически наиболее "популярное"? Одна из характерных черт императивного программирования - наличие переменных с операцией "разрушающего присвоения". То есть, была переменная А, было у нее значение Х. Алгоритм предписывает на очередном шаге присвоить переменной А значение Y. То значение, которое было у А, будет "навсегда забыто". Вот что на практике означает "переход между состояниями под управлением функции переходов". Синтаксис описания алгоритмов в простейшем языке программирования, поддерживающем императивную модель программирования, мог бы быть таким: Оператор ::= Простой оператор | Структурный оператор Простой оператор ::= Оператор присваивания | Оператор вызова | Оператор возврата Структурный оператор ::= Оператор последовательного исполнения | Оператор ветвления | Оператор цикла Оператор присванивания ::= Переменная := Выражение ; Оператор вызова ::= Имя подпрограммы (Список параметров ) ; Оператор возврата ::= return [ Выражение ] ; Оператор последовательного исполнения ::= begin Оператор* end Оператор ветвления ::= if Выражение then Оператор* (elseif Выражение then Оператор*)* [ else Оператор* ] end Оператор цикла ::= while Выражение do Оператор* end Императивное программирование наиболее пригодно для реализации небольших подзадач, где очень важна скорость исполнения на современных компьютерах. Кроме этого, работа с внешними устройствами, как правило, описывается в терминах последовательного исполнения операций ("открыть кран, набрать воды"), что делает такие задачи идеальными кандидатами на императивную реализацию.

3. Структурное программирование

Сутью структурного программирования является возможность разбиения программы на составляющие элементы. Идеи структурного программирования появились в начале 70-годов в компании IBM, в их разработке участвовали известные ученые Э. Дейкстра, Х. Милс, Э. Кнут, С. Хоор. Распространены две методики (стратегии) разработки программ, относящиеся к структурному программированию: программирование "сверху вниз" и программирование "снизу вверх". Программирование "сверху вниз", или нисходящее программирование – это методика разработки программ, при которой разработка начинается с определения целей решения проблемы, после чего идет последовательная детализация, заканчивающаяся детальной программой. Является противоположной методике программирования «снизу вверх». При нисходящем проектировании задача анализируется с целью определения возможности разбиения ее на ряд подзадач. Затем каждая из полученных подзадач также анализируется для возможного разбиения на подзадачи. Процесс заканчивается, когда подзадачу невозможно или нецелесообразно далее разбивать на подзадачи. В данном случае программа конструируется иерархически - сверху вниз: от главной программы к подпрограммам самого нижнего уровня, причем на каждом уровне используются только простые последовательности инструкций, циклы и условные разветвления. Программирование "снизу вверх", или восходящее программирование – это методика разработки программ, начинающаяся с разработки подпрограмм (процедур, функций), в то время когда проработка общей схемы не закончилась. Является противоположной методике программирования «сверху вниз». Такая методика является менее предпочтительной по сравнению с нисходящим программированием, так как часто приводит к нежелательным результатам, переделкам и увеличению времени разработки. Рассмотрим следующий пример. Разработать программный комплекс, который рисует на экране дисплея дачный участок, состоящий из дороги, забора, елки и сияющего на небе солнца. Нарисованная картина показана на рис. 1. Рис. 1. Дачный участок.

Укажем в виде схем, которые называются структурными диаграммами, составные элементы картины:  Посмотрим на изображение дома. Здесь можно выделить следующие элементы:Дальнейшая детализация стены, крыши, двери, окна, трубы, дороги, забора и солнца нецелесообразна. Елка состоит из двух элементов:Если объединить все приведенные структурные диаграммы, то получим первый вариант изображения структурной диаграммы программного комплекса, показанный на рис. 2.Рис. 2. Структурная диаграмма (первый вариант) Второй вариант представления структурной диаграммы имеет вид, представленный на рис. 3.Рис. 3. Структурная диаграмма (второй вариант) На рис. 2 и рис. 3 отмечены уровни, занимаемые программными модулями. Каждый нижележащий уровень соответствует более полной детализации программного комплекса. Те модули, которые не имеют дальнейшей детализации, например, "солнце", "ствол", "стена", являются процедурами, или функциями, реализующими решение соответствующей подзадачи. Разбиение программы на модули представляет одну из достаточно ответственных и сложных задач, так как влияет на дальнейший ход разработки программного комплекса, его надёжность, эффективность, продолжительность тестирования и отладки, сопровождение и возможность использование стандартных программных процедур. Достоинства структурного программирования: 1)  повышается надежность программ (благодаря хорошему структурированию при проектировании, программа легко поддается тестированию и не создает проблем при отладке); 2)  повышается эффективность программ (структурирование программы позволяет легко находить и корректировать ошибки, а отдельные подпрограммы можно переделывать (модифицировать) независимо от других);

3)  уменьшается время и стоимость программной разработки; 4)  улучшается читабельность программ.  

Резюме Технология структурного программирования при разработке серьезных программных комплексов, основана на следующих принципах: -   программирование должно осуществляться сверху вниз; -   весь проект должен быть разбит на модули (подпрограммы) с одним входом и одним выходом; -   подпрограмма должна допускать только три основные структуры – последовательное выполнение, ветвление (if, case) и повторение (for, while, repeat). -   недопустим оператор передачи управления в любую точку программы (goto); -   документация должна создаваться одновременно с программированием в виде комментариев к программе. Структурное программирование эффективно используется для решения различных задач, имеющих алгоритмический характер.  

Соседние файлы в папке тех прог