Структурные особенности современных  ЭВМ

 
 Адресация памяти (сегментный адрес, смещение)  
 Для адресации памяти в процессоре x86 используются 16-битные регистры. Но 16 бит позволяют получить значения от 0 до 65535 (64Кб), поэтому используется следующее:  
Адресация производится двумя регистрами.  
В одном из регистров хранится сегментный адрес, в другом - смещение.  
Это усложняет адресацию памяти , но упрощает аппаратную реализацию(Чтобы получить реальный адрес, нужно умножить сегментный адрес на 16 и сложить со смещением). Один и тот-же реальный адрес может быть представлен по разному.  
 Прерывания  
 В компьютере одновременно работает много устройств. Если бы центральный процессор всё время отслеживал их работу, времени на выполнение основной задачи оставалось бы на много меньше. Поэтому в современных ЭВМ реализован принцип прерываний.  
 Прерывание генерируется устройством в момент, когда необходимо вмешательство процессора - при нажатии клавиши, сигнале принтера, таймера и множества других причин.  
 Прерывание "прерывает" работу компьютера. Процессор запоминает место программы, на котором он остановился и некоторую вспомогательную информацию. Затем выполняется программа обработки прерывания и процессор возвращается к запомненному месту и продолжает выполнение программы.  
 Прерывание может быть и программным. При выводе данных на экран вызывается подпрограмма, которая находится в операционной системе. Этот вызов так-же реализуется через механизм прерываний.  
 Защита памяти  
 В современных операционных системах предусмотрен т.н. многозадачный режим, когда в памяти находится одновременно несколько программ. И даже если нет многозадачности, всёравно кроме основной программы в памяти постоянно находится множество других программ, в т.ч. BIOS(базовая система ввода-вывода), command.com(командный процессор), файловая оболочка NC и д.р.  
 Чтобы нечаянно не перезаписать данные чужой программы, реализуется защищённый режим, в котором пресекается выход программы за пределы отведённого ей адресного пространства. Такой механизм был реализован в больших ЭВМ, т.к. они изначально были ориентированы на многопользовательский режим.  
 Параллельная обработка  
 Для повышения быстродействия современные супер-ЭВМ снабжаются не одним, а несколькими десятками процессоров, которые работают одновременно. Это усложняет программирование, но в ряде решаемых научных задач (с большим количеством вычислений), повышает быстродействие. Элементарный пример: Требуется найти максимальное значение в каждой строке матрицы. Обычный алгоритм будет обрабатывать строки по очереди: 1, 2, 3...  
Для многопроцессорных ЭВМ алгоритм должен строиться по другому: каждый процессор ищет максимум в своей строке(примем, что строк меньше чем процессоров) - выигрыш очевиден.

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

  Понятие алгоритма  возникло задолго до появления  ЭВМ и стало одним из основных  понятий математики. Слово "алгоритм" произошло от имени среднеазиатского  математика IX века аль-Харезми и  сначала использовалось в математике  для обозначения правил выполнения  четырёх арифметических действий: сложения, вычитания, деления и умножения, которые предписывают определённую последовательность действий, благодаря которым по двум данным произвольным числам можно получить их сумму, произведение и т.д.  
  Математика располагает огромным количеством алгоритмов: вычисление квадратного корня, нахождение наибольшего общего делителя (алгоритм Евклида), алгоритм решения квадратного уравнения, вычисление площади фигур и т.д.  
  В математической энциклопедии 1977 года понятие "алгоритм" определяется следующим образом:  
  алгоритм - точное предписание, которое задаёт вычислительный процесс, начинающийся с произвольного исходного данного из совокупности всех возможных, и направленный на получение полностью определяемого этим данным результата.  
  Отметим два момента: 1) - для математики все алгоритмы носят вычислительный характер. Естественно, это определение устарело, т.к. в информатике существуют и нечисловые алгоритмы. 2) - понятие "алгоритм" даётся через понятие "предписание", а что такое "предписание"? Понятие "алгоритм" принадлежит к числу основных понятий математики и не допускает определения в терминах более простых понятий. Фактически в определении перечислены свойства алгоритма, которые отличают его от других предложений языка.  
  Для пояснения понятия "алгоритм" важное значение имеет определение понятия "исполнитель алгоритма".  
  Любой алгоритм предназначен для конкретного исполнителя. Этим исполнителем может быть человек, станок с ЧПУ, калькулятор, микроволновая печь, транслятор с некоторого алгоритмического языка и т.д. Для исполнителя следует чётко оговорить, какие предписания он понимает и умеет исполнять. Перечень таких предписаний называется множеством предписаний исполнителя. Для ЭВМ - это набор машинных команд, поэтому , строго говоря, когда мы набираем текст в текстовом редакторе, исполнителем является программа-редактор, которая умеет обрабатывать нажатия клавишь - для ввода символов, выделения, удаления, вставки фрагментов, установки шрифтов, форматирования и т.д.  
  Пример исполнителя - Черепашка. Исполнитель Черепашка понимает язык Лого, придуманный Пейпертом.  
  Базовые предписания:  
  вперёд число  
  назад число  
переместиться на заданное число шагов (единиц длины)  
  направо число  
  налево число  
повернуть на заданное число градусов  
  При движении черепашки за ней остаётся след (хвост играет роль пера). Чтобы след не оставался, следует выполнить команду поднять хвост. Теперь след появится только после выполнения команды опустить хвост.  
  Пример алгоритма:

 
  В языке Лого есть и другие конструкции, но об этом позже. Простые исполнители (Черепашка, Муравей, Робот и другие) широко используются в преподавании школьного курса информатики.

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

  1. Массовость алгоритма. Алгоритм должен быть пригодным для решения задач с любыми исходными данными из некоторого множества. Формально множество может состоять из одного элемента, но фактически это свойство означает пригодность алгоритма для некоторого класса исходныйх данных. Например, алгоритм поиска НОД применим к любой паре натуральных чисел, а не только к числам 51 и 34.  
  Будем считать, что для каждого алгоритма существует свой класс объектов, допустимых в качестве исходных данных. Тогда св-во массовости означает применимость алгоритма ко всем объектам этого класса. А количество объектов класса (конечное или бесконечное) - свойство самого класса исходных данных.  
  С массовостью связаны трудности, возникающие при доказательстве правильности алгоритма - для бесконечного числа исходных данных его нельзя проверить выполнением.  
  Пример:  
   
   
  Доказать, что последовательность сходится к единице.  
  Например n=17:  
   
  2. Понятность алгоритма. Для данного исполнителя - каждое предписание должно входить в систему команд исполнителя. Исполнитель должен знать как выполнить каждое предписание. Нарушение этого принципа вызывает диагносту ошибки типа "не понимаю", или "не могу выполнить".  
  3. Дискретность алгоритма. Алгоритм состоит из конечного числа шагов, каждый из которых начинается только после завершения предыдущего. Это свойство может нарушаться при выполнении программы на компьютерах с параллельной обработкой (матричные процессоры).  
  4. Результативность алгоритма. Алгоритм должен "выдавать" результат через конечное число шагов. При этом либо достигается конечная цель, либо выдаётся сообщение о невозможности решения задачи.  
  В математике существуют вычислительные процедуры, имеющие алгоритмический характер, но не обладающие свойством конечности. Например, есть алгоритм, позволяющий вычислить точное значение числа Пи.  
  Например:  
   
  Этот вычислительный процесс бесконечен, и если его оборвать на некотором шаге, мы получим приближенное значение Пи. Т.е. любой алгоритм должен быть не только потенциально, но и актуально выполнимым.  
  Проиллюстрируем понятие результативности алгоритма на следующем примере. Пусть возможными исходными данными являются слова (последовательности символов), состоящие только из букв {а} и {b}, и начинающиеся на {a}или{ba}.  
  Определим две операции над этими словами 
Операция V₁: aP Pb (где P - произвольное слово) 
Операция V₂: baP Paba 
Рассмотрим следующий алгоритм:  
  Начало  
      пока X aaP повторять  
          если X = aP то X := Pb  
          иначе если X = baP то X := Paba  
          иначе сотп  
      конец цикла пока  
      сообщить P  
  Конец  
  1) Пусть х = babaa = ba (baa), слово P будем брать в скобки 
ba(baa) (baa)aba = ba(aaba) (aaba)aba = aa(baaba) 
Алгоритм останавливается. Результат P = baaba.  
  2) Пусть x = baaba = 
= ba(aba) (aba)aba = 
= a(baaba) (baaba)b = 
= ba(abab) (abab)aba = 
= a(bababa) (bababa)b = 
= ba(babab) (babab) aba =... 
= ba (bababa) (bababa) aba 
Можно показать, что этот процесс никогда не закончится (т.е. никогда не возникнет слово, начинающее : с "aa", но к каждому промежуточному слову можно применить операцию V₁ либо V₂ (зацикливание)  
  3) Пусть x = abaab = 
= a(baab) (baab)b = 
= ba(abb) (abb)aba = 
= a(bbaba) (bbaba)b = bbabab 
Что будет дальше? Алгоритм остановится, но никакого результата мы не получим - его нет (безрезультативная остановка).  
  5. Определённость алгоритма. - заключается в однозначности выполнения всех предписаний алгоритма. Благодаря этому свойству процесс реализации алгоритма не зависит от конкретного исполнителя и рассчитан на число механическое выполнением автоматом, не обладающим "здравым смыслом".  
  6. Эффективность алгоритма. - заключается в том, что каждый шаг алгоритма должен быть выполнен точно и за конечное время. Например, условие типа: "Если в десятичном представлении числа встретится подряд три семёрки, то…" неэффективно, т.к. его проверка может занять бесконечное время.  
  Неэффективным может быть и алгоритм, требующий, вообще говоря, конечного, но очень большого числа шагов, так что его выполнение займёт неприемлемо большое время (например, 100лет). К таким алгоритмам относится в частности, алгоритм перебора большого количества вариантов. Однако развитие вычислительной техники может сделать неэффективный алгоритм - эффективным (или же следует искать более эффективный алгоритм).

Уточнение понятия алгоритма. Машина Тьюринга.

  Прогресс в развитие математики и алгоритмических методов породил представление о том, что окончательным решением любой поставленной математической задачи должно быть её алгоритмическое решение.  
  Рене Декарт развивал аналитическую геометрию с намерением сделать геометрию доступной алгебраическим методам вычислений, что позволило существенно продвинуться по пути алгоритмизации геометрии.  
  Исааку Лейбницу принадлежит первая попытка придумать автоматически работающую машину для решения алгоритмических проблем.  
  Давид Гильберт знаменит постановкой в начале ХХ века целого рода проблем. В ряде задач требовалось построить некоторый алгоритм и т.д.  
  Со временем пришло понимание того, что алгоритмические методы не являются универсальными. Примеры даёт та же математика: большинство теорем, которые доказывают существование чего-либо, не дают алгоритма построения этого чего-либо.  
  Начиная с 1935 года был предложен род формальных определений алгоритма, который бы обладал всеми свойствами интуитивно понимаемого алгоритма. Относительно всех уточнений была доказана их эквивалентность. Мы рассмотрим одно из них, предложенное Тьюрингом.  
  Машина Тьюринга - это некоторое воображаемое устройство, которое тем не менее можно представить в виде некоторого гипотетического механизма. Его основа - бесконечная лента, разделённая на ячейки.  
   
  a₀ - "пустой" символ  
  В каждую ячейку можно записать один символ из некоторго алгоритма A = {a₀}{a₁, ... ,a_n} Запись/чтение производится с помощью головки, которая в каждый данный момент времени находится над некоторой ячейкой ленты. Головка с помощью исполнительного мезанизма может перемещаться вдоль ленты "шагами" по одной ячейке.  
  Исполнительный механизм может находиться в одном из состояний {q₀,q₀, ... q_s}. Алгоритм работы машины Тьюринга описывается матрицей, каждая строка которой имеет формат:  
   
  В матрице перечислены все варианты сочетаний состояние - символ. Машина Тьюринга Т работает согласно следующим правилам.  
  Пусть Т находится в состоянии q, а читающая головка прочла на ленте символ a. Находим в таблице строку, которая начинается с символов qa (она единственна!). 
Если V A, то головка стирает содержимое рабочей ячейки и заносит туда символ V. 
Если V A, то он обозначает одно из следующих действий:  
V=L - сдвинуться влево, V=R - сдвинуться вправо, V=S - конец работы. Если V S , то машина Тьюринга после выполнения действия V переходит в состояние q'  
  Пример машины Тьюринга.  
  Опишем машину, в альфавите A = {a₀,a₁}, где a₀ - пустой символ, a₁="*" , которая сдвигается на 3 позиции вправо, записывает символ a₁ на ленту и останавливается.  
   
  Начинаем заполнять таблицу с начального состояния q₀

  Задача. Сконструировать в алфавите A = {0,1} с дополнением "пустого" символа (пробела) машину Тьюринга для решения следующей задачи: Если слово начинается с 0, то приписать в конце 1, а если с 1 - то 0.Начальное положение головки чтение/запись - перед словом.  
Используем более компактный способ записи:

Средства  записи алгоритмов.