Лекции по дисциплине «Языки и системы программирования» (стр. 5 )

Партнерка на США и Канаду по недвижимости, выплаты в крипто

30% recurring commission
Выплаты в USDT
Вывод каждую неделю
Комиссия до 5 лет за каждого referral

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

продуктом?

сложности?

Эти вопросы были сформулированы американским программистом Фредериком Бруком в 1968 году. Они актуальны и в настоящее время. Сегодняшнее содержание раздела «Инженерия программирования» изменяется весьма динамично и отражает большое количество направлений. Перечислим некоторые из них:

o процесс разработки программного обеспечения;

o формирование требований к программному продукту;

o обратная (реверсивная) инженерия (реинжиниринг)- процесс восстановления спецификации из кода;

o тестирование;

o сопровождение и эволюция программного обеспечения;

o архитектура программного обеспечения;

o объектно-ориентированное моделирование;

o инженерия программирования и «промежуточное» (между сетевой операционной системой и программой пользователя) программное обеспечение;

o анализ программного обеспечения;

o формальные спецификации;

o математические основания инженерии программирования;

o инженерия программирования и производительность программного продукта;

o инженерия программирования для реального времени;

o инженерии программирования для мобильных систем;

o инструментарий и окружение инженерии программирования;

o инженерии программирования и Интернет;

o экономика программного обеспечения;

o метрики программного обеспечения;

o инженерия программирования как учебная дисциплина.

· Инструментальное направление, изучающее системы программирования. Сюда входят все инструменты, поддерживающие процесс программирования. Особое место в инструментарии занимают современные CASE-средства, которые охватывают обширную область поддержки многочисленных технологий проектирования ИС: от простых средств анализа и документирования до полномасштабных средств автоматизации, покрывающих весь жизненный цикл ПО.

Основные области программирования представлены тремя группами. Каждая группа - это объединение двух достаточно близких направлений. Они представлены на рис 2.

Рис.2.

Лекция 8

Создание сложных программных приложений.

1. Программные продукты и их основные характеристики

2. Понятие программного обеспечения

3. Характеристики качество ПО

4. Проектирование программного продукта

5. Структура программного продукта

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

Программные продукты и их основные характеристики

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

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

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

В настоящее время на мировом рынке господствуют компьютеры разного типа: VAX и IBM и языки, совместимые с этими машинами. Программы, написанные для одной машине, не всегда подходят к другой.

Для разработчика это творчество, для заказчика это удобный инструмент.

В Японии 60% трудоспособного населения занимается программированием.

Понятия программного обеспечения

Программирование – это сфера действий, направленная на создание программ.

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

Приложение – это программная реализация на компьютере решения задачи.

Программное обеспечение (ПО) - это программные продукты и техническая документация к ним.

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

Программы являются критерием развития вычислительной техники.

Проблемы, возникающие при создании программных продуктов:

1. Быстрая смена вычислительной техники и алгоритмических языков.

2. Не стыковка машин друг с другом (VAX и IBM).

3. Отсутствие полного взаимопонимания между заказчиком и исполнителем к разработанному программному продукту.

Характеристики качества ПО

Перечень показателей качества:

- документированность,

- эффективность,

- простота использования,

- удобство эксплуатации,

- мобильность,

- совместимость,

- испытуемость,

- стоимость.

Критерии оценки качества программы.

НЕ нашли? Не то? Что вы ищете?

Программа должна:

1. работать согласно техническому заданию (и это легко проверяется);

2. быть эффективна по быстродействию и памяти (или быстрее работать или занимать меньше памяти);

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

4. быть приспособлена к выявлению ошибок (достаточно надежна в процессе расчета получать достоверные результаты);

5. должна быстро разработана и отлажена с минимальными трудозатратами.

0.5. Проектирование программных продуктов (ПП)
0.5.1. Классификация методов проектирования ПП
Неавтоматизированное проектирование алгоритмов и программ используется при разработке небольших по трудоемкости и структурной сложности ПП. Автоматизированное проектирование используется в крупных фирмах при разработке определенного класса ПП большого коллектива разработчиков. .Структурное проектирование – это последовательная декомпозиция, целенаправленное разбиение на отдельные составляющие. Структурное проектирование включает в себя: - нисходящее проектирование ("сверху вниз"), - модульное программирование, - структурное программирование (кодирование). Информационное моделирование – построение комплекса взаимосвязанных моделей данных. Объектно-ориентированный подход основан на: - выделении классов объектов; - установлении свойств объектов и методов их обработки; - создании иерархии классов, наследовании свойств объектов и методов их обработки. Каждый объект объединяет данные и программу обработки этих данных и относится к определенному классу. Основная цель ООП - преодолеть следующие недостатки проектирования “сверху вниз”: - недостаточное внимание к структурам данных, - слабая связь структур данных с процессами их обработки.	Проектирование алгоритмов и программ – наиболее ответственный этап жизненного цикла ПП. Традиционное неавтоматизированное проектирование алгоритмов и программ используется при разработке небольших по трудоемкости и структурной сложности ПП, не требующих большого числа разработчиков. ПП имеют прикладной характер. Автоматизированное проектирование алгоритмов и программ возникло с необходимостью уменьшить затраты на проектные работы, сократить сроки их выполнения, создать типовые "заготовки", многократно тиражируемых для различных разработок, координации работ большого коллектива разработчиков Методология –это подходы к проектированию Начало развития падает на 60-е годы. Метод нисходящего проектирования предполагает последовательное разложение общей функции обработки данных на простые функциональные элементы ("сверху вниз"). В основе Информационного моделирования лежит положение об определяющей роли данных при проектировании алгоритмов и программ. Структурное программирование основано на модульной структуре программного продукта и базовых алгоритмических структурах. Кроме того, ООП позволяет резко сократить объем и трудоемкость подготовки программ, имеющих дело с множеством связанных друг с другом объектов. Объектно-ориентированный анализ – это выявление объектов, определение свойств и методов обработки объектов, установление их взаимосвязей. ООП процесс объектной декомпозиции и представления с использованием моделей данных проектируемой системы на логическом и физическом уровнях.
0.5.2. Этапы создания ПП	0.5
Составление технического задания на программирование. На этом этапе требуется: · определить тип ОС - MS DOS, Windows, Windows NT, · оценить необходимость сетевого варианта работы программы, · определить необходимость разработки программы, · обосновать необходимость работы с БД под управлением СУБД, · выбрать методы решения задачи, · разработать обобщенный алгоритм решения комплекса задач и структуры данных, · определить требования к интерфейсу пользователя. Технический проект. На этом этапе выполняется: · разработка детального алгоритма обработки данных, · определение состава общесистемного программного обеспечения, включающего базовые средства (ОС, модель БД, электронные таблицы), · разработка внутренней структуры ПП, образованной отдельными программными модулями, · выбор средств разработки программных модулей. 3. Рабочая документация (рабочий проект). На этом этапе осуществляется: · разработка программных модулей, · программирование или создание программного кода, · отладка программного продукта, · испытание работоспособности программных модулей и базовых программных средств, · подготовка контрольного примера, для проверки соответствия ПП заданию, · создание эксплуатационной документации на программный продукт: – Описание применения; – Руководство пользователя; – Руководство программиста (оператора). – Обучающей системы (для ПП массового применения) 4. Ввод в действие. Готовый программный продукт сначала проходит опытную эксплуатацию, а затем сдается в промышленную эксплуатацию.	Создание программных продуктов трудоемкий процесс, основанный на определенной технологии. которую можно переносить на различные платформы. Разрабатывают функциональную структуру алгоритма или состав объектов, определяют требования к комплексу технических средств системы. Пример: для создания MS DOS - приложений может быть использован язык программирования Visual Basic for DOS Standard, Fortran, Visual C++ for Windows. Если необходима переносимость программ на другие ЭВМ, выбирается среда Windows NT. При разработке программ, работающих в среде Windows, возможно применение технологии OLE, для создания приложений. Приложение может работать с БД различных СУБД. - характеристика программного изделия с указанием сферы его применения; - детальное описание функциональных возможностей и технологии работы с программным продуктом; - указывает особенности установки программного продукта. Тиражирование и распространение ПП

0.6. Структура программных продуктов ( ПП ).

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

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

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

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

Программный продукт обладает внутренней структурой.

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

– разработки,

– программирования,

– отладки,

– внесения изменения в ПП.

Структуризация ПП преследует следующие цели:

· Распределить работы по исполнителям, обеспечив их загрузку и требуемые сроки разработки;

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

· Контролировать трудозатраты и стоимость проектных работ.

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

Среди множества модулей различают:

Г о л о в н о й модуль – управляет запуском ПП; (Существует в единственном числе.)

· У п р а в л я ю щ и й модуль – обеспечивает вызов других модулей на обработку;

· Р а б о ч и е модули - выполняют функции обработки

· С е р в и с н ы е модули и библиотеки, утилиты – осуществляют обслуживающие функции.

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

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

Структура ППП многомодульная.

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

0.7.1. Диалоговый режим

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

Большинство ПП работают в Диалоговом режиме.

Состав диалоговых систем:

· Меню – пользователю предлагается выбор альтернативных функций обработки из фиксированного перечня;

Меню может содержать вложенные подменю.

· Действия запрос-ответ – фиксированный перечень возможных значений, выбираемых из списка или ответы типа Да/Нет;

· Запрос по формату - с помощью ключевых слов, фраз.

Диалоговый процесс управляется согласно созданному сценарию, для которого определяются:

· Момент начала диалога;

· Инициатор диалога – человек или ПП;

· Параметры и содержание диалога – сообщения, состав и структура меню, экранные формы;

· Реакция ПП на завершение диалога.

Для создания диалогового процесса и интерфейса пользователя используют объектно-ориентированные средства разработки программ (Delphi).

В их составе содержатся:

· Построители меню (для создания главного меню и вложенного подменю);

· Конструктор экранных форм (для разработки форматов экранного ввода и редактирования данных).

Диалоговые окна содержат элементы управления:

· Тексты сообщения;

· Поля ввода информации пользователя;

· Списки возможных альтернатив для выбора;

· Кнопки, переключатели и т. п.

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

0.7.2. Графический интерфейс пользователя

Реализуется для ПП, работающих в среде Windows. Обязательный компонент большинства современных ПП.

К нему предъявляются высокие требования с инженерной и художественной стороны разработки.

Строится в виде системы ниспадающих меню с использованием в качестве средства манипуляции мыши и клавиатуры.

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

Требования к графическому интерфейсу:

1. Содержать привычные и понятные пользователю пункты меню, соответствующие функциям обработки;

2. Ориентироваться на пользователя, который общается с программой на внешнем уровне взаимодействия;

3. Удовлетворять правилу "шести" – в одну линейку меню включать не более 6 понятий, каждое из которых содержит не более 6 опций;

4. Сохранять стандартизированное назначение и местоположение на экране графических объектов

Лекция 9

Методы сортировки и поиска информации

1. Сортировака

1.1. Сортировка методом простого выбора

1.2. Сортировка методом простого обмена

1.3. Сортировка методом прямого включения

1.4. Сортировка методом слияний

1.5. Обменная сортировака с разделением (сортировка Хоара)

2. Алгоритмы поиска информации

2.1. Линейный поиск

2.2. Линейный поиск с использованием барьера

2.3. Бинарный поиск

3. Поиск подстроки в строке

3.1. Прямой поиск

3.2. Бойера и Дж. Мура

4. Пример

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

Данные, например, элементы массива, можно отсортировать:

· по возрастанию – каждый следующий элемент больше предыдущего:

a[1] < a[2] < ... < a[n];

· по неубыванию – каждый следующий элемент не меньше предыдущего:

a[1] ≤ a[2] ≤ ... ≤ a[n];

· по убыванию – каждый следующий элемент меньше предыдущего:

a[1] > a[2] > ... >a[n];

· по невозрастанию – каждый следующий элемент не больше предыдущего: a[1] ≥ a[2] ≥ ... ≥ a[n].

Простейшими примерами могут служить следующие задачи.

Сортировка

Сортировка методом простого выбора

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

1. выбрать максимальный элемент массива;

2. поменять его местами с последним элементом ( после этого наибольший элемент будет стоять на своем месте );

3. повторить пп.1-2 с оставшимися n-1 элементами, то есть рассмотреть часть массива, начиная с первого элемента до предпоследнего, найти в ней максимальный элемент и поменять его местами с предпоследним (n-1) - м элементом массива и так далее, пока не останется один элемент, уже стоящий на своем месте.

Всего потребуется n-1 раз выполнить эту последовательность действий. В процессе сортировки будет увеличиваться отсортированная часть массива, а не отсортированная, соответственно, уменьшаться.

Рассмотрим этот процесс на примере. Пусть исходный массив а состоит из 10 элементов и имеет вид:

5 10 2

После сортировки массив должен выглядеть так:

13 16

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

1-й шаг: рассмотрим весь массив и найдем в нем максимальный элемент -16 ( он стоит на седьмом месте ); поменяем его местами с последним элементом.

5 10 2

Максимальный элемент помещен на свое место.

2-й шаг: рассмотрим часть массива с первого до девятого элемента. Максимальный элемент этой части стоит на втором месте и имеет значение 13. Поменяем его местами с последним элементом этой части.

510 16

Отсортированная часть массива состоит теперь уже из двух элементов.

3-й шаг: снова уменьшим рассматриваемую часть массива на один элемент. Здесь нужно поменять местами второй элемент ( его значение 10 ) и последний элемент этой части ( его значение 4 ).

513 16

В отсортированной части массива теперь стало 3 элемента.

4-й шаг: аналогично.

13 16

5-й шаг: максимальный элемент этой части массива является последним в ней, поэтому его нужно оставить на своем месте.

13 16

Далее действуем аналогично.

6-й шаг:

13 16

7-й шаг:

13 16

8-й шаг:

13 16

9-й шаг:

13 16

Итог: 13 16

Для программной реализации этого процесса необходимо организовать цикл по длине рассматриваемой части массива, которая изменяется от n до 2. В качестве начального значения максимума разумно взять значение последнего элемента рассматриваемой части.

Теперь можем записать алгоритм сортировки:

For i: = n Downto 2 Do

Begin

найти максимальный элемент из a[1], ..., a[i]; запомнить его индекс в переменной

k; если i<>k поменять местами a[i] и a[k]

End;

Опишем этот алгоритм подробно:

program n1;

type ar=array [1..10] of integer;

var i:integer;

a:ar;

Procedure sorting1(var a:ar);

{поскольку в процессе работы процедуры массив изменится, формальный

параметр а описывается как параметр-переменная}

var i, j,k:integer;

m:integer;

{значение максимального элемента рассматриваемой части массива}

begin

for i:=10 downto 2 do

{цикл по длине рассматриваемой части массива}

begin

{поиск максимального элемента и его номера в текущей части массива}

k:=i;

m:=a[i];

{начальные значения максимального элемента и

его индекса в рассматриваемой части массива}

for j:=2 to i-1 do

if a[j]>m then begin k:=j; m:=a[k] end;

if k<>i then

begin {перестановка элементов}

a[k]:=a[i];

a[i]:=m;

end;

begin

writeln('Введите исходный массив:');

for i:=1 to 10 do read(a[i]);

sorting1(a);

writeln('Отсортированный массив:');

for i:=1 to 10 do write(a[i],' ');

writeln;

end.

При решении практических задач упорядочивание x1,...xn как правило сопровождается некоторыми дополнительными действиями. Например, если x1, y1, x2, y2, ..., xn, yn - это значения аргумента x и некоторой функций y=f(x), то перестановка x1, ..., xn должна сопровождаться перестановкой y1, ..., yn. Элементы y1, ..., yn переставляются так же, как x1, ..., xn вне зависимости от значений самих

y1, ..., yn. Рассмотрим эту задачу; переставленные значения x1, y1, x2, y2, ..., xn будут выведены в два столбца:

x1 y1

x2 y2

.....

xn yn

program tab;

const n=5;

type u=array[1..n] of real;

var x, y:u;

v:real;

i, j,k:integer;

begin

for i:=1 to n do read(x[i],y[i]);

for i:=1 to n do begin

k:=i;

for j:=i+1 to n do

if x[j]<x[k] then k:=j;

v:=x[i]; x[i]:=x[k]; x[k]:=v;

v:=y[i]; y[i]:=y[k]; y[k]:=v;

writeln(x[i],y[i]);

end;

end.

Сортировка методом простого обмена

Сортировка методом простого обмена может быть применена для любого массива. Этот метод заключается в последовательных просмотрах массива слева направо ( от начала к концу ) и обмене местами соседних элементов, расположенных “неправильно”, то есть таких, что i < j, а a[i] > a[j]. Опишем этот метод подробнее.

Начнем просмотр с первой пары элементов ( a[1] и a[2] ), если первый элемент этой пары больше второго, то меняем их местами, иначе оставляем без изменения. Затем берем вторую пару элементов ( a[2] и a[3] ), если a[2] > a[3], то меняем их местами и так далее. На первом шаге будут просмотрены все пары элементов массива a[i] и a[i+1] для i от 1 до n-1. В результате максимальный элемент массива переместится в конец массива.

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

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

Пример

Отсортируем по возрастанию методом простого обмена массив из 5 элементов:

Длина текущей части массива - n-k+1, где k - номер просмотра, i - номер проверяемой пары; номер последней пары - n-k. За вертикальной чертой располагаются отсортированные элементы.

Первый просмотр: рассматривается весь массив.

i = 1 5 >

обмен

i = 2 4 5 < 8 2 9

нет обмена

i = 3 4 5 8 > 2 9

обмен

i = 4 < 9

нет обмена

9 стоит на своем месте.

Второй просмотр: рассматриваем часть массива с первого до четвертого элемента.

i = 1 4 < 5 2 8 ½ 9

нет обмена

i = 2 4 5 > 2 8 ½ 9

обмен

i = 3 4 2 5 < 8 ½ 9

нет обмена

8 стоит на своем месте.

Третий просмотр: рассматриваемая часть массива содержит три первых элемента.

i = 1 4 > 2 5 ½ 8 9

обмен

i = 2 2 4 < 5 ½ 8 9

нет обмена

5 стоит на своем месте.

Четвертый просмотр: рассматриваем последнюю пару.

i = 1 2 4 < 5 ½ 8 9

нет обмена

4 стоит на своем месте.

Для самого маленького элемента ( 2 ) остается только одно место - первое.

Итак, наш массив отсортирован по возрастанию элементов методом простого обмена. Этот метод называют также методом “пузырька”. Название это происходит от обратной интерпретации, при которой в процессе выполнения сортировки более “ легкие ” элементы ( элементы с заданным свойством ) мало - помалу всплывают на “поверхность”.

Программа “пузырьковой” сортировки.

program n2;const n=5;type ar=array [1..n] of integer;

var i:integer;

a:ar;

procedure sorting2(var a:ar);

var k, i,t:integer;

{k - номер просмотра (изменяется от 1 до n-1)

i - номер рассматриваемой пары

t - промежуточная переменная для перестановки местами элементов}

begin

for k:=1 to n-1 do

{цикл по номеру просмотра}

for i:=1 to n-k do

if a[i]>a[i+1] then

{перестановка элементов}

begin

t:=a[i];

a[i]:=a[i+1];

a[i+1]:=t;

end;

begin

writeln('Введите исходный массив:');

for i:=1 to n do read(a[i]);

sorting2(a);

writeln('Отсортированный массив:');

for i:=1 to n do write(a[i],' ');

writeln;

end.

Сортировка методом прямого включения

Сортировка методом прямого включения, так же как и сортировка методом простого выбора, обычно применяется для массивов, не содержащих повторяющихся элементов.

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

а [1] ≤ а [2] ≤ ... ≤ a [k-1].

Далее необходимо взять k - й элемент и подобрать для него такое место в отсортированной части массива, чтобы после его вставки упорядоченность не нарушалась, то есть надо найти такое j ( 1 ≤ j ≤ k -1 ), что а [j] ≤ a[k] < a[j+1]. Затем вставить элемент а [k] на найденное место.

С каждым шагом отсортированная часть массива увеличивается. Для выполнения полной сортировки потребуется выполнить n-1 шаг.

Рассмотрим этот процесс на примере. Пусть требуется отсортировать массив из 10 элементов по возрастанию методом прямого включения

1 - й шаг

13 5 7 Рассматриваем часть массива из одного эле-