Вопрос 10. Представление положительных и отрицательных целых чисел в эвм.

Числа в компьютере подразделяются на две группы: целые и вещественные. Целые числа бывают 2-х типов: со знаком и без знака.

Целые положительные числа (без знака), т.е.только положительное или нулевое значении):

М-? М=2^к-1 к – число разрядов

в этом классе чисел определены операции сложения и умножения.

Отрицательные целые числа.

Для представления отрицательных чисел используется так называемый ДОПОЛНИТЕЛЬНЫЙ КОД. Для перевода числа в дополнительный код необходимо проделать следующее:

1. в двоичном представлении числа все единицы заменить нулями и наоборот ("проинвертировать" все разряды числа);

2. к полученному результату прибавить единицу.

Применим сформулированный алгоритм к числу -5. Сначала представим модуль числа в двоичного виде, дополнив его нулями слева до необходимого количества разрядов. Пусть нас интересует стандартное 16-разрядное значение, тогда десятичное число 5 преобразуется к виду 0000 0000 0000 0101 . Произведем замену нулей и единиц; получим 1111 1111 1111 1010 . Остается прибавить единицу и ответ готов: 1111 1111 1111 1011.

Особое внимание обратим на старший разряд. Он называется знаковым и равен 0 для знака "плюс" и 1 для "минуса". При определении величины числа знаковый разряд не используется, так что числа со знаком могут иметь максимальное значение, состоящее из 15 двоичных разрядов.

Повторное применение рассмотренных выше правил преобразований в дополнительный код возвращает исходное число. Сложение исходного числа с его дополнительным кодом всегда дает нулевой результат, т.к. X + (-X) = 0. Обобщая это свойство, можно утверждать, что вместо вычитания всегда можно воспользоваться сложением уменьшаемого с дополнительным кодом вычитаемого.

Относительно скромное десятичное число 254 в двоичной системе имеет вид 1111 1110. Поэтому на практике чаще всего переходят к более компактной системе счисления с основанием, кратным двойке - к шестнадцатеричной системе счисления.

Little endion

11 Понятие о формальном языке и грамматике.

Всякий язык подразумевает 2 вида правил (синтаксис и семантика).

Синтаксис – совокупность формальных правил, по которым строятся правильные (допустимые) в данном языке конструкции.

Семантика - анализирует правильность выражения с точки зрения здравого смысла. Формальная грамматика – это наука, которая задаёт правила, по которым создаются те или иные конструкции.

Необходимо задать следующие компоненты:

1) множество терминальных символов ( все знаки, которые используются в языке). (пр. в Паскале: :=, <,>).

2) Множество вспомогательных нетерминальных символов.(<……..> всё, что находится внутри угловых скобок нетерминальные символы), (пр. <подлежащее> , <сказуемое>, <существительное>);

3) Начальный нетерминальный символ ( как правило определяющий самое общее понятие языка), (пр. в языке Паскаль Program).

4) Система подстановок.

Пример задачи: построить формальную грамматику, которая описывает все слова перевёртыши, состоящие из букв А и Б.

Решение:

1) а и б – терминальные символы;

2) < S > - слово (нетерминальный символ);

3) < S > → а (слово по определению есть «а»); < S > → б (слово по определению есть «б»); < S > → а < S > а (если взять слово-перевёртыш и добавить к нему сзади и спереди букву «а», то получим новое слово); < S > → б < S > б;

Вопрос №13. Теория автоматов .Примеры построения автоматов

Теория автоматов- годиться для создания реальных приборов и для реализации виртуальных программ. Автомат- устройство (группа устройств) которые без непосредственного участия человека выполняет процессы приёма, преобразования и передачи энергии, материалов или информации в соответствии с заложенной в него программой.

Характерные признаки автомата:

1) автомат характеризует множество допустимых входных сигналов (А)

2) также имеется множество выходных сигналов (V)

3) также существует множество внутренних состояний (Q)

Если кол-во A, V и Q конечно то такой автомат называеться конечным. - функция перехода, которая зависит от состояния автомата и от входных сигналов. (q, a)=q’- новое состояние.

- функция выходов;  (q, a)= V; Чтобы описать автомат необходимо задать все эти функции.

Виды автоматов:

1) информационные автоматы (информационное табло на вокзале, стадионе, светофор);

2) управляющие автоматы (автоматический станок, кодовый замок, управление лифтом);

3) вычислительные автоматы (микрокалькулятор, ЭВМ); Чаще всего реальный автомат трудно отнести к какой либо группе, скорее к их комбинаций.

Пр. кодовый замок. Пусть замок имеет 5 кнопок (А,Б,В,Г,Д). Для того чтобы описать автомат нужно задать множество входных сигналов. * - состояние входных сигналов, когда не одна из кнопок не нажата. Правильный набор – БД. При неправильном нажатии происходит сброс.

состояния	А	Б	В	Г	Д	*
q 1	q 1, 0	q 2, 0	q 1, 0	q 1, 0	q 1, 0	q 1, 0
q 2	q 1, 0	q 1, 0	q 1, 0	q 1, 0	q 1, 0	q 3, 0
q 3	q 1, 0	q 1, 0	q 1, 0	q 1, 0	q 4, 0	q 3, 0
q 4	q 1, 0	q 1, 0	q 1, 0	q 1, 0	q 4, 1	q 1, 0

А=(А,Б,В,Г,*) – не одна из кнопок не нажата. V=(0,1); q – состояние, 0,1 – выходной сигнал; q 1 – исходное состояние; q 2 – кнопка нажата Б; q 3 – кнопка Б отпущена;

С помощью графов:

Задачи, которые можно решать в рамках теории автоматов:

1) возможно то или иное устройство представить в виде теории автоматов?

2) как это сделать?

3) проблема эквивалентности автоматов;

4) задача тестирования автоматов;

5) задача связанная с композицией автоматов и декомпозицией автоматов (объединение простых в сложный и наоборот). Наиболее распространены двоичные автоматы.

Пр. имеется цепочка из 0 и 1. Построит автомат, который распознаёт цепочки, в которых находятся хотя бы одна пара 01

	0	1
А	А	В	 0
В	А	С	 0
С	С	С	 1