Исполнители алгоритмов — человек и автомат

10. Лекция: Исполнители алгоритмов - человек и автомат Рассматриваются основные понятия о базовых исполнителях алгоритмов – человеке и конечном автомате, об их управляющих и исполняющих подсистемах, структурах. Исполнителем называется некоторая биологическая, техническая или смешанная структура, способная исполнять (покомандно или программно) некоторый класс алгоритмов в некоторой операционной среде (некотором множестве допустимых "инструментов" и "команд"). Наиболее используемые типы исполнителя алгоритмов – человек или автомат (компьютер). Человек как исполнитель алгоритмов – совокупность исполняющих подсистем (мышечная, двигательная, зрительная, обонятельная и др.) и управляющей подсистемы (нервная, нейронная). Нервная система передает информацию, получаемую от нервных окончаний кожи, глаз, ушей и других органов, к нервным центрам для ее последующей интеграции, обработки и выработке адекватной реакции. Нервная система – совокупность взаимодействующих нервных клеток или нейронов. У человека их – громадное количество. Пример. По различным оценкам физиологов, в коре переднего мозга человека – около 50 млрд нейронов. Нейроны, хотя и работают медленно (около сотни инструкций в секунду), но могут за счет более эффективного взаимодействия друг с другом и организации сложнейших нейроструктурных связей (кластеров) решать сложные мыслительные задачи, принимать решения. Пример. Такая плохо структурируемая, но "простая" для человека задача, как "одеться по погоде", решается быстро с помощью обработки зрительной, слуховой информации и согласованной "нейронной" оценки ситуации, хотя она и плохо формализуемая. Компьютеру эту задачу решать будет намного сложнее. С другой стороны, вычислительные ресурсы человека ограничены по сравнению с возможностями компьютера, который во много раз лучше (быстрее, точнее) решает хорошо формализуемые и хорошо структурируемые задачи. Нейроны служат для передачи информации за счет нервных импульсов, которая расшифровывается в соответствующих областях коры головного мозга. В непосредственную (сенсорную) память человека поступает информация от различных сенсоров: зрительных, слуховых, обонятельных и т.д. Затем эта информация переводится в оперативную память (память сознания). Далее она пересылается в долговременную память с привлечением подсознания ("укладывается на полочки" с соответствующими названиями "Формы поведения", "Объекты и образы", "Правила и процедуры обнаружения и идентификации объектов", "Правила выборки и организации информации", "Жизненный опыт", "Бытовые навыки и умения", "Профессиональные навыки и умения" и др.). Пример. Увиденный человеком конкретный компьютер ассоциируется с абстрактным понятием "Компьютер" (из долговременной памяти) – например со сведениями об этом устройстве – информационными кодами, которые определяют объект (связь, понятие). Коды связываются между собой, создавая образ конкретного компьютера. В живом организме передача, хранение или обработка информации происходит с помощью биохимических реакций и сообщений – сигнальных молекулярных систем и их превращений за счет химических реакций катализа и разностей концентрации химических веществ. Разность потенциалов действий (электрические сигналы) проводят нервные волокна, с помощью центральной нервной системы. При этом используется и генная информация, которая передается от ДНК к РНК, от РНК – к белку, определяя новую белковую структуру, ее функции. Второй важный тип исполнителей – конечные автоматы , автоматические (то есть функционирующие определенный промежуток времени без участия человека) устройства, вход, выход и состояния которых можно описать конечными последовательностями сообщений (слов над конечными алфавитами). Любой конечный автомат реализует некий непустой класс алгоритмов и состоит из совокупности управляющего автомата, который определяет порядок выполнения действий, и операционного автомата, реализующего сами действия, выполняемые автоматом. Пример. Пример конечного автомата – автомат для продажи газированной воды. Его функционирование можно изобразить графом (рис. 10.1), если ввести следующие множества и события: X = {1, 3, Г, Ø} – входное множество, Y = {В, С, О} – выходное множество, S = {s0 , s1 , s2 , s3} – множество состояний, 1 – входной сигнал "опустить 1 руб.", 3 – входной сигнал "опустить 3 руб.", Г – входной сигнал "опустить гнутую монету", Ø– входной сигнал "монета не опущена", В – выходной сигнал "выдача воды газированной без сиропа", С – выходной сигнал "выдача газированной воды с сиропом", О – выходной сигнал "отказ выдать воду", s0 – первое состояние – "начальное состояние", s1 – второе состояние – "обработка 1 руб.", s2 – третье состояние – "обработка 3 руб.", s3 – четвертое состояние – "состояние неисправности". Рис. 10.1.  Граф автомата для продажи газированной воды Функционирование конечного автомата происходит в дискретные моменты времени t = 0, 1, 2, ..., T. Изменение состояния автомата , то есть переход из текущего состояния в новое состояние , может быть осуществлено либо до выдачи выходного сигнала , либо – после выдачи этого сигнала. В связи с этим, выделяют два типа конечных автоматов – автоматы Мили и автоматы Мура, которые различаются законами функционирования автоматов. Законы функционирования автомата Мили: Законы функционирования автомата Мура: Функция выходов f автомата Мура явно не зависит от входного сигнала и полностью определяется только самим внутренним состоянием автомата, которое, в свою очередь, определяется входным сигналом. Пример. Пример конкретного автомата Мура приведен выше (автомат для газировки). Приведем абстрактный пример автомата Мили: Х = {х1, х2} , У = {у1, у2, у3} , S = {s0, s1, s2, s3, s4, s5} , функции перехода и выхода f зададим таблицами соответствий: – функция перехода s(t – 1) S1 s1 s2 s3 s3 s4 s5 x(t) Х1 х2 x1 x2 x1 x2 х2 x1 s(t) S2 s3 s4 s2 s4 s3 s5 s5 – функция выхода s(t – 1) S1 s1 s2 s2 s3 s3 s4 s5 x(t) X1 x2 x1 x2 x1 х2 х2 х1 y(t) У2 у3 y1 y1 y3 у2 у3 y2 Компьютер можно рассматривать как совокупность взаимодействующих конечных автоматов. Рассмотрим такую структуру подробнее. Память компьютера – последовательность ячеек памяти, то есть физических устройств, куда можно записывать или считывать последовательность битов, каждый из которых хранится в нужном разряде. Пример. Запишем числа 1310, в формате целых чисел в восьмиразрядную ячейку памяти запишется в виде (старший бит будет содержать бит знака числа, например, 1 – если число отрицательно и 0 – если число положительно). Учитывая, что 1310 = 11012, получаем представление вида: Аналогичным образом представляются в памяти компьютера и вещественные числа: либо по частям (целая часть – отдельно, дробная – отдельно), либо в специальной, так называемой нормализованной форме, для которой хранится отдельно дробная часть (мантисса) и порядок – степень двойки, домножением на которую можно записать данное число. Пример. Если десятичное число равно 5,25, то есть в двоичной форме – 101,01, то оно записывается в нормализованной форме: 0,10101 с порядком, равным в двоичном виде 101. Команды, как и числа, размещаются (в битовом изображении) в специальных электронных устройствах – так называемых регистрах. Регистр – электронное устройство, как и ячейка памяти, запомнающее и хранящее (временно) последовательность битов определенной длины. Регистры реализуются более дорогими и чувствительными физическими устройствами и поэтому, по сравнению с основной памятью компьютера, регистровая память или так называемая кэш-память – невелика. Пример. Для компьютера с памятью 512 мегабайт основной памяти может быть характерна регистровая память в 64 килобайта. Каждой команде ставится в соответствие операция, производится расшифровка кода этой операции, затем извлекаются операнды или числа, над которыми необходимо выполнить операцию. Далее выполняется операция с этими операндами, и результат операции помещается в соответствующую ячейку памяти. Кроме оперативной памяти, компьютер имеет внешнюю память (ВЗУ) с большой емкостью, но с большим временем записи или считывания информации. Внешняя память реализуется с помощью внешних носителей информации: магнитных или оптических дисков. Джон фон Нейман предложил ряд принципов, которые легли в основу фон Неймановской или классической архитектуры компьютера : 1. память состоит из однородных ячеек памяти с адресами; 2. программа состоит из последовательных команд; 3. хранение программы и обрабатываемых ею данных – одинаковое, в битовом виде; 4. команды выполняются последовательно, данные извлекаются в соответствии с командами; 5. процессор – один и имеет централизованное управление и доступ к памяти. Структура ЭВМ фон Неймановской архитектуры приведена на рис. 10.2. Рис. 10.2.  Структура ЭВМ фон Неймановской архитектуры Арифметико-логическое устройство (АЛУ) выполняет арифметические, логические операции. Пример. Команды АЛУ – просты: "сравнить два числа", "переслать число", "взять дизъюнкцию" и др. Устройство управления (УУ) организует работу ЭВМ, в частности это устройство извлекает очередную команду из памяти, расшифровывает команду, выбирает из памяти операнды к расшифрованной команде и передает их АЛУ для выполнения расшифрованной операции, а после выполнения пересылает результат для хранения в память. При этом УУ реагирует на нормальный или аварийный ход выполнения операции. Совокупность АЛУ и УУ, информационно-управляющих линий называется процессором компьютера (его структура приведена на рис. 10.3; жирная линия – информационное взаимодействие, другая – управляющее). Рис. 10.3.  Структура процессора Обмен информацией с компьютером осуществляется устройствами ввода и устройствами вывода. Пример. Устройствами ввода являются, например, клавиатура, мышь. Устройствами вывода — дисплей, принтер, плоттер. Распространенный тип компьютера – персональный компьютер. Персональный компьютер отвечает требованиям малой стоимости, малых размеров, малого энергопотребления, высокой надежности, высокого уровня интеграции компонентов, адаптируемости к разнообразным применениям и др. Ядро персонального компьютера – системная (материнская плата), на которой размещаются: микропроцессор, микропроцессорная память, интерфейсная система микропроцессора для сопряжения и связи с другими устройствами, генератор тактовых импульсов, контроллеры устройств (схем), интегрированных в материнскую плату, микросхемы ОЗУ и ПЗУ и др. Другими важными устройствами персонального компьютера являются: 1. дисковод гибких магнитных дисков; дисковод жестких магнитных дисков; 2. CD-ROM (устройство только для чтения компакт-дисков) или CD-RW (чтение и перезапись); 3. монитор (дисплей); 4. видеокарта (видеоадаптер) для обеспечения связи системного блока и монитора; 5. клавиатура; 6. принтер; 7. сканер; 8. плоттер (графопостроитель); 9. дигитайзер (кодирующий планшет); 10. манипулятор-мышь или манимулятор-трекбол; 11. звуковая карта (адаптер); 12. звуковые колонки; 13. модем и другие устройства. Классификацию компьютеров проводят по быстродействию, технологии использования и др. Дадим обобщенную и поэтому нечеткую и перекрывающуюся классификацию. 1. Суперкомпьютеры – наиболее мощные компьютеры в мире, используемые для решения очень сложных и очень больших задач (исследования космоса, ядерной физики, геологии и др.). 2. Компьютеры универсального назначения, используемые для решения сложных и больших задач. 3. Персональные компьютеры, используемые в индивидуальном порядке для решения как несложных и небольших, так и сложных, больших задач. Пример. Супервычислительный центр может быть создан для решения государственных проблем, например обороны, изучения космоса, прогноза погоды, макроэкономического прогнозирования и др. В этом центре могут использоваться как персональные компьютеры на рабочих местах сотрудников, так и компьютеры общего, универсального назначения для решения менее сложных, например вспомогательных проблем. При работе на компьютере необходимо следовать определенным и простым санитарно-гигиеническим правилам , так как компьютер имеет вредно влияющие на здоровье человека факторы: излучения (инфракрасное, рентгеновское, электромагнитное); вибрация и шум; электростатические поля; ультразвук строчной частоты монитора и др. Необходимо соблюдать простые санитарно-гигиенические и эргономические правила работы на компьютере, в компьютерном зале: • работа с компьютером не более 4-х часов подряд с 10-минутными перерывами после каждого часа интенсивной работы или после 2-х часов менее интенсивной работы; • расстояние от глаз до поверхности экрана – не менее 0,6 м; • перемещаемость клавиатуры относительно экрана в пределах 0,5-1,0 м; • преимущественно желтый, зеленый, серый или светло-голубой фон дисплея; • температура воздуха в помещении – 15-25 градусов по Цельсию; • относительная влажность помещения – 45-75%; • наличие свободной площади рабочего стола не менее 0,3x1,0 м; • размер экрана по диагонали – не меньше 17 дюймов; • разрешение экрана – не менее 800x600; • частота обновления кадра – не менее 70 Гц; • размер зерна экрана (расстояние между точками на экране) – не более 0,26; • частота кадров (мерцание экрана) – не менее 75 Гц; • стандарты безопасности, например MPR-II. Минимальный объем знаний, который необходим для решения профессиональных задач и приобщения к знаниям, накопленным с помощью компьютера и различных информационных систем и сетей, а также для решения различных бытовых задач с помощью компьютера, называют компьютеpной гpамотностью.