Такой алгоритм выбора процесса осуществляет невытесняющее планирование . Процесс, получивший в свое распоряжение процессор, занимает его до истечения текущего CPU burst . После этого для выполнения выбирается новый процесс из начала очереди.
Преимуществом алгоритма FCFS является легкость его реализации, но в то же время он имеет и много недостатков. Рассмотрим следующий пример. Пусть в состоянии готовность находятся три процесса p 0 , p 1 и p 2 , для которых известны времена их очередных CPU burst . Эти времена приведены в таблице 3.1. в некоторых условных единицах. Для простоты будем полагать, что вся деятельность процессов ограничивается использованием только одного промежутка CPU burst , что процессы не совершают операций ввода-вывода и что время переключения контекста так мало, что им можно пренебречь.
Если процессы расположены в очереди процессов, готовых к исполнению, в порядке p 0 , p 1 , p 2 , то картина их выполнения выглядит так, как показано на рисунке 3.2 . Первым для выполнения выбирается процесс p 0 , который получает процессор на все время своего CPU burst , т. е. на 13 единиц времени. После его окончания в состояние исполнение переводится процесс p 1 , он занимает процессор на 4 единицы времени. И, наконец, возможность работать получает процесс p 2 . Время ожидания для процесса p 0 составляет 0 единиц времени, для процесса p 1 – 13 единиц, для процесса p 2 – 13 + 4 = 17 единиц. Таким образом, среднее время ожидания в этом случае – (0 + 13 + 17)/3 = 10 единиц времени. Полное время выполнения для процесса p 0 составляет 13 единиц времени, для процесса p 1 – 13 + 4 = 17 единиц, для процесса p 2 – 13 + 4 + 1 = 18 единиц. Среднее полное время выполнения оказывается равным (13 + 17 + 18)/3 = 16 единицам времени.
Рис.
3.2.
Если те же самые процессы расположены в порядке p 2 , p 1 , p 0 , то картина их выполнения будет соответствовать рисунку 3.3 . Время ожидания для процесса p 0 равняется 5 единицам времени, для процесса p 1 – 1 единице, для процесса p 2 – 0 единиц. Среднее время ожидания составит (5 + 1 + 0)/3 = 2 единицы времени. Это в 5 (!) раз меньше, чем в предыдущем случае. Полное время выполнения для процесса p 0 получается равным 18 единицам времени, для процесса p 1 – 5 единицам, для процесса p 2 – 1 единице. Среднее полное время выполнения составляет (18 + 5 + 1)/3 = 8 единиц времени, что почти в 2 раза меньше, чем при первой расстановке процессов.
Рис. 3.3.
Как мы видим, среднее время ожидания и среднее полное время выполнения для этого алгоритма существенно зависят от порядка расположения процессов в очереди. Если у нас есть процесс с длительным CPU burst , то короткие процессы, перешедшие в состояние готовность после длительного процесса, будут очень долго ждать начала выполнения. Поэтому алгоритм FCFS практически неприменим для систем разделения времени – слишком большим получается среднее время отклика в интерактивных процессах .
Round Robin (RR)
Модификацией алгоритма FCFS является алгоритм, получивший название Round Robin ( Round Robin – это вид детской карусели в США) или сокращенно RR . По сути дела, это тот же самый алгоритм, только реализованный в режиме вытесняющего планирования . Можно представить себе все множество готовых процессов организованным циклически – процессы сидят на карусели. Карусель вращается так, что каждый процесс находится около процессора небольшой фиксированный квант времени , обычно 10 – 100 миллисекунд (см. рис. 3.4.). Пока процесс находится рядом с процессором, он получает процессор в свое распоряжение и может исполняться.
Рис. 3.4.
Реализуется такой алгоритм так же, как и предыдущий, с помощью организации процессов, находящихся в состоянии готовность, в очередь FIFO. Планировщик выбирает для очередного исполнения процесс, расположенный в начале очереди, и устанавливает таймер для генерации прерывания по истечении определенного кванта времени . При выполнении процесса возможны два варианта.
- Время непрерывного использования процессора, необходимое процессу (остаток текущего CPU burst ), меньше или равно продолжительности кванта времени . Тогда процесс по своей воле освобождает процессор до истечения кванта времени , на исполнение поступает новый процесс из начала очереди, и таймер начинает отсчет кванта заново.
- Продолжительность остатка текущего CPU burst процесса больше, чем квант времени . Тогда по истечении этого кванта процесс прерывается таймером и помещается в конец очереди процессов, готовых к исполнению, а процессор выделяется для использования процессу, находящемуся в ее начале.
Рассмотрим предыдущий пример с порядком процессов p 0 , p 1 , p 2 и величиной кванта времени равной 4 . Выполнение этих процессов иллюстрируется таблицей 3.2 . Обозначение "И" используется в ней для процесса, находящегося в состоянии исполнение, обозначение "Г" – для процессов в состоянии готовность, пустые ячейки соответствуют завершившимся процессам. Состояния процессов показаны на протяжении соответствующей единицы времени, т. е. колонка с номером 1 соответствует промежутку времени от 0 до 1 .
| Время | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| p 0 | И | И | И | И | Г | Г | Г | Г | Г | И | И | И | И | И | И | И | И | И |
| p 1 | Г | Г | Г | Г | И | И | И | И | ||||||||||
| p 2 | Г | Г | Г | Г | Г | Г | Г | Г | И |
Первым для исполнения выбирается процесс p 0 . Продолжительность его CPU burst больше, чем величина кванта времени , и поэтому процесс исполняется до истечения кванта , т. е. в течение 4 единиц времени. После этого он помещается в конец очереди готовых к исполнению процессов, которая принимает вид p 1 , p 2 , p 0 . Следующим начинает выполняться процесс p 1 . Время его исполнения совпадает с величиной выделенного кванта , поэтому процесс работает до своего завершения. Теперь очередь процессов в состоянии готовность состоит из двух процессов, p 2 и p 0 . Процессор выделяется процессу p 2 . Он завершается до истечения отпущенного ему процессорного времени, и очередные кванты отмеряются процессу p 0 – единственному не закончившему к этому моменту свою работу. Время ожидания для процесса p 0 (количество символов "Г" в соответствующей строке) составляет 5 единиц времени, для процесса p 1 – 4 единицы времени, для процесса p 2 – 8 единиц времени. Таким образом, среднее время ожидания для этого алгоритма получается равным (5 + 4 + 8)/3 = 5,6(6) единицы времени. Полное время выполнения для процесса p 0 (количество непустых столбцов в соответствующей строке) составляет 18 единиц времени, для процесса p 1 – 8 единиц, для процесса p 2 – 9 единиц. Среднее полное время выполнения оказывается равным (18 + 8 + 9)/3 = 11,6(6) единицы времени.
Легко увидеть, что среднее время ожидания и среднее полное время выполнения для обратного порядка процессов не отличаются от соответствующих времен для алгоритма FCFS и составляют 2 и 8 единиц времени соответственно.
Алгоритм описания процессов
Рисунок 11 – Алгоритм описания процессов
Литература
1. Обеспечение качества обучения государственных и муниципальных служащих Российской Федерации. Выпуск 11. Инструктивно-методические материалы. Часть 1. Практические рекомендации по выбору типовой модели системы управления качеством образования. – М.: РАГС, 2006. – с.:38-44.
2. ГОСТ Р ИСО 9000-2001 Системы менеджмента качества. Основные положения и словарь.
3. Репин В.В., Елиферов В.Г. Процессный подход к управлению. Моделирование бизнес-процессов. – 3-е изд., испр. – М.: РИА «Стандарты и качество», 2005г. – с.: 305-314, ил. – (Серия «Практический менеджмент»).
4. http://slovar.plib.ru/ Толковый словарь Ожегова.
Приложение 1
Пример заполнения реестра типовых процессов и видов деятельности ОУ
| № п/п | Наименование вида деятельности или процесса | Иден. № | |
| Основные процессы | |||
| 1.1 | Маркетинговые исследования рынка научных, образовательных услуг и рынка труда | ||
| 1.2 | Проектирование и разработка образовательных программ | ||
| 1.3 | Довузовская подготовка и прием студентов | ||
| 1.4 | Реализация основных образовательных программ | ||
| 1.5 | Воспитательная и внеучебная работа с обучаемыми | ||
| 1.6 | Проектирование и реализация программ дополнительного образования | ||
| 1.7 | Подготовка кадров высшей квалификации (аспирантура, докторантура) | ||
| 1.8 | Научно-исследовательская и инновационная деятельность | ||
| Вспомогательные процессы | |||
| 2.1 | Бухгалтерско-финансовое обеспечение научно-образовательного процесса | ||
| 2.2 | Кадровое обеспечение | ||
| 2.3 | Закупки и взаимодействие с поставщиками материальных ресурсов | ||
| 2.4 | Управление образовательной средой | ||
| 2.5 | Издательская деятельность | ||
| 2.6 | Библиотечное и информационное обслуживание | ||
| 2.7 | Управление инфраструктурой и производственной средой | ||
| 2.8 | Обеспечение безопасности жизнедеятельности | ||
| 2.9 | Социальная поддержка студентов и сотрудников ОУ |
Приложение 2
Пример заполнения таблицы 2 «Спецификация процесса»
| 1. Наименование процесс | Научно-исследовательская деятельность (НИД) | |||
| 2. Цель процесса | Создание условий для реализации научно-исследовательской деятельности студентов и преподавателей | |||
| 3. Владелец процесса | Проректор по научно-исследовательской работе | |||
| 4. Входы процесса | Поставщик входа – процесс(ы), предоставляющий(ие) вход | |||
| 4.1 Аспиранты, докторанты. | Процесс управления докторантуры и аспирантуры | |||
| 4.2 Соискатели | Процесс управления докторантуры и аспирантуры; Внешний поставщик | |||
| 4.3 Студенты | Учебный процесс | |||
| 4.4 Данные маркетинговых исследований (требования потребителей) | Маркетинг и планирование набора | |||
| 5. Выходы процесса | Потребитель выхода – процесс(ы), использующий(ие) выход | |||
| 5.1 Статьи, изобретения | Учебный процесс; Отдел интеллектуальной собственности; Процесс управления докторантуры и аспирантуры; Библиотечное и информационное обслуживание; Внешний потребитель* и др. | |||
| 5.2 Дипломы, гранты | Учебный процесс, Процесс управления финансовым обеспечением; Внешний потребитель и др. | |||
| 5.3 Защитившие кандидатские, докторские диссертации | ||||
| 5.4 Научные школы | Учебный процесс; Научно-исследовательская деятельность; Внешний потребитель и др. | |||
| 6. Управляющая документация | 6.1 Программа развития подразделения | |||
| 6.2 Внутренние нормативные документы | ||||
| 6.3 Инструкция по организации научной и научно- технической деятельности, осуществляемой за счет собственных средств ТГУ с приложениями и др. | ||||
| 7. Механизмы процесса | 7.1 Персонал | |||
| 7.2 Финансы | ||||
| 7.3 Орг. техника | ||||
| 7.4 Библиотека и др. | ||||
| 8. Показатели процесса, ед. изм. | Норматив | Частота измерения | Метод расчета показателя | |
| 8.1 Процент ППС с учеными степенями и (или) учеными званиями, % | Не менее 60 | ежегодно | (Количество ППС с уч.степенями и званиями / Общ. количество ППС)*100 | |
| 8.2 Процент докторов наук и профессоров, % | Не менее 10 | ежегодно | (Кол-во докторов наук и профессоров / Общее количество ППС)*100 | |
| 8.3 Объем НИР на единицу ППС, тыс. руб. | За 5 лет – не менее 18 | ежегодно | … и др. | |
Всеобщий менеджмент качества (Total Quality Management – TQM) - интегрированный метод менеджмента, целиком ориентирующий деятельность организации на полную удовлетворенность потребителей (внешних и внутренних), сотрудников и общества в целом, охватывающий все процессы организации, вовлекающий в деятельность по непрерывному улучшению качества всех ее сотрудников и направленный на достижение долговременного успеха и стабильности функционирования организации.
Потребитель (согласно ГОСТ Р ИСО 9000-2005) – организация или лицо, получающие продукцию. Примеры: клиент, заказчик, конечный пользователь, розничный торговец, покупатель, студент и др.
Продукция (согласно ГОСТ Р ИСО 9000-2005) – результат процесса, т.е. результат совокупности взаимосвязанных или взаимодействующих видов деятельности, преобразующих входы в выходы.
Результативность
Эффективность (согласно ГОСТ Р ИСО 9000-2005) - степень реализации запланированной деятельности и достижения запланированных результатов.
Внутренний потребитель – потребитель, находящийся в организации и, в ходе своей деятельности, использующий результаты (выходы) предыдущего процесса.
Внешний потребитель – потребитель, находящийся за пределами организации и использующий результат (выход) процесса.
1. Заявка заказчика в правительство Москвы или префектуру (выпуск основного распорядительного документа)
2. Исходно-разрешительная документация и предпроектные проработки (утверждение задания на проектирование)
Москомархитектура, Мосгосэкспертиза, Москомзем и др.
3. Проектирование (проектные организации)
4. Согласование и экспертиза (Москомархитектура, Мосгосэкспертиза, Москомприрода, Госсанэпиднадзор, УГПН)
5. Утверждение (инвестор, заказчик)
6. Разрешение строительства (МВК (ИГАСН))
7. Договор аренды земельного участка или свидетельство собственности (Москомзем)
8. Рабочее проектирование (проектные организации)
9. Строительство (подрядные организации)
10. Ввод объекта в эксплуатацию.
Первым этапом проектно-строительно-монтажного процесса является получение Заказчиком основного распорядительного документа (ОРД). ОРД - это распоряжение первого заместителя премьера правительства г. Москвы, либо распоряжение префекта административного округа. ОРД может быть получен на основе заявки Заказчика и дает ему право подготовки полного пакета исходно-разрешительной документации (ИРД) для начала проектирования.
Состав ИРД зависит от категории (значимости) объекта и стадии проектирования.
Объекты реконструкции и многие объекты нового строительства могут быть отнесены по 2-й или 3-й категории сложности, для которых предусматривается проектирование в одну стадию - разработка рабочего проекта с утверждаемой частью. Однако в зависимости от ситуации может понадобиться разработка эскизного проекта или предпроектных предложений.
Пакет ИРД включает документы:
ОРД о предоставлении права проектирования и строительства; задание на разработку проектной документации; ситуационный план (М 1:2000); геоподоснова (М 1:500); градостроительное заключение (задание); технологическое задание;
технические условия (ТУ) присоединения электросетей; ТУ присоединения тепловых сетей; ТУ присоединения водопроводных сетей; ТУ присоединения канализационных сетей; ТУ присоединения стока условно чистой воды; ТУ присоединения телефонной сети; инженерно-геологическое заключение о грунтах;
инженерное заключение о несущей способности фундаментов и конструкций.
На основе ИРД, предоставленной Заказчиком, Генпроектировщик разрабатывает пакет проектной документации, основываясь на требованиях: строительные нормы и правила (СНиП 10-01-94, 21-01-97, 2.04.01-85 и др.); нормы пожарной безопасности (НПБ 104-95); санитарные правила и нормы (СанПиН 2.3.5.021-94); московские городские строительные нормы (МГСН 4.13-97 и др.).
Архитектурно-строительная документация согласуется в инстанциях:
Госпожнадзор;
Мосэкспертиза;
АПУ административного округа или Москомархитектуры;
жилищная инспекция;
отдел подземных сооружений;
межведомственная комиссия или ИГАСН;
Москомприрода;
Мослесопарк (в случае вырубки зеленых насаждений);
согласование с Москомимуществом (в случае аренды).
Для согласования, экспертизы и утверждения дополнительно к ИРД предоставляются документы: архитектурно-строительная документация;
планы БТИ (не более чем 3 месячной давности) с экспликациями; правоустанавливающие документы:
Документы землепользования, оформленные в Москомземе; -свидетельство о собственности или договора аренды на все помещения, включая подвал;
Согласование отдела потребительского рынка соответствующей префектуры;
Согласование балансодержателя помещения.
Технические разделы проекта должны согласовываться с заинтересованными органами тепло, водо- и электроснабжения. Согласованный пакет документов направляется для выдачи разрешения на проведение строительных и монтажных работ установленным порядком.
Приведённый порядок подготовки и согласования документов может испугать неискушённого сотрудника. Однако при должном упорстве и целеустремлённости этот путь может быть успешно пройден. Поэтому рекомендуется правильно и своевременно оформлять необходимые документы в соответствии с существующим порядком, государственными стандартами и СНиП. Отступление от правил неизбежно повлечёт финансовые и моральные потери.
Литература
Основная литература
1. Монтаж электрооборудования и средств автоматизации/А.П. Коломиец, Н.П. Кондратьева, И.Р. Владыкин и др. М.: "КолосС", 2007. 352 с. (базовый).
1. Водянников В.Т. Организационно-экономические основы сельской электроэнергетики: Учебное пособие для вузов по агроинженерным специальностям. Издание второе, переработанное и дополненное. М.: ИКФ "ЭКМОС", 2003. 352 с.
2. Электротехнические чертежи и схемы: Производственно-практическое пособие: Сб. документов/К.К. Александров, Е.Г. Кузьмина. 2-е изд. доп. М.: Изд-во МЭИ, 2004. 584с.
Митин Г.П. Условные обозначения в отечественных и зарубежных электрических схемах. М.: Изумруд, 2003. 224 с.
4. Карлащук В.И. Электронная лаборатория на IBM PC. Лабораторный практикум на базе Electronics Workbench и MATLAB. 5-е изд. М.: СОЛОН-Пресс, 2004. 800 с.
5. Инструкция о порядке допуска в эксплуатацию новых и реконструированных энергоустановок. М.: Изд-во НЦ ЭНАС, 2003. 24 с.
6. Межотраслевые правила по охране труда (правила безопасности) при эксплуатации электроустановок. 7-е изд. Новосибирск: Сиб. унив. изд-во, 2007. 176 с.
7. Правила безопасности при работе с инструментом и приспособлениями. М.: Изд-во ЭНАС, 2004. 176 с.
8. Межотраслевые типовые инструкции по охране труда при эксплуатации электроустановок, проведении электрических измерений и испытаний. ТИ Р М-(062-074)-2002. М.: Изд-во НЦЭНАС, 2003. 184 с.
10. Правила устройства электроустановок. Все действующие разделы ПУЭ-6 и ПУЭ-7. 5-й выпуск (с изм. и доп., по состоянию на 1 июля 2006 г.). Новосибирск: Сиб. унив. изд-во, 2006. 854 с.
11. Квалификационный справочник должностей руководителей, специалистов и других служащих. Новосибирск: Сиб. унив. изд-во, 2007. 319 с.
12. Справочник инженера-электрика сельскохозяйственного производства: Учеб. пособие. М.: Информагротех, 1999. 536 с.
13. Электротехнический справочник: В 4-т. / Под ред. В.Г. Герасимова и др. 9-е изд., стер. М.: Изд-во МЭИ: т. 1: Общие вопросы. Электротехнические материалы, 2003. 440 с.; т. 2: Электротехнические изделия и устройства, 2003. 518 с.; т. 3: Производство, передача и распределение электрической энергии, 2004. 964 с.; т. 4: Использование электрической энергии, 2004. 696 с.
14. Создание и использование компьютерных информационных систем в сельском хозяйстве: Метод. рекомендации / Под ред. В.В. Альта; РАСХН. Сиб. отд-ние. СибФТИ. Новосибирск, 2005. 126 с.
15. Справочник по проектированию электрических сетей. Под ред. Д.Л. Файбисовича. М.: Изд-во НЦ ЭНАС, 2005. 320 с.
16. Технология конструкционных электротехнических материалов: учеб. пособие: в 2-кн./С.В. Горелов и др.; под общ. ред. В.П. Горелова, М.Н. Иванова. 2-е изд. дополн. Новосибирск: Новосиб. гос. акад. вод. трансп., 2005: Кн. 1. 354 с.; Кн. 2. 239 с.
17. Правила проектирования и монтажа электроустановок. М.: Изд-во Омега-Л, 2006. 104 с.
18. Нестеренко В.М. Технология электромонтажных работ: Учеб. пособие для нач. проф. образования/В.М. Нестеренко, А.М. Мысьянов. 2-е изд., стер. М.: Изд. центр "Академия", 2005. 592 с.
Монтаж электрооборудования и средств автоматизации Задания и методические указания по выполнению контрольных работ
Составители: Ляпин Виктор Григорьевич
Савченко Олег Федорович
Фотьев Андрей Викторович
Самохвалов Максим Владимирович
Редактор В. В. Попова
Лицензия №020426 от 7 мая 1997г. Подписано к печати 30 января 2001 г. Объем 0,7 уч.-изд. л. Формат 84x108 1/32. Тираж 100 экз. Цена договорная.
Слово «алгоритм» происходит от имени великого среднеазиатского ученого 8–9 вв. Аль-Хорезми (Хорезм – историческая область на территории современного Узбекистана). Из математических работ Аль-Хорезми до нас дошли только две – алгебраическая (от названия этой книги родилось слово алгебра) и арифметическая. Вторая книга долгое время считалась потерянной, но в 1857 в библиотеке Кембриджского университета был найден ее перевод на латинский язык. В ней описаны четыре правила арифметических действий, практически те же, что используются и сейчас. Первые строки этой книги были переведены так: «Сказал Алгоритми. Воздадим должную хвалу Богу, нашему вождю и защитнику». Так имя Аль-Хорезми перешло в Алгоритми, откуда и появилось слово алгоритм. Термин алгоритм употреблялся для обозначения четырех арифметических операций, именно в таком значении он и вошел в некоторые европейские языки. Например, в авторитетном словаре английского языка Webster"s New World Dictionary , изданном в 1957, слово алгоритм снабжено пометкой «устаревшее» и объясняется как выполнение арифметических действий с помощью арабских цифр.
Слово «алгоритм» вновь стало употребительным с появлением электронных вычислительных машин для обозначения совокупности действий, составляющих некоторый процесс. Здесь подразумевается не только процесс решения некоторой математической задачи, но и кулинарный рецепт и инструкция по использованию стиральной машины, и многие другие последовательные правила, не имеющие отношения к математике, – все эти правила являются алгоритмами. Слово «алгоритм» в наши дни известно каждому, оно настолько уверенно шагнуло в разговорную речь, что сейчас нередко на страницах газет, в выступлениях политиков встречаются выражения «алгоритм поведения», «алгоритм успеха» и т.д.
Проблема определения понятия «алгоритм».
На протяжении многих веков понятие алгоритма связывалось с числами и относительно простыми действиями над ними, да и сама математика была, по большей части, наукой о вычислениях, наукой прикладной. Чаще всего алгоритмы представлялись в виде математических формул. Порядок элементарных шагов алгоритма задавался расстановкой скобок, а сами шаги заключались в выполнении арифметических операций и операций отношения (проверки равенства, неравенства и т.д.). Часто вычисления были громоздкими, а вычисления вручную – трудоемкими, но суть самого вычислительного процесса оставалась очевидной. У математиков не возникала потребность в осознании и строгом определении понятия алгоритма, в его обобщении. Но с развитием математики появлялись новые объекты, которыми приходилось оперировать: векторы, графы, матрицы, множества и др. Как определить для них однозначность или как установить конечность алгоритма, какие шаги считать элементарными? В 1920-х задача точного определения понятия алгоритма стала одной из центральных проблем математики. В то время существовало две точки зрения на математические проблемы:
Все проблемы алгоритмически разрешимы, но для некоторых алгоритм еще не найден, поскольку еще не развиты соответствующие разделы математики.
Есть проблемы, для которых алгоритм вообще не может существовать.
Идея о существовании алгоритмически неразрешимых проблем оказалась верной, но для того, чтобы ее обосновать, необходимо было дать точное определение алгоритма. Попытки выработать такое определение привели к возникновению теории алгоритмов, в которую вошли труды многих известных математиков – К.Гедель , К.Черч, С.Клини, А.Тьюринг , Э.Пост, А.Марков, А.Колмогоров и многие другие.
Точное определение понятия алгоритма дало возможность доказать алгоритмическую неразрешимость многих математических проблем.
Появление первых проектов вычислительных машин стимулировало исследование возможностей практического применения алгоритмов, использование которых, ввиду их трудоемкости, было ранее недоступно. Дальнейший процесс развития вычислительной техники определил развитие теоретических и прикладных аспектов изучения алгоритмов.
Понятие «алгоритма».
В повседневной жизни каждый человек сталкивается с необходимостью решения задач самой разной сложности. Некоторые из них трудны и требуют длительных размышлений для поиска решений (а иногда его так и не удается найти), другие же, напротив, столь просты и привычны, что решаются автоматически. При этом выполнение даже самой простой задачи осуществляется в несколько последовательных этапов (шагов). В виде последовательности шагов можно описать процесс решения многих задач, известных из школьного курса математики: приведение дробей к общему знаменателю, решение системы линейных уравнений путем последовательного исключения неизвестных, построение треугольника по трем сторонам с помощью циркуля и линейки и т.д. Такая последовательность шагов в решении задачи называется алгоритмом. Каждое отдельное действие – это шаг алгоритма. Последовательность шагов алгоритма строго фиксирована, т.е. шаги должны быть упорядоченными. Правда, существуют параллельные алгоритмы, для которых это требование не соблюдается.
Понятие алгоритма близко к другим понятиям, таким, как метод (метод Гаусса решения систем линейных уравнений), способ (способ построения треугольника по трем сторонам с помощью циркуля и линейки). Можно сформулировать основные особенности именно алгоритмов.
Наличие исходных данных и некоторого результата.
Алгоритм – это точно определенная инструкция, последовательно применяя которую к исходным данным, можно получить решение задачи. Для каждого алгоритма есть некоторое множество объектов, допустимых в качестве исходных данных. Например, в алгоритме деления вещественных чисел делимое может быть любым, а делитель не может быть равен нулю.
Массовость, т.е. возможность применять многократно один и тот же алгоритм. Алгоритм служит, как правило, для решения не одной конкретной задачи, а некоторого класса задач. Так алгоритм сложения применим к любой паре натуральных чисел.
Детерминированность.
При применении алгоритма к одним и тем же исходным данным должен получаться всегда один и тот же результат, поэтому, например, процесс преобразования информации, в котором участвует бросание монеты, не является детерминированным и не может быть назван алгоритмом.
Результативность.
Выполнение алгоритма должно обязательно приводить к его завершению. В то же время можно привести примеры формально бесконечных алгоритмов, широко применяемых на практике. Например, алгоритм работы системы сбора метеорологических данных состоит в непрерывном повторении последовательности действий («измерить температуру воздуха», «определить атмосферное давление»), выполняемых с определенной частотой (через минуту, час) во все время существования данной системы.
Определенность.
На каждом шаге алгоритма у исполнителя должно быть достаточно информации, чтобы его выполнить. Кроме того, исполнителю нужно четко знать, каким образом он выполняется. Шаги инструкции должны быть достаточно простыми, элементарными, а исполнитель должен однозначно понимать смысл каждого шага последовательности действий, составляющих алгоритм (при вычислении площади прямоугольника любому исполнителю нужно уметь умножать и трактовать знак «x » именно как умножение). Поэтому вопрос о выборе формы представления алгоритма очень важен. Фактически речь идет о том, на каком языке записан алгоритм.
Формы представления алгоритмов.
Для записи алгоритмов необходим некоторый язык, при этом очень важно, какой именно язык выбран. Записывать алгоритмы на русском языке (или любом другом естественном языке) громоздко и неудобно.
Например, описание алгоритма Евклида нахождения НОД (наибольшего общего делителя) двух целых положительных чисел может быть представлено в виде трех шагов. Шаг 1: Разделить m на n . Пусть p – остаток от деления.
Шаг 2: Если p равно нулю, то n и есть исходный НОД.
Шаг 3: Если p не равно нулю, то сделаем m равным n , а n равным p . Вернуться к шагу 1.
Приведенная здесь запись алгоритма нахождения НОД очень упрощенная. Запись, данная Евклидом, представляет собой страницу текста, причем последовательность действий существенно сложней.
Одним из распространенных способов записи алгоритмов является запись на языке блок-схем. Запись представляет собой набор элементов (блоков), соединенных стрелками. Каждый элемент – это «шаг» алгоритма. Элементы блок-схемы делятся на два вида. Элементы, содержащие инструкцию выполнения какого-либо действия, обозначают прямоугольниками, а элементы, содержащие проверку условия – ромбами. Из прямоугольников всегда выходит только одна стрелка (входить может несколько), а из ромбов – две (одна из них помечается словом «да», другая – словом «нет», они показывают, соответственно, выполнено или нет проверяемое условие).
На рисунке представлена блок-схема алгоритма нахождения НОД:
Построение блок-схем из элементов всего лишь нескольких типов дает возможность преобразовать их в компьютерные программы и позволяет формализовать этот процесс.
Формализация понятия алгоритмов. Теория алгоритмов.
Приведенное определение алгоритма нельзя считать представленным в привычном математическом смысле. Математические определения фигур, чисел, уравнений, неравенств и многих других объектов очень четки. Каждый математически определенный объект можно сравнить с другим объектом, соответствующим тому же определению. Например, прямоугольник можно сравнить с другим прямоугольником по площади или по длине периметра. Возможность сравнения математически определенных объектов – важный момент математического изучения этих объектов. Данное определение алгоритма не позволяет сравнивать какие-либо две таким образом определенные инструкции. Можно, например, сравнить два алгоритма решения системы уравнений и выбрать более подходящий в данном случае, но невозможно сравнить алгоритм перехода через улицу с алгоритмом извлечения квадратного корня. С этой целью нужно формализовать понятие алгоритма, т.е. отвлечься от существа решаемой данным алгоритмом задачи, и выделить свойства различных алгоритмов, привлекая к рассмотрению только его форму записи. Задача нахождения единообразной формы записи алгоритмов, решающих различные задачи, является одной из основных задач теории алгоритмов. В теории алгоритмов предполагается, что каждый шаг алгоритма таков, что его может выполнить достаточно простое устройство (машина), Желательно, чтобы это устройство было универсальным, т.е. чтобы на нем можно было выполнять любой алгоритм. Механизм работы машины должен быть максимально простым по логической структуре, но настолько точным, чтобы эта структура могла служить предметом математического исследования. Впервые это было сделано американским математиком Эмилем Постом в 1936 (машина Поста) еще до создания современных вычислительных машин и (практически одновременно) английским математиком Аланом Тьюрингом (машина Тьюринга).
История конечных автоматов: машина Поста и машина Тьюринга.
Машина Поста – абстрактная вычислительная машина, предложенная Постом (Emil L.Post), которая отличается от машины Тьюринга большей простотой. Обе машины «эквивалентны» и были созданы для уточнения понятия «алгоритм».
В 1935 американский математик Пост опубликовал в «Журнале символической логики» статью Финитные комбинаторные процессы, формулировка 1 . В этой статье и появившейся одновременно в Трудах Лондонского математического общества статье английского математика Тьюринга О вычислимых числах с приложением к проблеме решения были даны первые уточнения понятия «алгоритм». Важность идей Поста состоит в том, что был предложен простейший способ преобразования информации, именно он построил алгоритмическую систему (алгоритмическая система Поста). Пост доказал, что его система обладает алгоритмической полнотой. В 1967 профессор В.Успенский пересказал эти статьи с новых позиций. Он ввел термин «машина Поста». Машина Поста – абстрактная машина, которая работает по алгоритмам, разработанным человеком, она решает следующую проблему: если для решения задачи можно построить машину Поста, то она алгоритмически разрешима. В 1970 машина Поста была разработана в металле в Симферопольском университете. Машина Тьюринга была построена в металле в 1973 в Малой Крымской Академии Наук.
Абстрактная машина Поста представляет собой бесконечную ленту, разделенную на одинаковые клетки, каждая из которых может быть либо пустой, либо заполненной меткой «V». У машины есть головка, которая может перемещаться вдоль ленты на одну клетку вправо или влево, наносить в клетку ленты метку, если этой метки там ранее не было, стирать метку, если она была, либо проверять наличие в клетке метки. Информация о заполненных метками клетках ленты характеризует состояние ленты, которое может меняться в процессе работы машины. В каждый момент времени головка находится над одной из клеток ленты и, как говорят, обозревает ее. Информация о местоположения головки вместе с состоянием ленты характеризует состояние машины Поста. Работа машины Поста заключается в том, что головка передвигается вдоль ленты (на одну клетку за один шаг) влево или вправо, наносит или стирает метки, а также распознает, есть ли метка в клетке в соответствии с заданной программой, состоящей из отдельных команд.
Машина Тьюринга состоит из счетной ленты (разделенной на ячейки и ограниченной слева, но не справа), читающей и пишущей головки, лентопротяжного механизма и операционного исполнительного устройства, которое может находиться в одном из дискретных состояний q 0, q 1, …, qs , принадлежащих некоторой конечной совокупности (алфавиту внутренних состояний), при этом q 0 называется начальным состоянием. Читающая и пишущая головка может читать буквы рабочего алфавита A = {a 0, a 1, …, at }, стирать их и печатать. Каждая ячейка ленты в каждый момент времени занята буквой из множества А . Чаще всего встречается буква а 0 – «пробел». Головка находится в каждый момент времени над некоторой ячейкой ленты – текущей рабочей ячейкой. Лентопротяжный механизм может перемещать ленту так, что головка оказывается над соседней ячейкой ленты, при этом возможна ситуация выхода за левый край ленты, которая является аварийной (недопустимой), или машинного останова, когда машина выполняет предписание об остановке.
Современный взгляд на алгоритмизацию.
Теория алгоритмов строит и изучает конкретные модели алгоритмов. С развитием вычислительной техники и теории программирования возрастает необходимость построения новых экономичных алгоритмов, изменяются способы их построения, способы записи алгоритмов на языке, понятном исполнителю. Особый тип исполнителя алгоритмов – компьютер, поэтому необходимо создавать специальные средства, позволяющие, с одной стороны, разработчику в удобном виде записывать алгоритмы, а с другой – дающие компьютеру возможность понимать написанное. Такими средствами являются языки программирования или алгоритмические языки.
Анна Чугайнова
Для начала как уже известно существуют ГОСТы, которые строго описывают сами блок-схемы и их построение, соединения (ГОСТ 19.701–90, ГОСТ 19.002–80, ГОСТ 19.003–80 ). Основные элементы схем алгоритма представлены в таблице 1.1.
Таблица 1.1 – Основные элементы схем алгоритмов
Продолжения таблицы 1.1.
Отображает решение или функцию переключательного типа с одним входом и двумя или более альтернативными выходами, из которых только один может быть выбран после вычисления условий, определенных внутри этого элемента. Вход в элемент обозначается линией, входящей обычно в верхнюю вершину элемента. Если выходов два или три, то обычно каждый выход обозначается линией, выходящей из оставшихся вершин (боковых и нижней). Если выходов больше трех, то их следует показывать одной линией, выходящей из вершины (чаще нижней) элемента, которая затем разветвляется. Соответствующие результаты вычислений могут записываться рядом с линиями, отображающими эти пути. Примеры решения: в общем случае − сравнение (три выхода: >, <, =); в программировании − условные операторы if (два выхода: true, false) и case (множество выходов).Продолжения таблицы 1.1.
Продолжения таблицы 1.1.
Продолжения таблицы 1.1.
Данные элементы удобно создавать и соединять в специализированных программах, которых существует множество, в том числе бесплатных. Как это сделать в Visio?
Если вкратце, то Visio позволяет рисовать различные схемы (бизнес процессы, алгоритмы, планы зданий и т.д.) при помощи готовых и создаваемых фигур. В нашем случае в качестве фигур выступают основные элементы схемы алгоритма.
В качестве примера нарисуем алгоритм для простой программы – нахождению вещественных корней квадратного уравнения для заданных значений коэффициентов a, b и с.
Напомним, что решение осуществляется через дискриминант
При корней два, и они вычисляются по формуле
При корень один (в некоторых контекстах говорят также о двух равных или совпадающих корнях), кратности 2:
При вещественных корней нет.
Особенностью данного алгоритма будет разветвляющийся процесс при проверке дискриминанта квадратного уравнения на условие D<0.