Лекции (Ведищев) + шпоры к экзамену / Теория к экзаменам / вопросы 1+

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 г. Тьюринг и Черч выдвинули тезис о том, что определения вычислимости могут быть сведены к определению Тьюринга. В частности любой алгоритм можно признать вычислимым, если он допускает реализацию на машине Тьюринга. Машина Тьюринга – гипотетическая. Для неё определены правила выполнения элементарных определённых операций. 12.Средства выполнения программ. Понятие операционной системы для прикладного программиста. Интерфейс прикладного программиста с операционной системой, понятие API. Система программирования (средство поддержки программирования; средство поддержки программных разработок). Понятие о библиотеках программ, их использование. Операционная система – набор программ, управляющих оперативной памятью, внешними устройствами, процессором и файлами, ведущими диалог с пользователем. Перечень функций с описанием способа их вызова, входа и выхода параметров, доступных из прикладных программ и выполняемых операционной системой называется интерфейсом прикладных программ. API – Application PI – набор функций операционной системы, позволяющих прикладным программам осуществить взаимодействие с аппаратным обеспечением ОС. К ним относят работу с файловой системой, взаимодействие с оперативной памятью, операции ввода/ вывода. Например. Вызов функции из программы на языке с вывода на экран printf приводит к вызову функции ОС, которая позволяет выводить символ на экран. Взаимодействие с функцией API реализуется через механизм программных прерываний. При вызове функции генерируется соответствующее прерывание, тип которого определяется номером и значением определенного регистра. Система поддержки программных разработок – это вычислительная система, обеспечивающая необходимую поддержку проектировщика в фазе разработки программ при создании систем программного обеспечения. Такая система в стандартном ее варианте представляет простую базу данных в качестве информационного архива и инструментальные программные средства для редактирования исходных текстов программ компилирования, компоновки, загрузки и отладки. Несмотря на эффективность и мощность конструкций языка Си, он относительно мал по объему. В нем отсутствуют встроенные операторы для выполнения ввода-вывода, динамического распределения памяти, управления процессами и т.п., однако в системное окружение языка Си входит библиотека стандартных функций, в которой реализованы подобные действия. Вынос этих функций в библиотеку позволяет отделить особенности архитектуры конкретного компьютера и соглашений операционной системы от реализации языка, сделать программу максимально независимой от деталей реализации операционной среды. В то же время программисты могут пользоваться системными библиотечными программами, чтобы более эффективно использовать особенности конкретных операционных сред. Библиотека программ - совокупность отдельных программ в программных пакетах, которые предназначены для всеобщего использования в какой-либо определенной среде.	3. Абстрактная машина фон Неймана. Понятие об элементарном исполнителе. Нейман предложил трехкомпонентную архитектуру, получившее название треугольник Фон - Неймана. В Фон-Неймановская архитектура ЭВМвключает в себя: 1)ЦП – объединяющий в себе УУ(устройство управления) и АЛУ(арифметико-логическое устройство). 2) ЗУ - запоминающее устройство - память. 3)УВВ - устройство ввода-вывода. Классификация памяти: 1.постоянная; 2.оперативная Программы и данные должны храниться в памяти. Ввод/вывод осуществляется через устройство ввода/вывода. Общее управление осуществляет ЦП. Между УВВ и ЗУ предусмотрена связь, т. к. при выполнении медленных операций ввода-вывода, ЦП может выполнять другие вычисления, не требующие ввода-вывода. А специальное устройство – контроллер прямого доступа к памяти управляет процессом передачи данных между ЗУ и УВВ. Под программой понимают набор команд, извлекаемые в порядке их следования, либо в соответствии с управляющими командами. Данные хранятся в виде переменных, которые могут быть поименованы для последующей реализации и изменения. Программы данных хранятся в памяти. Память – последовательность ячеек для хранения порций информации. Доступ к информации ячеек осуществляется в соответствии с адресом (порядковым номером) информация хранится в двоичном виде. Единица информации бит, байт – минимально адресуемая в памяти единица информации (1 байт=8 бит). Одним байтом может быть закодировано 2^8, т. е. 256 различных значений. Байты объединяются в слова, двоичные слова. Размер машинного слова – разрядность ЭВМ. Классификация памяти: постоянная и оперативная. В процессоре объединены два устройства - УУ - для считывания команд данных из памяти и общей координации команд и АЛУ - для простейших логических и арифметических операций. Регистры – быстродействующие ячейки памяти, расположенные на кристалле процессора. Регистры специального назначения и регистры общего назначения: РОН предназначены для логических и арифметических операций. РСН – в их состав входят счетчик команд; регистр состояния программы; регистр указателя стека. Счетчик команд хранит адрес следующей команды; регистр состояние программы – обязательно включает в себя флаги (1/0, да/нет, правда/ложь, true/false), характеризующие результат выполнения последней программы. Флаги используются для выполнения условных операций. Регистр стека – хранит адрес вершины стека. Стек – область памяти, доступ к которой осуществляется по принципу LIFO. Арифметико-логическое устройство процессора предназначено для выполнения операций в соответствии с кодом команды над данными, которые указываются в качестве аргумента. Команда пересылки. По ней данные, определяемые 1-м операндом пересылаются по месту хранения, которое определяется 2-м операндом. Данные пересылаются по адресу со смещением. При этом говорят о непосредственной адресации в случае, если указаны данные; прямой адресации данных, если указан адрес данных; косвенной, если указывается адрес адреса данных; индексная, если указан индекс блока адреса и смещение. Команды перехода. Командам безусловного перехода соответствует оператор goto; вместе с кодом операции указывается операнд определяющий адрес команды на которую передается управление. Фактически осуществляется команда пересылки адреса команды в реестр счетчика команд. Для задания адреса могут использоваться различные виды адресации. При команде условного перехода пересылка адреса выполняется в случае истинности условия перехода, что определяется значениями файлов регистра состояния программы. Арифметические операции. "+" (выполняется в прямом коде). "-" (реализуется как сложение уменьшаемого с вычитаемым, которое представляется в дополнительном коде). Умножение (выполняется как комбинация сложений и сдвигов). Деление - комбинация вычитаний и сдвигов с определением частного и остатка. Операции над числами с плавающей точкой. Операции над действительными числами выполняются в зависимости от форм представления (с фиксированной или с плавающей точкой). Выполняется в виде совокупности операций или над мантиссой и характеристикой числа. Логические операции. И (++ = +, +- = -, -- = -) ИЛИ (++ = +, +- = +, -- = -) НЕ ИСКЛЮЧАЮЩЕЕ ИЛИ (++ = +, +- = неоднозначность, -- = -). Другие операции: команды останова, команды работы со стеком, пустую операцию, команды вызова подпрограммы, команда обмена, команда цикла. Они могут быть реализованы как комбинация пересылок, переходов, арифметических или логических действий, но присутствуют в виде отдельных команд из-за частого использования. Понятие об элементарном исполнителе. Выполнение программы на машинном языке осуществляется следующим образом: в счетчик команд заносится адрес первой исполняемой команды. Устройство управления считывает по этому адресу код операции, дешифрует его, определяет количество операндов, место их размещения. Дешифрованная информация передается арифметико-логическому устройству. Также при этом значение регистра и счетчика команд увеличивается на размер команды, включая операнды. Если код команды соответствует команде перехода, то в регистр счётчика команд заносится адрес перехода. Процедура повторяется до тех пор, пока не возникнет исключительная ситуация: или внешнее прерывание, или пока не встретится команда остановок. ЦП является элементарным исполнителем для алгоритма исполняемой программы.	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++ и запущена на счет. Объявления не являются исполняемыми операторами. Блок-схема — это графическое представление алгоритма или фрагмента алгоритма. Блок-схема рисуется с использованием специальных символов, таких, как прямоугольники, ромбы, овалы и малые окружности; эти символы соединяются стрелками, называемыми линиями связи. Подобно псевдокоду блок-схемы часто используются при разработке и описании алгоритмов, хотя большинство программистов предпочитает псев­докод. Блок-схемы наглядно показывают, как действуют управляющие струк­туры. Нисходящее проектирование – метод пошаговой детализации Нисходящее проектирование. по алгоритму программы создается текст главного модуля, содержащего в виде комментариев основны6е этапы решения задачи. Желательно, чтобы каждая строка комментария представляла собой вызов подпрограммы, решающей подзадачу главной задачи основные этапы заменяются строчкой кода, представляющего собой вызов функции, соответствующей этапу решения задачи. Выбирается имя функции, тип возвращаемого значения и определяется список параметров. По каждой вновь созданной1 функции записывается определение. Тело функции содержит комментарии. Процедура повторяется до тех пор, пока комментарии не будут заменены кодом на языке С Нисходящее проектирование – подход к проектированию программ, при котором первоначально создается главный модуль, для которого затем проводится декомпозиция (разбиение на модули, решающие подзадачи главной задачи). Метод нисходящего проектирования предполагает последовательное разложение общей функции обработки данных на простые функциональные элементы ("сверху-вниз"). В результате строится иерархическая схема, отражающая состав и взаимоподчиненность отдельных функций. Создание программы с исполь­зованием технологии нисходящей (сверху-вниз) разработки с пошаговой детали­зацией. Эта технология является неотъемлемой частью создания хорошо структурированных программ. Она начинаем с записи псевдокода вершины. Вершина — это единственное предложение (оператор), выражающее общее назначение программы. Таким образом, вершина отображает всю про­грамму в целом. К сожалению, вершина редко отображает достаточное количество деталей, на основании которых можно написать программу на C++. Поэтому надо начинать процесс детализации. Для этого вершину делят на ряд более мелких задач и записывают их в том порядке, в котором они должны выполняться. В результате получают пер­вую детализацию: здесь использована только структура следования — записанные шаги должны выполняться последовательно один за другим. Каждая детализация, так же, как и сама вершина, является полным описанием алгоритма; меняется только уровень детализации. Многие программы могут быть логически разделены на три этапа: этап задания начальных значений, в котором задаются начальные значения переменных програм­мы; этап обработки данных, в котором вводятся данные и устанавливаются значения соответствующих переменных программы; заключительный этап, в котором вычис­ляются и печатаются окончательные результаты. Программист завершает процесс нисходящей разработки с пошаговой детализацией, когда алгоритм на псевдокоде настолько детализирован, чтобы его псевдокод можно было бы преобразовать в программу на C++. Реализованная программа на C+ + окажется в этом случае простой и наглядной.	10.Модульные программы (основные понятия; критерии разбиения; принцип утаивания информации Д. Парнаса; разбиение на основе целевой функции, на основе выделения однотипных этапов обработки; декомпозиция на основе абстрактных типов данных). Восходящее проектирование программы. Восходящее проектирование (снизу вверх) – подход к проектированию, при котором в основной задаче определяются минимальные подзадачи, решение которых возможно без использования вызовов дополнительных вновь создаваемых модулей. После того, как все подзадачи будут представлены в виде программных модулей, формируются вызывающие модули, решающие более крупные задачи. Процедура повторяется до тех пор, пока не будет получен главный модуль, решающий основную задачу. Это способ программирования при котором вся программа разбивается на группу компонентов, называемых модулями. Каждый со своими контролируемыми размерами, четким значением и хорошо определенным интерфейсом с внешней средой. Поскольку естественная альтернатива - создание монолитной программы, что крайне неудобно, вопрос заключается в том, должны ли программы разбиваться на модули, а в том, каким должен быть критерий разбиения. Эту проблему решил Парнас, который предложил, чтоб одним из критериев считался принцип утаивания информации. До этого разбиение на модули обычно осуществлялось на основе какой-нибудь целевой функции или на основе выделения однотипных этапов обработки выполняемой программы, что давало совсем незначительный выигрыш. Еще раньше основное внимание сосредотачивалось на декомпозиции, основанной на использовании абстрактных типов данных. Это разбиение на модули может удачно сочетаться с принципом утаивания информации. Принцип утаивания информации Д. Парнаса Для обоих подходов к проектированию программы (восходящее и нисходящее проектирование) важнейшим этапом является способ взаимодействия между модулями. В соответствии с принципом утаивания информации Парнаса никакие данные, используемые внутри модуля не могут быть доступны извне, кроме тех, которые передаются через интерфейс ввода/ вывода, определяемых списком параметров. 11.Основы доказательства правильности (соответствие семантики программы требованиям ее спецификации; доказательство общей правильности; двухэтапное доказательство правильности; частичная правильность: совместимость семантики с предусловием и постусловием; инварианты циклов; концепция вполне упорядоченного множества – основа доказательства отсутствия зацикливаний). Верификация и тестирование программы. Доказательство правильности - это подтверждение того, что семантика программы соответствует предъявляемым требованиям, изложенным в спецификации этой программы. Существуют два предварительных условия для построения такого доказательства: необходимо иметь формальное описание программы и формальное определение используемого языка программирования. Такое определение может принимать фирму системы аксиом, охватывающих семантические правила для любого простого оператора в языке, и набора правил вывода, показывающих, как семантики составных операторов к числу которых относится и целостная программа. Интерпретированные пооперационно утверждения характеризуют состояние программы. Доказательство строится на следующей схеме: если выполнение программы начинается в состоянии, когда входное утверждение истинно, то работа программы в итоге должна завершаться состоянием, при котором выходное утверждение тоже истинно. Этот тип доказательства известен как доказательство общей правильности. Традиционно, однако, такое доказательство часто выполняется в два этапа. Вначале доказывается правильность частей программы (частичная правильность); считается, что, если программа завершается нормально, то это происходит в состоянии, для которого выходное утверждение истинно. На втором этапе доказывается правильность завершения программы; в результате этого доказательства показывается, что программа завершила работу нормально, а не преждевременно. Совместимость семантики с предусловием и постусловием. Описание программы может очень удобно представляться в форме двух утверждений: входного и выходного. Для того чтобы проверить правильность программы, необходимо сформулировать предусловие – выражение, определяющее значение до начала работы группы операторов и постусловие – выражение, определяющее значение после окончания работы группы операторов. Если выражение на входе и на выходе соответствует ожидаемому, то группу операторов можно считать семантически правильной. Для доказательства правильности циклических участков в ней включают так называемые инварианты циклов. Инвариант- это утверждение, которое остается истинным при некотором преобразовании или отображении. При доказательстве правильности инвариантом является некоторое утверждение о свойствах фрагментов программы, который остается истинным не смотря выполненную часть этого аргумента. Инвариант цикла – выражение, значение которого не изменяется при каждом прохождении цикла. Для доказательства факта завершения программы необходимо доказать: 1)Что программа не зациклилась 2)Что программа не остановлена преждевременно Подтверждение того, что программа в конце концов выйдет из цикла может быть основано на концепции вполне упорядоченного множества. Доказательство правильности программы не дает полного решения надежности программы. Так же практически всегда невозможно машинное доказательство правильности. Наибольшие трудности возникают при отсутствии понимания замысла разработчиков. Машинную проверку правильности программы называют верификацией программы. Тест по возможности составляют так, чтоб были рассмотрены все комбинации значений из перечисленного ряда.	13. Программа на языке высокого уровня. Язык программирования С. Программа на языке высокого уровня Программа – алгоритм, записанный на языке программирования + структура данных, с которыми работает программа. Этапы существования ПО (не жизненный цикл программы): подвергается трансляции – процедура перевода с языка высокого уровня на машинный язык. В ходе трансляции может использоваться переход на промежуточный язык – кросстрансляции, в качестве промежуточного языка может использоваться язык ассемблера. Ассемблер – программа, осуществляющая перевод с языка ассемблера на машинный язык. Машинный язык – язык, использующий машинные команды, записанные в формате воспринимаемом конкретным вычислительным устройством. Транслятор – программа, выполняющая процедуру трансляции. Существует 2 вида: компилятор и интерпретатор. Компилятор – осуществляет перевод текста программы на машинный язык целиком. Результат работы – объектный файл, содержащий программу на машинном языке и информацию о данных, используемых программой. Объектный файл обрабатывается компоновщиком (линкером) или редактором связи. Компоновщик обрабатывает объектные файлы, разрешает внешние ссылки (делает доступным вызовы объектов функций или данных из других объектных файлов или стандартных библиотек), осуществляет необходимую подготовительную работу для последующей загрузки программы на исполнение. Загрузчик программ, осуществляющих размещение исполняемого кода и данных в памяти ЭВМ и передающий управление первой исполняемой команде программы. В случае персональных ЭВМ функции загрузчика распределены между ОС и кодом, включаемым в исполняемый файл. Исполнение программы начинается с загрузки в регистр счетчика исполняемых команд ЦП, адреса первой исполняемой команды программы. Устройство управления считывает по этому адресу код команды, в соответствии с ним считывает значения операндов, передает код и операнды АЛУ, которое выполняет необходимые операции. По завершению выполнения команды значение регистра счетчика команд увеличивается на значение длины команды, которая известна по коду операции. Процедура повторяется до тех пор, пока не будет встречена команда stop. Исполняемая программа обычно завершается возвратом управления программе, вызвавшей данную программу (ОС). Интерпретатор – покомандно или построчно считывает программу на исходном языке, переводит на машинный язык и отправляет на выполнение. Входом является программа на языке программирования. Результат – построчно выполняемая команда. Компилятор языка С воспринимает исходный файл, содержащий программу на языке С, как последовательность текстовых строк. Каждая строка завершена символом новой строки. Этот символ вставляется текстовым редактором при нажатии клавиши ENTER (ВВОД). Компилятор языка С последовательно считывает строки программы и разбивает каждую из считанных строк на группы символов, называемые лексемами. Лексема—это единица текста программы, которая имеет самостоятельный смысл для компилятора языка С и которая не содержит в себе других лексем. Никакие лексемы, кроме символьных строк, не могут продолжаться на последующих строках текста программы. Знаки операций, константы, идентификаторы и ключевые слова, описанные в этом разделе, являются примерами лексем. Разделители, например квадратные скобки [], фигурные скобки {}, круглые скобки (), угловые скобки < > и запятые, также являются лексемами. Внутри идентификаторов, ключевых слов, а также знаков операций, состоящих из нескольких символов, пробельные символы недопустимы. Когда компилятор языка Си выделяет отдельную лексему, он пытается включить в нее последовательно столько символов, сколько возможно, прежде чем перейти к выделению следующей лексемы. Рассмотрим, например, следующее выражение: i+++j В этом примере компилятор языка Си вначале сформирует из первых двух знаков "плюс" операцию инкремента (++), а из оставшегося знака плюс — операцию сложения. Выражение проинтерпретируется как (i++)+(j), а не как (i)+(++j).В подобных случаях рекомендуется для ясности разделять лексемы пробельными символами или круглыми скобками.