Алгоритмизация и управление информационными процессами

Вид материала

Содержание

Система команд исполнителя (СКИ)
Принцип формальности
Словесная формулировка
Требования, предъявляемые к правильно организованным алгоритмам
Графическое описание алгоритмов
Название блока
Принципы разработки алгоритмов
Флаг знакорезультата
2. структурный подход
Азовые управляющие структуры алгоритмов
Программное обеспечение
Ii. инструментальные средства создания по
Iii. прикладное программное обеспечение
Операционные системы
Характерные состояния исполнительной системы (процессора) при исполнении программы
Суть функции
Прерывание первого рода
Организация управления данными на дисках
D: \ каталог \ подкаталог \ имя_файла . расширение

Подобный материал:

АЛГОРИТМИЗАЦИЯ И УПРАВЛЕНИЕ
ИНФОРМАЦИОННЫМИ ПРОЦЕССАМИ

АЛГОРИТМ И ЕГО СВОЙСТВА

Понятие алгоритма

Алгоритм – Аlgorithmi (латинская форма написания имени) –аль Хорезми (великий математик IX в., сформулировал правила арифметических действий).

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

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

Система команд исполнителя (СКИ) – основа алгоритмизации процессов достижения результата; это совокупность команд, которые данный исполнитель (решатель, интерпретатор) умеет выполнять.

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

Способы описания алгоритмов

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

Свойства алгоритма

Требования, предъявляемые к правильно организованным алгоритмам

1. ДИСКРЕТНОСТЬ

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

2. ПОНЯТНОСТЬ

Ориентация на определенного исполнителя. Можно использовать команды из состава СКИ.

3. ОПРЕДЕЛЕННОСТЬ или ДЕТЕРМИНИРОВАННОСТЬ

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

4. РЕЗУЛЬТАТИВНОСТЬ

Возможность достижения результата за конечное число шагов. При этом должен получиться определенный результат. Вывод «решение не существует» – результат.

5. МАССОВОСТЬ

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

Графическое представление алгоритмов

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

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

внутри блоков помещается информация, поясняющая действия;
конфигурация блоков и размеры оговорены ГОСТом;
каждый блок снабжается номером в разрыве контура блока в левой верхней части;
высота блока (размер a) выбирается из ряда 10, 15, 20…мм;
ширина блока (размер b) выбирается как b=1,5a;
в схемах, не являющихся документацией (плакаты, курсовые работы), можно увеличить ширину блока для удобства записи информации;
ход вычислительного процесса изображается линиями связи;
линии связи обязательно имеют стрелки, если они направлены снизу вверх или справа налево – в остальных случаях стрелки необязательны.

Преимущества графического описания алгоритмов

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

Типы вершин блок-схем алгоритмов

Блок-схема – ориентированный граф, указывающий порядок исполнения команд алгоритма.
Имеет только три типа вершин.

1. Функциональная вершина – имеет один вход и один выход.
2. Предикатная вершина – имеет один вход и два выхода. Функция Р передает управление по одной из ветвей в зависимости от значения функции Р.
3. Объединяющая вершина – обеспечивает передачу управления от одного из двух входов к выходу

Распространенные блоки алгоритмов

Название блока	Обозначение (ГОСТ 19003-80)	Вычислительная функция
Процесс		Вычислительное действие или последовательность действий
Условие		Проверка условия и выбор направления хода вычислительного процесса
Модификация		Начало цикла
Предопределенный процесс		Использование ранее созданных и отдельно описанных алгоритмов (подпрограмм)
Ввод - вывод		Ввод и вывод данных
Документ		Вывод данных на печатающее устройство
Соединитель		Указание связи между прерванными линиями потока
Пуск, остановка		Начало, конец, остановка, вход и выход в отдельно описанных алгоритмах и подпрограммах
Комментарий		Пояснения, содержания программ, формулы

ПРИНЦИПЫ РАЗРАБОТКИ АЛГОРИТМОВ

1. ОПЕРАЦИОННЫЙ ПОДХОД

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

Требование эффективности к алгоритмам:

минимальные требования к вычислительным ресурсам (!) особенно к памяти;
минимальное время исполнения (алгоритмов, программ).

Требования обусловили состав системы команд исполнителя (СКИ):

операции присваивания;
простейшие арифметические операции;
операции сравнения чисел;
операторы условного и безусловного перехода;
оператор вызова подпрограмм.

Состав системы команд

Операция присваивания

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

Набор простейших арифметических операций

сложение «+», вычитание «-», умножение «*», деление «/»

Особенности этих операций:

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

Операции сравнения

Суть операции – определение знака разности значений величин ( Флаг знакорезультата).

Условные и безусловные переходы

Условные и безусловные переходы обусловлены тем, что команды алгоритма (шаги) имеют метки (адреса), при этом возможны:

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

Вызов подпрограмм

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

АССЕМБЛЕРЫ – языки команд конкретных ЭВМ (процессоров).

Достоинства таких алгоритмов:

экономичность ресурсов;
эффективность;
универсальность.

Недостатки таких алгоритмов:

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

Вывод:

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

2. СТРУКТУРНЫЙ ПОДХОД

Принцип структурного программирования
(Теорема Бема-Якопини) –
логическая структура любой программы может быть выражена комбинацией из базовых структур:

1) Следование. 2) Ветвление. 3) Цикл.

Б АЗОВЫЕ УПРАВЛЯЮЩИЕ СТРУКТУРЫ АЛГОРИТМОВ

1. КОМПОЗИЦИЯ или следование

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

2. АЛЬТЕРНАТИВА или ветвление

С

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

3. ИТЕРАЦИЯ или циклы

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

Повторение с предусловием

Повторение с постусловием

Цикл со счетчиком

Способы комбинации структур

Путем СЛЕДОВАНИЯ структур друг за другом.
Путем создания СУПЕРПОЗИЦИЙ – вложение одной структуры в другую.

Признаки структурного программирования

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

Преимущества модульной структуры:

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

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

построение иерархии модулей программ;
разбиение задач на подзадачи;
детализация до уровня подзадач, решение которых обеспечивается за 35 строк.

ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ

Классификация программного обеспечения

I. ОБЩЕСИСТЕМНОЕ ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ (ПО)

Операционные системы

базовые системы ввода / вывода (BIOS)
командные процессоры

Оболочки операционных систем

диспетчеры
менеджеры

Драйверы устройств
Утилиты
Сервисные программы общего назначения

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

Интегрированные системы (Windows).

II. ИНСТРУМЕНТАЛЬНЫЕ СРЕДСТВА СОЗДАНИЯ ПО

Ассемблеры
Трансляторы
Средства редактирования, отладки, компоновки
Средства работы с библиотеками

III. ПРИКЛАДНОЕ ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ

Программное обеспечение общего назначения
Офисные системы
Текстовые редакторы:

техническое редактирование
художественное редактирование

Издательские системы, системы презентаций
Электронные таблицы
СУБД – системы управления базами данных
Графические системы

системы растровой графики
системы векторной графики
деловая графика
инженерная графика
научная графика

Программное обеспечение профессионального уровня
Системы планирования и управления
АРМ - автоматизированные рабочие места
АСУП – автоматизированные системы управления производством
АСТПП – автоматизированные системы технологической подготовки производства;
САПР – системы автоматизированного проектирования
CAD/CAM/CAE – системы
PDM – системы коллективного ведения проекта и менеджмента данных
Системы телекоммуникаций
Системы документооборота
Системы мультимедиа
Банковские системы
Бухгалтерские системы
Системы учета складирования
Программное обеспечение специального назначения
Инструментальные средства специального назначения

системы научных расчетов
АСНИ - автоматизированные системы научных исследований
системы моделирования

Экспертные системы (оценки, анализа, принятия решений)
Гипертекстовые системы
Обучающие системы
Справочные системы
Авторские разработки

вирусы
антивирусы
тестирующие программы
компьютерные игры

ОПЕРАЦИОННЫЕ СИСТЕМЫ

Назначение операционных систем

Операционные системы (ОС) – это ядро программного обеспечения;

– наиболее машинно-зависимый вид ПО, ориентированный на конкретный вид компьютеров;

– обеспечивают интерфейс между пользователем и аппаратной частью вычислительной техники.

Функции ОС

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

Ресурсы – аппаратная часть компьютера:

центральный процессор
оперативное запоминающее устройство
периферийные устройства …

Управление устройствами:

На низком уровне:

выдача команд устройствам;
анализ всех ошибок, о которых, они сообщают.

На высоком уровне:

организация, хранение, защита данных на диске;
управление дисковым пространством;
быстрые и надежные операции поиска считывания и записи данных.

Управление программами:

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

Функционирование ОС

Управление процессами

Суть функции – управление процессами в целом и каждым в отдельности.

Характерные состояния исполнительной системы (процессора) при исполнении программы

Управление ресурсами

Ресурс – функциональный элемент вычислительной системы.

физический ресурс – реальные устройства;
виртуальный ресурс – модель физического устройства.

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

Управление ресурсами осуществляется согласно концепции ПРЕРЫВАНИЯ.

Концепция прерывания – базовая концепция выполнения программ при построении любой операционной системы.

Разновидности прерываний:

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

Схема работы прерывания:

восприятие запроса на прерывание;
запоминание состояния прерванного процесса в СТЕКЕ;
передача управления прерывающей программе;
обработка прерывания;
восстановление прерванного процесса.

Структура программной реализации ОС

Системное ПО

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

Программы-оболочки – обеспечивают более удобный и наглядный способ общения с компьютером, чем штатные средства ОС.

Утилиты – программы вспомогательного назначения.

Типовые утилиты

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

Режимы работы ОС

Режим разделения времени

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

Условие нормальной работы:

ЕСЛИ: Интервал мультиплексирования (времени) ~200 мс
и средняя длина очереди ~10 программ

ТО задержки соизмеримы со временем реакции человека.

Фоновый режим

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

Режим реального времени (RTW)

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

ОРГАНИЗАЦИЯ УПРАВЛЕНИЯ ДАННЫМИ НА ДИСКАХ

Задачи и функции файловой системы

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

FAT (File Allocation Table) – таблица размещения файлов.

Функции файловой системы

обеспечивает независимость программ от конкретной конфигурации вычислительной системы, то есть ЛОГИЧЕСКИЙ УРОВЕНЬ РАБОТЫ;
скрывает от пользователя и программиста реальное размещение информации (физический уровень работы);
обеспечивает стандартные реакции на ошибки обмена данными;
структура файловой системы и структура хранения данных на внешних носителях информации определяет удобство работы пользователя, скорость доступа к данным и т.п.;
обеспечивает стандартный интерфейс для общения с данными на дисках для прикладных программ (к файловой системе имеет доступ любая прикладная программа, для чего во всех языках программирования имеются специальные процедуры).

Файловая структура

ФАЙЛ – (обычно) именованная совокупность данных, хранимых на внешнем записывающем устройстве, имеющая определенную структуру;

– место постоянного хранения информации – программ, тестов, графических изображений и т.п.;

– реализуются файлы как участки памяти на носителях информации.

Каталоги (директории)

Учет файлов – это сведение учетной информации о расположении файлов в единое место – КАТАЛОГ.
Каталог (директория) – список элементов, описывающих характеристики конкретных файлов (имя, тип, местоположения, длина, …).

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

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

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

Операции над файлами и каталогами:

создание;
считывание;

запись;
переименование,

перенос,
удаление и др.

Идентификатор файла

ИДЕНТИФИКАТОР ФАЙЛА – обеспечивает доступ к файлу, имеет вид

<имя_файла> . <расширение>.

Имя файла – буквенно-цифровое обозначение (имеет некоторые ограничения для различных ОС).

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

Полное имя файла включает путь к его каталогу:

D: \ каталог \ подкаталог \ имя_файла . расширение

Атрибуты файла

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

В файловой системе FAT для файлов предусмотрено четыре атрибута. Каждый из этих атрибутов может быть либо установлен, либо нет:  или

«только для чтения» (read-only)

Атрибут «только для чтения» предохраняет файл от изменений. Для изменения или удаления файла с этим атрибутом требуется предварительно снять данный атрибут.

«скрытый» (hidden)

Атрибуты «скрытый» позволяет не отображать файлы в при просмотре каталогов (используются некоторыми системными файлами).

«системный» (system)

Атрибуты «системный» используются некоторыми системными файлами, обеспечивают некоторые приемы защиты служебных файлов.

«архивируемый» (archive).

Атрибут файла «архивируемый» устанавливается при создании файла и сбрасывается программами резервного копирования для обозначения того, что копия файла помещена в архив.

Атрибут «подкаталог»

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

Атрибут «метка диска»

Атрибут «метка диска» устанавливается у элемента каталога, описывающего метку диска. Описание метки диска делается в корневом каталоге диска.

Виды разрешения на доступ к файлу (каталогу):

чтение (R - read);
запись (W - write);
выполнение (X - execute).

Уровни защиты файла (назначает владелец):

защита от владельца;
защита от той же группы, что и владелец;
защита от всех остальных пользователей.

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

Blog