Построение алгоритма реализации численного метода «быстрой сортировки»

Автор: Пользователь скрыл имя, 03 Октября 2011 в 16:41, курсовая работа

Описание работы

В своей курсовой работе я ставлю следующие задачи:

научиться представлять данные в ЦА;
изучить методы контроля работы ЦА и научиться строить код Хемминга;
изучить реализацию алгоритма численного метода «быстрой сортировки» и построить его блок-схему.

Содержание

Введение

Глава 1. Представление данных в цифровых автоматах (ЦА)

Глава 2. Методы контроля работы ЦА

Глава 3. Построение алгоритма реализации численного метода «быстрой сортировки»

Список используемых источников

Работа содержит 1 файл

курсавик.doc

— 302.00 Кб (Скачать)

      С недавнего времени был предложен  новый стандарт символьного кодирования  UNICODE. Шестнадцать разрядов позволяют обеспечить уникальные коды для 216=65536 различных символов – этого поля достаточно для размещения в одной таблице символов большинства языков планеты. 

      Задание. Используя таблицу Windows 12.51, закодировать свои: фамилию и имя (записанные на русском и английском языках). Вписать их в разрядную сетку.

Буква Десятиричный код Двоичный код   Буква Десятиричный  код Двоичный код
Ш 216 11011000   S 83 1010011
а 224 11100000   h 104 1101000
б 225 11100001   a 97 1100001
а 224 11100000   b 98 1100010
р 240 11110000   a 97 1100001
о 238 11101110   r 114 1110010
в 226 11100010   o 111 1101111
        v 118 1110110
П 207 11001111        
а 224 11100000   P 80 1010000
в 226 11100010   a 97 1100001
е 229 11100101   v 118 1110110
л 235 11101011   e 101 1100101
        l 108 1101100
 
 
    1. Выполнение  арифметических операций с целыми числами, представленными в машинных кодах

      Арифметические  операции с целыми числами, представленными  в машинных кодах, выполняются только операцией сложения. Т.е. операция разности, заменяется операцией сложения, операция произведения также заменяется операцией  сложения.

      Например, вычислить: А + B, A – B, –A – B. Пусть А=16010, B=4510.

      [A]доп = 0|000000010100000

      [–A]доп = 1|111111101100000

      [B]доп = 0|000000000101101

      [–B]доп = 1|111111111010011

  А + B     A – B     –A – B
+ 0|000000010100000   + 0|000000010100000   + 1|111111101100000
0|000000000101101   1|111111111010011   1|111111111010011
  0|000000011001101     0|000000001110011     1|111111100110011
 

      Задание. Произвести сложение чисел, представленных в машинных кодах: A+C; –A+C; A+(– C); –A+(– C).

      A = 30710 =1001100112  С = 9110 = 10110112

      [A]доп = 0|000000100110011

      [–A]доп = 1|111111011001101

      [C]доп = 0|000000001011011

      [–C]доп = 1|111111110100101

  А + C     –A + C
+ 0|000000100110011   + 1|111111011001101
0|000000001011011   0|000000001011011
  0|000000110001110     1|111111100101000
  А + (– C)     –A + (– C)
+ 0|000000100110011   + 1|111111011001101
1|111111110100101   1|111111110100101
  0|000000011011000     1|111111001110010
 
 
    1. Выполнение  логических операций с целыми числами, представленными  в машинных кодах

      Количество  логических операций может быть вычисленно по формуле , где n – число переменных. Из формулы видно, что для двух переменных a и b логических операций 16. Основные из них: логическое сложение, логическое умножение, логическое отрицание, сложение по модулю 2.

      Для выполнения логических операций, используют таблицы истинности:

Логическое  сложение

a Ú b

  Логическое  умножение

a & b

  Логическое

отрицание

 
 
Сложение  по модулю 2

a Å b

a \ b 1 0   a \ b 1 0   a
  a \ b 1 0
1 1 1   1 1 0   1 0   1 0 1
0 1 0   0 0 0   0 1   0 1 0
 
 

Задание:

а) произвести логическое сложение чисел А и  С:

Ú 0|000000100110011
0|000000001011011
  0|000000101111011
 

б) произвести логическое умножение чисел А  и С:

& 0|000000100110011
0|000000001011011
  0|000000000010011
 

в) произвести сложение чисел А и С по модулю 2.

Å 0|000000100110011
0|000000001011011
  0|000000101101000
 

г) произвести логический сдвиг: влево для чисел  А и –А, вправо для С и –С

A   –A  
0|000000100110011   1|111111011001101 Число
0|000001001100110   1|111110110011010 Результат сдвига влево
 
C   –C  
0|000000001011011   1|111111110100101 Число
0|000000000101101   0|111111111010010 Результат сдвига вправо
 

д) произвести логический циклический сдвиг: влево  для чисел А и –А, вправо для чисел С и –С

A   –A  
0|000000100110011   1|111111011001101 Число
0|000010011001100   1|111101100110100 Результат сдвига влево на 2 бита

 

C   –C  
0|000000001011011   1|111111110100101 Число
0|000000000010110   0|011111111101001 Результат сдвига вправо на 2 бита
 

e) произвести арифметический сдвиг: влево для чисел А и –А, вправо для чисел С и –С

A   –A  
0|000000100110011   1|111111011001101 Число
0|000001001100110   1|111110110011010 Результат сдвига влево
C   –C  
0|000000001011011   1|111111110100101 Число
0|000000000101101   1|011111111010010 Результат сдвига вправо
 

 

Глава 2.  Методы контроля работы ЦА 

    1. Корректирующая  способность кодов

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

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

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

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

      Кодовое расстояние (Хемингово расстояние) d для кодовых комбинаций A и B определяется как вес такой третьей комбинации, которая получается сложением исходных комбинаций по модулю 2. Вес кодовой комбинации V – это количество единиц содержащихся в кодовой комбинации.

Информация о работе Построение алгоритма реализации численного метода «быстрой сортировки»