Ответы на вопросы к экзамену, страница 2

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

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

• последовательную декомпозицию задачи, выделение автономных этапов вычислительного процесса и разбивку каждого этапа на отдельные шаги;

• формальную запись содержания каждого этапа и/или шага;

• определение общего порядка выполнения этапов и/или шагов;

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

Алгоритмы обладают целым рядом свойств:

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

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

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

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

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

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

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

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

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

Объем текста алгоритма (программы) определяется количеством операторов, использованных для записи алгоритма.

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

13.Способы описания алгоритмов. Правила выполнения блок схем.

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

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

Словесный способ записи алгоритмов представляет собой последователь­ное описание основных этапов обработки данных и задается в произвольном из­ложении на естественном языке.

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

Такое графическое представление называется схемой алгоритма или блок-схемой. В блок-схеме каждому типу действий (вводу исходных дан­ных, вычислению значений выражений, проверке условий, управлению повто­рением действий, окончанию обработки и т. п.) соответствует геометрическая фигура, представленная в виде блочного символа. Блочные символы соединя­ются линиями переходов, определяющими очередность выполнения действий. Для начертания этих схем используется набор символов, определяемых ГОСТ 19.701-90 (ИСО 5807 - 85) "Единая система программной документации". В табл. 1 приведены наиболее часто употребляемые символы.

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

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

Символ "Решение" используется для обозначения переходов управления по условию. В каждом блоке решения должны быть указаны вопрос, реше­ние, условие или сравнение, которые он определяет.

Стрелки, выходящие из блока решения, должны быть помечены соответст­вующими ответами (например, ДА, НЕТ), так чтобы были учтены все возмож­ные ответы.

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

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

Символ "Документ" предназначен для ввода - вывода данных, носителем которых служит бумага.

Таблица 1

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

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

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

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

Правила выполнения блок-схем

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

Расстояние между параллельными линиями должно быть не менее 3 мм, между остальными символами схемы - не менее 5 мм.

Записи внутри символа или рядом с ним должны выполняться ма­шинописью с одним интервалом или чертежным шрифтом.

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

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

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

Размер а должен выбираться из ряда 10, 15, 20 мм. Допускается уве­личивать размер а на число, кратное 5. Размер b равен 1,5а. При ручном выполнении схем алгоритмов и программ для символов, представленных в табл. 1, допускается устанавливать b равным 2 а.

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

14.Информационные технологии решения задач. Структуры алгоритмов.

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

Общая формулировка задачи. Необходимо сформулировать задачу в
содержательных терминах и определить, что является "входными" данными
задачи и что мы собираемся получить в результате решения.

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

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

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

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

Тестирование программы. На этом этапе, чтобы удостовериться в
правильности работы алгоритма, решаются задачи с такими исходными дан­ными, для которых известно достоверное решение, либо используются ка­кие-то косвенные свидетельства.

Решение поставленной задачи и представление результатов.
Здесь наиболее существенным является удобный и наглядный вывод результатов. Во многих случаях целесообразно использовать графические программ­ные средства для визуализации полученных данных.

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

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

Структура алгоритма является линейной, если она образована последова­тельностью простых операторов (команд).

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

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

15.Сервисные и инструментальные системы.

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

Делятся на однопользовательские и многопользовательские, однозадачные и многозадачные, с текстовым или графическим интерфейсом.