Основные определения
ОСНОВЫ АЛГОРИТМИЗАЦИИ
Требования к операционным системам
Операционная система, как правило, должна реализовывать мультипрограммную обработку, виртуальную память, свопинг, поддерживать многооконный интерфейс, а также выполнять многие другие, необходимые функции. Кроме этих функциональных требований к операционным системам предъявляются не менее важные рыночные требования. К этим требованиям относятся:
- расширяемость: программное обеспечение системы должно быть написано таким образом, чтобы можно было легко внести дополнения и изменения, если это потребуется, и не нарушить целостность системы;
- переносимость: программное обеспечение системы должно легко переноситься с процессора одного типа на процессор другого типа;
- надежность и отказоустойчивость: программное обеспечение системы должно быть защищено как от внутренних, так и от внешних ошибок, сбоев и отказов, его действия должны быть всегда предсказуемыми, а приложения не должны быть в состоянии наносить вред;
- совместимость: операционная система должна иметь средства для выполнения прикладных программ, написанных для других операционных систем, а пользовательский интерфейс должен быть совместим с существующими системами и стандартами;
- безопасность: программное обеспечение операционной системы должно обладать средствами защиты ресурсов одних пользователей от других;
- производительность: система должна обладать настолько хорошим быстродействием и временем реакции, насколько это позволяет аппаратная платформа.
Опр. 1. Константа - величина, не изменяющая своего значения в процессе решения задачи, в процессе выполнения программы.
Опр. 2. Тип - свойство, характеристика объекта. Под типом понимается множество значений, которые могут принимать константы и переменные.
Константы могут быть нескольких типов: числовые (целые, вещественные), текстовые (символьные, строковые), логические.
Опр. 3. Переменная - величина, изменяющая свое значение в процессе решения задачи, в процессе выполнения программы.
Опр. 4. Идентификатор - лексическая единица, используемая в качестве имени для элементов языка.
Опр. 5. Идентификатор – последовательность латинских букв и цифр, начинающаяся с буквы, и используемая для задания имен константам, переменным и другим элементам языка.
Примеры идентификаторов: x, a1, qp, program. В идентификаторе разрешается использовать также символ подчеркивания ('_'). Например, Hello_Day, x_01.
Примеры не идентификаторов: x.2, 2am, c(j)7.
Опр. 6. Язык - совокупность трех основных компонент: алфавита, синтаксиса, семантики.
Опр. 7. Алфавит - набор разрешенных символов языка.
Опр. 8. Синтаксис- правила написания основных допустимых конструкций языка (слово, предложение и т.д.).
Опр. 9. Семантика - логический смысл конструкций языка (смысловая нагрузка конструкций).
Опр. 10. Выражение - это совокупность операндов и операций соответствующего типа.
Опр. 16. Алгоритм- последовательность команд (инструкций) данному исполнителю для решения поставленной задачи.
Свойства алгоритма:
Дискретность (пошаговый характер определяемого им процесса) - поочередное выполнение команд алгоритма; процесс решения задачи разбивается на отдельные элементарные акты, возможность выполнения которых человеком или машиной не вызывает сомнения.
Точность - на каждом шагу исполнения алгоритма известно какое действие должно быть выполнено;
Понятность - (данному исполнителю) - способность выполнить каждую команду алгоритма; при этом исполнитель алгоритма, выполняя его, действует “механически”. Очевидно, что формулировка алгоритма должна быть настолько точна и однозначна, чтобы могла полностью определить все действия исполнителя.
И если при этом каждый раз сравнивать результаты, полученные после соответствующих шагов алгоритмического процесса, то окажется, что при одних и тех же исходных данных эти результаты всегда будут одинаковыми. Таким образом, можно говорить об определенности и однозначности алгоритмов.
Результативность - исполнение алгоритма завершается в конечное число шагов, а его завершение всегда означает решение задачи или указание на то, что задача не имеет решения;
Массовость - свойство алгоритма давать решение задачи для всех возможных формулировок ее условия.
Смысл данного понятия заключается в том, что существует некоторое множество объектов, которые могут служить исходными данными для рассматриваемого алгоритма. Например, для алгоритмов выполнения арифметических операций - сложения, вычитания, умножения и деления - такими данными являются все действительные числа.
Теперь можно более точно определить алгоритмкак систему правил, сформулированную на языке, понятном исполнителю, и определяющую цепочку действий, в результате выполнения которых мы приходим от исходных данных к искомому результату.
Такая цепочка действий называется алгоритмическим процессом, а каждое действие - его шагом. Число шагов для достижения результата обязательно должно быть конечным. Кроме того, алгоритм должен обладать свойствами массовости, определенности и однозначности.
Действия алгоритма можно разбить на три класса:
1) простая последовательность действий,
2) условная конструкция (ветвления),
3) циклическая конструкция (повтор действий).
Опр. 17. Программа - алгоритм решения задачи, переведенный на какой-либо язык программирования (Си, Паскаль, Фортран, Бейсик и т.д.).
Опр. 18. Правильная программа - это такая программа, для которой доказано, что она удовлетворяет своим спецификациям. Надежная программа - программа, которая выдает приемлемый результат даже в том случае, когда входные данные либо условия использования не удовлетворяют принятым допущениям.