1. История развития и классификация языков программирования (по уровню близости к аппаратному обеспечению; по степени автоматизации процесса

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

История развития: 1. В машинных кодах; 2. Язык ASSEMBLER; 3. Язык FORTRUN 1954; 4. Язык COBOL 1960; 5. BASIC 1963; 6. PASCAL 1970 (Николас Вирт); 7. С 1972 (Ритчи, Кернеган).

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

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

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

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

Процедура – Часть программы выполняющая некоторые операции над данными в соответствии с задаваемыми параметрами. К процедурным языкам программирования относятся фортран, си, паскаль, Алгол.

Логическое программирование – класс языков, который основывается на символической логике. Пример: пролог. Логические языки программирования наиболее приспособлены для реализации в рамках вычислительных архитектур с высокой степенью параллелизма. Логические языки программирования являются основными при проектировании систем искусственного интеллекта, систем управления базами знаний и экспертных систем. Логические языки программирования позволяют хранить информацию в базах фактов и знаний, которые представляются в них в виде решающих правил. Вычисления сводятся к определению фактов и продуцированию выводов на основе логики вида «если существует факт 1, то сущ. факт 2» или «если истина А, то выполнить В».

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

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

Инкапсуляция – хранение в объекте данных и методов их обработки. Этот принцип позволяет жестко ограничить набор способов модифицирования данных. Наследование позволяет создавать объекты с использованием средств ранее использованных объектов. Полиморфизм позволяет автоматизировать процесс обработки данных за счет автоматического выбора способов обработки в зависимости от вида данных. Все это значительно повышает производительность.

Классификация языков программирования: 1. Неструктурный (преобразование машинных кодов на языке Assembler); 2. Модульные (задачи→подзадачи →алгоритмы→функции); 3. Логический подход; 4. Объектно-ориентированный подход; 5. Функциональный подход; 6. Смешанный подход; 7. Компонентно-ориентированный подход;

2. Понятие формального алгоритма. Тезис Тьюринга – Черча об эквивалентности различных определений вычислимости. Понятие формального алгори

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

1. он состоит из конечного множества простых команд, для которых однозначно определен порядок исполнения.

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

Тезис Тьюринга-Черча об эквивалентности различных определений вычислимости.

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

3. Абстрактная машина фон Неймана. Понятие об элементарном исполнителе.

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

1)ЦП – объединяющий в себе УУ(устройство управления) и АЛУ(арифметико-логическое устройство).

2) ЗУ - запоминающее устройство - память.

3)УВВ - устройство ввода-вывода.

Классификация памяти: 1.постоянная; 2.оперативная

Программы и данные должны храниться в памяти. Ввод/вывод осуществляется через устройство ввода/вывода. Общее управление осуществляет ЦП. Между УВВ и ЗУ предусмотрена связь, т. к. при выполнении медленных операций ввода-вывода, ЦП может выполнять другие вычисления, не требующие ввода-вывода. А специальное устройство – контроллер прямого доступа к памяти управляет процессом передачи данных между ЗУ и УВВ. Под программой понимают набор команд, извлекаемые в порядке их следования, либо в соответствии с управляющими командами. Данные хранятся в виде переменных, которые могут быть поименованы для последующей реализации и изменения. Программы данных хранятся в памяти. Память – последовательность ячеек для хранения порций информации. Доступ к информации ячеек осуществляется в соответствии с адресом (порядковым номером) информация хранится в двоичном виде.

Единица информации бит, байт – минимально адресуемая в памяти единица информации (1 байт=8 бит). Одним байтом может быть закодировано 28, т. е. 256 различных значений. Байты объединяются в слова, двоичные слова. Размер машинного слова – разрядность ЭВМ.

Классификация памяти: постоянная и оперативная.

В процессоре объединены два устройства - УУ - для считывания команд данных из памяти и общей координации команд и АЛУ - для простейших логических и арифметических операций.

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

Регистры специального назначения и регистры общего назначения:

РОН предназначены для логических и арифметических операций. РСН – в их состав входят счетчик команд; регистр состояния программы; регистр указателя стека. Счетчик команд хранит адрес следующей команды; регистр состояние программы – обязательно включает в себя флаги (1/0, да/нет, правда/ложь, true/false), характеризующие результат выполнения последней программы. Флаги используются для выполнения условных операций. Регистр стека – хранит адрес вершины стека. Стек – область памяти, доступ к которой осуществляется по принципу LIFO.

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

Команда пересылки.

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

Команды перехода.

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

Арифметические операции.

1) "+" (выполняется в прямом коде).

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

3) Умножение (выполняется как комбинация сложений и сдвигов).

4) Деление - комбинация вычитаний и сдвигов с определением частного и остатка.

5) Операции над числами с плавающей точкой.

6) Операции над действительными числами выполняются в зависимости от форм представления (с фиксированной или с плавающей точкой).

7) Выполняется в виде совокупности операций или над мантиссой и характеристикой числа.

Логические операции.

· И (++ = +, +- = -, -- = -)

· ИЛИ (++ = +, +- = +, -- = -)

· НЕ

· ИСКЛЮЧАЮЩЕЕ ИЛИ (++ = +, +- = неоднозначность, -- = -).

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

Понятие об элементарном исполнителе.

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

4. Основные этапы решения задач на ЭВМ: математическая постановка; алгоритм; программа; отладка и тестирование; сдача в эксплуатацию.

Основные этапы решения задач на ЭВМ.

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

2. Формальная постановка задачи. Форма представления – естественный язык или язык математики.

3. Разработка метода и алгоритма решения задачи. Форма представления – язык математики.

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

5. Перевод алгоритма на язык программирования. Форма представления – язык программирования.

6. Разработка системы тестов и отладка программы. Форма представления – язык программирования или машинный язык.

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

8. Обработка результатов вычисления и их интерпретация. Форма представления – математический или естественный язык.

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

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

Способы записи алгоритма.

Графический вид представления алгоритма в текстовом виде на псевдоязыке программирования (естественный язык с ограничениями для записи алгоритмической конструкцией).

Ошибки в программе включают в себя :

1. синтаксические ошибки, определяемые транслятором

2. ошибки этапа выполнения (ошибки арифметических операций (деление на 0), переполнение, потеря значимости…).

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

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

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

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

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

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

Эффективность программного обеспечения может характеризоваться двумя способами:

1. С учетом объема используемой памяти;

2. С учетом быстродействия программы.

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

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

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

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

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

Диалоговые программы.

1. Понятие интерфейса человек-компьютер;

2. Процессы ввода- вывода;

3. Структура диалога;

4. Поддержка пользователя.

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

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

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

1. Режим командной строки (программа получает параметры работы из строки ввода с помощью команд). Например, ОС MS-DOS.

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

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

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

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

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

3. Интерфейс должен быть не избыточным. Реализация этого требования определяется правилом: количество воспринимаемой информации ограничено количеством знаков восприятия.

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

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

7. Жизненный цикл программы (период от первоначальной концепции до морального устаревания: выработка требований к системе, разработка требов

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

Он включает в себя следующие этапы:

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

2. разработка требований к программному обеспечению;

3. общее проектирование;

4. детальное проектирование;

5. создание отдельных модулей;

6. тестирование отдельных модулей;

7. объединение модулей в систему;

8. выпуск системы;

9. эксплуатация и сопровождение системы.

Например при разработке АС было принято следующее разграничение фаз жизненного цикла программы:

1). Предпроектное исследование объекта.

2). Оформление технического задания - документа, содержащего спецификацию всех информационных и управляющих функций с указанием входов/выходов, а также требования к видам обеспечения ОС: математическим, лингвистическим, техническим, организационным.

3). Разработка технического проекта (все функции описаны подробно).

4). Разработка рабочего проекта (прототипа системы).

5). Экспериментальное внедрение.

6). Сдача в промышленную эксплуатацию.

7). Промышленная эксплуатация системы.

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

8. Постановка задачи и спецификация программы (представление в виде спецификации ввода–вывода; особенности спецификации для завершающихся и

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

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

Способы записи алгоритмов.

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

9. Способы конструирования программ (простое кодирование алгоритма; нисходящее проектирование – метод пошаговой детализации).

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

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

Нисходящее проектирование – метод пошаговой детализации

Нисходящее проектирование.

1) по алгоритму программы создается текст главного модуля, содержащего в виде комментариев основны6е этапы решения задачи. Желательно, чтобы каждая строка комментария представляла собой вызов подпрограммы, решающей подзадачу главной задачи

2) основные этапы заменяются строчкой кода, представляющего собой вызов функции, соответствующей этапу решения задачи. Выбирается имя функции, тип возвращаемого значения и определяется список параметров.

3) По каждой вновь созданной1 функции записывается определение. Тело функции содержит комментарии. Процедура повторяется до тех пор, пока комментарии не будут заменены кодом на языке С

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

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

Создание программы с использованием технологии нисходящей (сверху-вниз) разработки с пошаговой детализацией. Эта технология является неотъемлемой частью создания хорошо структурированных программ. Она начинаем с записи псевдокода вершины. Вершина — это единственное предложение (оператор), выражающее общее назначение программы. Таким образом, вершина отображает всю про­грамму в целом. К сожалению, вершина редко отображает достаточное количество деталей, на основании которых можно написать программу на C++. Поэтому надо начинать процесс детализации. Для этого вершину делят на ряд более мелких задач и записывают их в том порядке, в котором они должны выполняться. В результате получают первую детализацию: здесь использована только структура следования — записанные шаги должны выполняться последовательно один за другим. Каждая детализация, так же, как и сама вершина, является полным описанием алгоритма; меняется только уровень детализации. Многие программы могут быть логически разделены на три этапа: этап задания начальных значений, в котором задаются начальные значения переменных программы; этап обработки данных, в котором вводятся данные и устанавливаются значения соответствующих переменных программы; заключительный этап, в котором вычисляются и печатаются окончательные результаты. Программист завершает процесс нисходящей разработки с пошаговой детализацией, когда алгоритм на псевдокоде настолько детализирован, чтобы его псевдокод можно было бы преобразовать в программу на C++. Реализованная программа на C+ + окажется в этом случае простой и наглядной.

10.Модульные программы (основные понятия; критерии разбиения; принцип утаивания информации Д. Парнаса; разбиение на основе целевой функции,

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

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

Принцип утаивания информации Д. Парнаса

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

11.Основы доказательства правильности (соответствие семантики программы требованиям ее спецификации; доказательство общей правильности; дву

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

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

Совместимость семантики с предусловием и постусловием.

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

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

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

1)Что программа не зациклилась

2)Что программа не остановлена преждевременно

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