Форум программистов, компьютерный форум, киберфорум
Наши страницы
Мат. логика и множества
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/4: Рейтинг темы: голосов - 4, средняя оценка - 5.00
Nicholas Essen
3 / 3 / 0
Регистрация: 02.04.2011
Сообщений: 38
#1

Формальное определение алгоритма поиска НОД через теорию множеств

23.08.2012, 15:42. Просмотров 656. Ответов 1
Метки нет (Все метки)

Здравствуйте.По возможности буду краток.В книге Д.Кнута дается определение алгоритма Евклида по нахождению НОД,с помощью теории множеств.При чтении у меня возникло недопонимание некоторых частей
Метод вычислений - четверка вида(Q,I,O,f).
Q - содержит в себе множества I и O.
f - функция отображения множества в себя.Причем f(q)=q для всех q из множества O.

Пусть элементами Q будут:
все величины(n)
все упорядоченные пары (m,n)
все упорядоченные четверки (m,n,r,1),(m,n,r,2),(m,n,p,3)(Почему в последней четверке после n следует p?)

m,n,p - целые положительные числа
r - неотрицательное целое число
I - подмножество всех пар (m,n)
O - подмножество всех величин (n)

Определение функции f:

f((m,n)) = (m,n,0,1); f((n))=(n);

f((m,n,r,1))=(m,n,остаток от деления m на n,2)

f((m,n,r,2))=(n),если r=0, в противном случае (m,n,r,3)

(Почему в 2 верхних строках число,следующее за r,увеличивается?)

f((m,n,p,3))=(n,p,p,1)(Почему в левой части этого равенства у за n идет p,а в правой присутствуют 2 символа p ?)

Заранее спасибо.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.08.2012, 15:42
Ответы с готовыми решениями:

Задачка на теорию множеств
Это пример задачи подобного типа, который я никак не могу понять каким образом...

Разбор задачи на теорию множеств
Здраствуйте. Разбираю задачу по дискретной математике на доказательство, но...

Теория множеств. определение множества в явном виде(списком)
Условие задачи. пусть Х-множество {1,2}, а Y-множество{х: х=y+z; y,z...

Формальное решение логической задачи
Всем привет. Есть такая задача: 1) "Если Иванов не участвовал или...

Написать теорию для алгоритма нахождения пути в лабиринте
кто может помочь мне написать на самую скушную тему нахожденния пути в...

1
Mysterious Light
Эксперт по математике/физике
3937 / 1916 / 382
Регистрация: 19.07.2009
Сообщений: 2,928
Записей в блоге: 21
23.08.2012, 20:31 #2
Скорее, не «с помощью теории множеств», а «в терминах теории множеств» (из книги). Просто эта теория очень распространена, вот де-факто она и считается самой примитивной из всех.
Всё становится очевидным, если аккуратно нарисовать блок-схему, ну или расписать все переходы в виде диаграммки.
Ещё: реально там не четверки, а "меченные" тройки. Тройка, потому что там три значимых элемента, а меченная, потому что есть пять разных типов состояний: число, пара и три тройки. Число и пару от тройки отличить можно, а чтоб тройки между собой различать, мы их помечаем циферкой в конце.
Пять типов состояний требуют пять переходов. Правда, один тривиальных, а один условный.

Собственно, сам алгоритм:
1. f(m,n)=f(m,n,0,1) -- читаем два числа, переходим ко второй инструкции
2. f((m,n,r,1))=(m,n,остаток от деления m на n,2) -- r:=m%n, переходим к третей инструкции
3. f((m,n,r,2))=(n), если r=0 -- перейти к последней инструкции с параметром n
4. f((m,n,r,2))=(m,n,r,3), в противном случае -- перейти к пятой инструкции, параметры те же
5. f((m,n,p,3))=(n,p,p,1) -- m:=n; n:=p, перейти ко второму шагу
6. f((n))=(n) -- завершить работу алгоритма

p и r означают примерно одно и то же. Кнут только делает акцент, что в 5 шаге третий параметр не может равнятся 0 в силу условия 4-го шага.
2
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.08.2012, 20:31

Есть ли формальное определение "обратной операции"
Группа - множество с наделенной обратимой ассоциативной операцией. Верно? Есть...

Реализуйте на практике 2 алгоритма поиска и 2 алгоритма сортировки. Результаты сравните
Всем привет! Я в С++ абсолютный чайнег, поэтому за дебильные вопросы сапогами...

Найти НОД трёх чисел. Примечание. НОД(a,b,c)=НОД(НОД(a,b),c).
Кто может решить данную задачку (составить программу с помощью циклов))))...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru