Дискретная математика, машина Тьюринга, нормальный алгоритм Маркова...

[~deep~spell~]

Здравствуйте! Неоднократно помогала в сообществе, теперь самой очень нужна помощь. Я просто не успеваю это сделать и вообще вникнуть в материал, а сдать надо в четверг.
Возможно, это по проганью, но нам задали по дискретке. Пожалуйста, помогите...

Заранее благодарю..

ЗЫ  Trotil смог найти информацию про негадвоичную систему счисления( и очень подробно объяснил мне как умножать число на 2. Теперь только осталось сделать это машиной Тьюринга и алгоритмом Маркова. Пожалуйста, помогите те, кто это помнят/знают!

Умножить целое число, записанное в негадвоичной системе счисления, на 2

@темы: Дискретная математика

Comments

[Trotil]

Умножить с помощью машины Тьюринга?

И что такое "негадвоичная" система счисления?

[~deep~spell~]

да... хотя, возможно, это на алгоритм Маркова (я просто пропустила семинар и совсем не знаю что это такое). Но вроде решить с помощью машины Тьюринга.
А что это за система счисления я не знаю, но задача сформулирована именно так...
Блин, это даже гугл не находит(ушла листать справочники)

[Trotil]

И что такое "негадвоичная" система счисления?

Нашел

en.wikipedia.org/wiki/Negative_base

www.indopedia.org/Negabinary.html

Вот так она интересно работает

[Trotil]

Надо теперь разобраться, как там работает умножение...

[~deep~spell~]

Trotil, какая штука интересная!
*пытается понять, по какому принципу оно вообще строится*
спасибо тебе большое=)

[Trotil]

Сначала разберем, как оно вообще устроено:

a0 - 2*a1 + 4*a2 - 8*a3 +16*a4 - 32*a5...

Рассмотрим в лексикографическом порядке: возъмем 4 бита: - 8*a3 + 4*a2 - 2*a1 + a0

биты число
3210 x
--------
0000 0
0001 1
0010 -2
0011 -1
0100 4
0101 5
0110 2
0111 3
1000 -8
1001 -7
1010 -10
1011 -9
1100 -4
1101 -3
1110 -6
1111 -5

Например 0110 это - 8*a3 + 4*a2 - 2*a1 + a0 = - 8*0 + 4*1 - 2*1 + 0 = 4 -2 = 2

1 битом можно задать диапазон {0,1}
Двумя - {-2,1}
Тремя - {-2,5}
Четырьмя {-10, 5}

(интересно получается - с добавлением бита промежуток разрастается то в одну сторону, то в другую, причем на 2^n значений )
Даже не выписывая значений можно догадаться, что пятью битами можно задать числа из промежутка {-10, 21}
21 = 10101 = 16 + 4 + 1.
-10 = 01010 = -8 - 2 = -10

Если упорядочивать в десятичной системе счисления, как это будет выглядеть - можно увидеть по ссылке.

Перехожу к операциям.

[Trotil]

Сложение.



При сложении трех чисел в разряде (двух бит и переноса) может получиться -1, 0, 1, 2, 3.
(-2 из таблицы может получится только при вычитании - оно нам не нужно)

3 = 1+1+1
2 = 1+0+1 = 0+1+1 и т.д.

Первое число - перенос, бит первого числа, бит второго числа.

В примере складывается 85+52=137



Первая строчка - переносы
Вторая строчка - 1010101 = 85
Третья строчка - 1110100 = 52
------------------------------------------
Четвертая строчка - сумма трех строчек
Пятая строчка - бит результата (по таблице 1)
Шестая строчка - переносы (по таблице 1)

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

Последовательно действия (от младшего к старшему):
0+1+0 = 1; бит результата - 1, перенос - 0,
0+0+0 = 0; бит результата - 0, перенос - 0,
0+1+1 = 2 бит результата - 0, перенос - (-1)
-1+0+0 = -1 бит результата - 1, перенос - 1
... и.т.д.

Пятая строчка - результат в негапозиционной системе счисления.

110011001 (1-8+16-128+256 = 137).

Перехожу к умножению. Нам нужно разобрать умножение на 110 и реализовать его на машине Тьюринга.

[Trotil]

Умножение.



Используя технику сложения разобраться в ней очень легко.

Умножение на "1" - переписываем целиком первый множитель
Умножение на "0" - пустая строка (сдвиг разряда все равно происходит)

Дальше все это суммируется в правилам, расписанным выше. Думаю, на картинке доходчиво указано все. Если будут вопросы - поясню.

Теперь нужно по этим правилам умножить на 110.

Первая строчка - неизвестный множитель
Вторая строчка - 110.
---------------------------------------------
Третья - нули
Четвертая - неизвестный множитель со сдвигом в один разряд
Пятая - неизвестный множитель со сдвигом в два разряда.

Итого: умножение на 110: это сумма в негадвоичной системе счисления двух чисел: неизвестного множителя, и неизвестного множителя с приписанным нулем справа. После того, как сумму подсчитали, справа приписать нуль.


Пример: 18 = 10110 = 16+4-2 умножим на два. Должно получиться 36 = 1100100= 64-32+4

1 0 1 1 0 0
0 1 0 1 1 0
--------
1 1 0 2 1 0
1 1 0 0 1 0
0 0 0-1 0 0

Приписываем ноль: 1100100

Получилось то, что нужно. Ура

Пример 2: Умножим 10111=19=16+4-2+1 на два.
0 1 0 1 1 1
1 0 1 1 1 0
-------------
1 1 1 1 2 1
1 1 1 1 0 1
0 0 0 0-1 0

Приписываем ноль 1111010=64-32+16-8-2=38 (опять правильно получилось )

Осталось эту сумму реализовать на машине Тьюринга.

[Trotil]

Пока только ссылки:
Описание машины Тьюринга
Еще немного про машину Тьюринга

Унарное сложение на машине Тьюринга

PDF с примером на сложение двоичных чисел

Буду рад, если найдется тот, кто хорошо знает эту тему, а то я немного подзабыл конечные автоматы.

[~deep~spell~]

ты монстр!!!
Такую работу для меня сделал! Спасибо!) Разобралась почти во всем, только немного не понятно как строится первая и последние строчки при сложении... Объясни еще раз, если не сложно...

Теперь мне осталось только с машинами разобраться, благо их я немного вспомнила...
По ходу оказалось, что надо решить не только с помощью машины Тьюринга, но и алгоритмом Маркова... Так что меняю задачу...
Ты алгоритм Маркова тоже не помнишь?)

[Гость]

Тротил,слушай,если это не очень нагло, иесли ты этим заинтересовался,то ты не знаешь как из двоичной перевести в негадвоичную,помоги пожалуйста?

[Trotil]

Разобралась почти во всем, только немного не понятно как строится первая и последние строчки при сложении... Объясни еще раз, если не сложно...

Это переносы. Это как сложить 4 + 8 будет равно 2, и в переносе "1" для следующего разряда.



Строятся согласно этой таблице.

1) Получаем сумму трех чисел (number) - переноса, и двух бит слагаемых
2) По этому числу записываем бит результата (0,1) в пятую строчку и перенос (carry) в шестую.
3) Этот перенос из пункта 2 записываем в первую строчку (но со сдвигом на один бит влево)
4) Полученный перенос на шаге3 и два новых бита суммируем... (см. пункт 1)

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

[Trotil]

ты монстр!!!

Да... А особенно по утрам, когда проснусь Людей своим видом пугаю

Тротил,слушай,если это не очень нагло, иесли ты этим заинтересовался,то ты не знаешь каты монстр!!!к из двоичной перевести в негадвоичную,помоги пожалуйста?

Не знаю Я сам о негадвочной системе только вчера узнал

Ты алгоритм Маркова тоже не помнишь?)

А это мы вообще не проходили

[~deep~spell~]

Trotil, 1) Получаем сумму трех чисел (number) - переноса, и двух бит слагаемых
2) По этому числу записываем бит результата (0,1) в пятую строчку и перенос (carry) в шестую.
3) Этот перенос из пункта 2 записываем в первую строчку (но со сдвигом на один бит влево)
4) Полученный перенос на шаге3 и два новых бита суммируем... (см. пункт 1)

Вот мне именно здесь непонятно. Получается, шестая строчка зависит от первых трех, а первая от шестой?

Жалко, что Маркова не знаешь.)

Еще раз спасибо!!! Такой трактат написал=)

[Trotil]

Первая - это шестая и есть, только сдвинутая на бит влево. Короче, посмотри на последнюю и четвертую снизу строчки при умножении.

Когда пишешь сложение, записываешь вначале две строчки (вторую и третью), а не три. Первая дописывается по ходу решения примера (также, как и нижние три)

[Гость]

Ребят, очень прошу мне помочь !задали сложить 2 двоичных числа на машине Тьюринга.Я разобралась в принципе работы, построила пятерки, а в вот как диаграмму нарисовать и как с лентой связать- не знаю(((((((((((((((((((рисунок бы посмотреть..Помогите, пожалуйста....
1. (0,'0','0',0,R);
2. (0,'1','1',0,R);
3. (0,' ',' ',1,R);
4. (1,'0','0',1,R);
5. (1,'1','1',1,R);
6. (1,' ',' ',2,L);
7. (2,'1','0',3,L);
8. (2,'0','1',2,L);
9. (2,' ',' ',5,R);
10. (3,'1','1',3,L);
11. (3,'0','0',3,L);
12. (3,' ',' ',4,L);
13. (4,'1','0',4,L);
14. (4,'0','1',0,R);
15. (4,' ',' ',0,R);
16. (5,'1',' ',5,R);
17. (5,' ',' ',5,H)

[Robot]

Обращение к Гостям
Вступите в сообщество, сделайте свою запись

[Гость]

Ребята, как с помощью машины Тьюринга сложить два числа, к примеру в восьмеричной системе счисления?

[~deep~spell~]

Гость ну программку надо написать...

Знаешь принципы работы машины Тьюринга ?
Составь алгоритм и напиши программку.

А вообще, смотри пост Робот

[Robot]

А именно
Обращение к Гостям
Вступите в сообщество, сделайте свою запись