22. Основные понятия теории алгоритмов.

• Теория алгоритмов — раздел математики, изучающий общие свойства алгоритмов. Понятие «алгоритм» сформировалось в мате­матике в 20-х годах XX в. Началом систематической разработки теории алгоритмов можно считать 1936 г. и связывают это начало с публикацией работы А.А. Черна.

Под алгоритмом всегда (и до возникновения строгой теории) понималась процедура, которая позволяла путем выполнения после­довательности элементарных шагов получать однозначный результат (независящий от того, кто именно выполнял эти шаги) или за конечное число шагов прийти к выводу о том, что решения не существует. В основе формализации понятия «алгоритм» лежит идея построения алгоритмической модели. Составляющими такой модели должны быть конкретный набор элементарных шагов, способы определения следующего шага и т.д. От модели также требуется простота и универсальность. 'Результатами теоретических исследований явились три основных класса арифметических моделей.

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

Второй класс моделей порожден следующей идеей. Для того чтобы алгоритм понимался однозначно, а его каждый шаг считался элементарным и выполнимым, он должен быть представлен так, чтобы его могла выполнять машина, к которой предъявляются уже упомянутые требования простоты и универсальности. Одной из таких машин явилась абстрактная машина Тьюринга.

состоит из трех частей ленты, головки и управляющего устройства (УУ). Лента беско­нечна в обе стороны и разбита на ячейки. В каждой ячейке может быть записан только один символ.Отсутствие символа в ячейке обозначается специальным «пус­тым» символом « ». Головка всег­да располагается над некоторой ячейкой ленты. Она может читать и писать символы, стирать их и перемещаться вдоль ленты.Третий класс моделей алгоритмов очень близок к предыдущему, но не оперирует конкретными машинными мехнизмами. Наиболее известная алгоритмич. Модель этого типа – нормальные алгоритмы Маркова. Для нормального алгоритма задается алфавит, над которым он работает, конечное множество допустимых подстановок и порядок их применения.

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

25.Форматы данных

Под данными понимается информация представленная в виде, пригодном для обработки автоматическими средствами. Формат зависит от архитектуры. Поэтому если не будем оговаривать особо, будем иметь в виду архитектуру типа РДР. Данные обрабатываемые на ЭВМ делят на :

1 Логические коды. 2 Числа с фиксированной запятой. 3 Числа с плавающей запятой

1 Могут размещаться в различных байтах, для их представления используются все байты. Логическими кодами могут быть числа без знаков, символьные величины. Символьные величины задаются в кодах ASCII. Седьмой разряд всегда содержит нуль. Числа без знаков имеют диапазон от 0 до 3778- для байты, от 000000 до 17777778- для слова. Бит увеличения задаёт значение отделения байтов или слова.

2 Могу занимать байт или слово. Если число занимает байт, то для его представления используются числа от 0 до 7, 8-для знака. При размещении числа с фиксированной запятой в слова, используются числа от 0 до 14. Диапазоны представление чисел в байтах (-12810/ +12710) в слове (-3276810/+3276710). В настоящее время в универсальных ЭВМ числа с фиксированной запятой практически перестали применяться. Любое действительное число представленное в системе счисления х=+-mNв степени +-р, где m-мантиса, распорядок числа. Если m <1, а число m не отрицательное, то запись числа -нормализованная слева.

3.  372,95=37,295*10 в степени 1=3,7295*10 в степени2=0,37295*10 в степени3.

Представление чисел с плавающей запятой неоднозначно. В ЭВМ с целью уменьшения погрешностей примечают нормализацию справа. Число называют нормализованным справа, если в мантике стоит не 0 (0,076*10 в степени 2=0,76*10 в степени 3) нормализованное число одинарной точности записывается в памяти следующим образом: знак числа в 15 бите первого слова. Нормализует число второй точности записывается в четырёх словах памяти .

Порядок числа с плавающей запятой изменяется от-12810 (2008) до +12710 (1778) и запоминается увеличенным на 12810. Такой способ представления порядка называется смешным.

23.Система счисления. Переходы из одной системы счисления в другую.Система счисления – совокупность приемов наименования и записи чисел. В любой системе счисления для представления чисел выби­рают некоторые символы (слова или знаки), называемые базисными числами, а все остальные числа получаются в результате каких-либо операций из базисных чисел в данной системе счисления.Системы счисления, в которых любое число получается путем сло­жения или вычитания базисных чисел – аддитивные. Недостатком этой системы счисления является то, что такие действия как: умно­жение и деление неудобно выполнять, поэтому более широкое рас­пространение получили позиционные системы. А(итое) - одно из базис­ных чисел. Позиционные СС (системы счисления) – если значение каждой цифры (ее вес) изменяется в зависимости от ее положения (позиции) в последовательности цифр, изображающих число. Арифметические действия над числами в позиционной СС производятся по тем же правилам, что и в десятичной системе, т.к. все они основываются на правилах выполнения действий над соответствующими полиномами. . При этом нужно только пользоваться теми таблицами сложения и умножения, которые имеют место при данном основании К системы счисления. К – основатель системы счисления.Так как в двоичной системе счисления для изображения любых чисел используются только две различные цифры, то при построении ЭВМ можно использовать элементы, которые могут аходиться только в двух состояниях (например, высокое или низкое напряжение в цепи, наличие или отсутствие электрического импульса и т.п.). Это обстоятельство, а также простота выполнения арифметических операций являются причиной того, что большинство современных ЭВМ используют двоичную систему счисления.Другие позитивные системы счисления: шестнадцатеричной, восьмеричная В ряде случаев числа, заданные в системе счисления с основанием Р, приходится изображать с помощью цифр другой системы счисления с основанием Q, где Q<Р. Такая ситуация возникает, например, когда в ЭВМ, способной непосредственно воспринимать только двоичные числа. Для того чтобы запись числа в смешанной системе счисления была однозначной, для представления любой Р-ичной цифры отводится одно и то же количество Q-ичных разрядов, достаточное для представления любого базисного числа Р-ичной системы. Десятичное число х = 925 в двоично-десятичной системе запишется в виде 1001 0010 0101. Здесь последовательные четверки (тетрады) двоичных разрядов изображают цифры 9, 2, 5 записи числа в десятичной системе счисления. Особого внимания заслуживает случай, когда Р = Q ^L где L— целое положительное число. В этом случае запись какого-либо числа в смешанной системе тождественно совпадает с изображением этого числа в системе счисления с основанием Q. В современных ЭВМ данные кодируются в основном в двоичных кодах, то, в частности, возникает необходимость перевода чисел из десятичной в двоичную систему счисления и наоборот. При рассмотрении правил перевода нужно учитывать, средствами какой арифметики должен быть осуществлен перевод, т.е. в какой системе счисления должны быть выполнены все необходимые для перевода действия. Перевод должен осущест­вляться средствами Р-ичной арифметики. Перевод Q-Р. Задача перевода произвольного числа x, задан­ного в системе счисления с основанием Q, в систему счисления с основанием Р сводится к вычислению полинома вида X=q _n Q ^n-1+…+q₁ Q ¹+ q ₀ Q ⁰ + q _-1Q ^-1 +…+q _-mQ^-m (3-11) Для получения Р-ичного изображения выражения (3.11) необхо­димо все цифры q _I , и число Q заменить Р-ичными изображениями и выполнить арифметические операции в Р-ичной системе счисления.Пример 1. Перевести число х = 371₈ в десятичную систему счисления, пользуясь правилами десятичной арифметики.Для перевода запишем число х в виде x = 3*8² +7*8¹+1 и выполним все необходимые действия в десятичной системе:x = 3*64 + 7*8+ 1 = 192 + 56+ 1 = 249Заметим, что при переводе следует придерживаться правила сохранения точности изображения числа в разных системах, причем под точностью понимается значение единицы самого младшего (правого) разряда, используемого в записи числа в той или иной системе счисления. Перевод Р —Q. Так как для перевода любого числа достаточно уметь переводить его целую и дробную части, рассмотрим отдельно эти два случая.1. Перевод целых чисел. Пусть известна запись целого числа N в системе счисления с основанием Р и требуется перевести это число в систему счисления с основанием Q.. Так как N— целое, то его запись в 2-ичной системе счисления имеет вид N=q _s q _s-1 …q ₁ q ₀ , где q, - искомые цифры Q-ичной системы 0 <q _I <Q - 1). Для опреде­ления q₀ разделим обе части равенства:N=q_s Q ^s +q_s-1 Q ^s-1 +…q ₁ Q ¹ +q₀ (3.12)на число Q, причем в левой части произведем деление, пользуясь правилами Р-ичной арифметики (так как запись числа N в Р-ичной системе счисления известна), а правую часть перепишем в виде N/Q=q _s Q ^s-1 +q _s-1 Q ^s-2 +…+q ₁ +q ₀ /Q Приравнивая между собой полученные целые и дробные части (учитывая, что q₁<Q) Таким образом, младший коэффициент до в разложении (3.12 определяется соотношением q ₀ =Q[n/q]_, причем указанные здесь действия на самом деле не выполняются, т как qо является просто остатком от деления N на Q. Заметим, что поскольку все операции выполняются в систем счисления с основанием Р, то в этой же системе будут получен искомые коэффициенты q,, поэтому их необходимо записать одной Q- ичной цифрой.

Пример 3. Перевести число N = 47 в двоичную систему с использованием десятичной арифметики. Применяя формулы (3.13) при Q = 2, имеем:47:2 = 23(1); 23:2=11(1); 11:2 = 5(1); 5:2 = 2(1); 2:2=1(0); 1:2 = 0(1).Поскольку числа нуль и единица в обеих системах счисления обозначаются одинаковыми цифрами 0 и 1, то в процессе деления сразу получим двоичное изображения искомых цифр:N= 101111.Перевод дробных чисел. Пусть необходимо перевести в Q-ичную систему счисления правильную дробь х (0 < x < 1), заданную в P-ичной системе счисления. Так как х < 1, то число х в Q-ичной системе счисления можно представить в виде полинома. Где q _I , (I =1, 2, ...) — искомые коэффициенты Q ичного разложения числах. Для определения q_л умножим обе части этого полинома на число Q причем в левой части произведем умножение, пользуясь правилами P-ичной арифметики (так как запись числа х в Р-ичной системе счисления известна), а правую часть перепишем в виде: xQ=q _-1+q _-2 Q^-1+q _–m Q ^–m+1+…Приравняем между собой полученные в правой части этого выражения целые и дробные части Таким образом, младший коэффициент q_л в разложении определяется соотношением q _-1 =[x _I Q] Замечание. При переводе приближенных дробей из одной? системы счисления в другую необходимо придерживаться следую­щего правила. Если единица младшего разряда числа х, заданного в Р-ичной системе счисления, есть Р ^{– k} , то в его Q-ичной записи следует сохранить l разрядов после запятой, где l удовлетворяет условию Q^-l>P^-k/2>Q^-(l+1)округляя последнюю оставляемую цифру обычным способом.

Пример 5. Перевести число х = 0.2 в двоичную систему счисления с использованием средств десятичной арифметики. Применение формул (3.15) при­водит к такой последовательности действий: 0.2*2 = 0.4 = 0 + 0.4 =>q -1 =0; 0.4 * 2 = 0.8 = 0 + 0.8 => q _-2 = 0 ; 0.8* 2 =1.6=1+0.6 =>q-з = 1; 0.6*2=1.2=1 +0.2 =>q_и =1 и т. д. Если десятичную дробь х = 0.2 считать точным числом, то в результате перевода в двоичную систему счисления получим периодическую дробь x = 0.(0011) (в скобках указан период дроби).

Любое число Х в позиционной системе счисления можно кратко записать путем перечисления всех К с указанием позиции точки. В современной ВТ широко используется 2-ная система счисления. Для изображения числа 0 и 1.