2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Задачки по дискретной математике
Сообщение13.01.2008, 09:53 
Аватара пользователя
Доброго времени суток.

Ситуация такая, что знакомый попросил помочь решить несколько задач по Дискретке. Сам я проходил её три года назад, поэтому что-то подзабыл, а чего-то и не знал.

В одной из задач нужно вычислить подгруппу, порожденную 8 в мультипликативной группе вычетов по модулю 97. Я мозгами пораскинул так:
группа вычетов по модулю 97 это {0,1,2,...,96}, тогда подгруппа вроде должна быть такая {1,8,64}, но вот только проблема - она вроде группой не является. Короче, я запутался.

 
 
 
 
Сообщение13.01.2008, 10:27 
Аватара пользователя
А где же, например, элемент 64х8-5х97=27

 
 
 
 
Сообщение13.01.2008, 10:57 
Аватара пользователя
Мультипликативная группа вычетов по модулю $97$ - это $\{1,2,3,\ldots,96\}$, то есть, без $0$. Искомая подгруппа - циклическая, образованная степенями порождающего элемента. В общем, вычисляйте степени $8^1\pmod{97}$, $8^2\pmod{97}$, $8^3\pmod{97}$, ..., пока не получится $1$.

Добавлено спустя 4 минуты:

Brukvalub писал(а):
А где же, например, элемент 64х8-5х96=32


Тут у Вас опечатка, наверное. Должно быть $64\times 8-5\times 97=27$.

 
 
 
 
Сообщение13.01.2008, 11:18 
Аватара пользователя
Someone писал(а):
Brukvalub писал(а):
А где же, например, элемент 64х8-5х96=32


Тут у Вас опечатка, наверное. Должно быть $64\times 8-5\times 97=27$.
Спасибо, я уже исправил. При выписывании примера в вопросе посмотрел на максимальный остаток и "на секундочку" принял его за модуль. :oops:

 
 
 
 
Сообщение13.01.2008, 11:58 
Аватара пользователя
Получается, что подгруппа у меня такая:
H = \{1, 8, 12, 18, 22, 27, 33, 47, 50, 64, 70, 75, 79, 85, 89, 96\}

Смежный класс gH, где g = 4:
gH = \{4, 6, 9, 11, 25, 32, 35, 48, 49, 62, 65, 72, 86, 88, 91, 93\}

Добавлено спустя 16 минут 54 секунды:

В продолжении задания нужно каждый элемент класса gH представить в виде двоичного числа длины 7. Получилось у меня вот что:
4 0000100

6 0000110

9 0001001

11 0001011

25 0011001

32 0100000

35 0100011

48 0110000

49 0110001

62 0111110

65 1000001

72 1001000

86 1010110

88 1011000

91 1011011

93 1011101
Теперь из этих векторов нужно построить диаграмму Хассе для отношения порядка. Я не совсем пойму, какие узлы должны соединяться.

Ещё нужно выписать три максимальные цепи и антицепи. В этом тоже проблема. Что такое антицепи?

 
 
 
 
Сообщение13.01.2008, 12:10 
Аватара пользователя
mastedm писал(а):
Что такое антицепи?
У Вас же есть Интернет: http://d1.hse.ru/data/137/315/1234/ltida2_1909.pdf

 
 
 
 
Сообщение13.01.2008, 12:27 
Аватара пользователя
mastedm писал(а):
Теперь из этих векторов нужно построить диаграмму Хассе для отношения порядка. Я не совсем пойму, какие узлы должны соединяться.


Вероятно, считается, что последовательность $\varepsilon_1\ldots\varepsilon_7$ длины $7$, составленная из нулей и единиц, меньше либо равна аналогичной последовательности $\delta_1\ldots\delta_7$ если $\varepsilon_i \leqslant \delta_i$ для всех $i \in [1,7]$. Соответственно на диаграмме Хассе последовательность $0000100$ будет минимальным элементом (меньше может быть только последовательность $0000000$, а её в нашем списке нет), прямо над ней будет последовательность $0000110$ и так далее...

P. S. Антицепь --- это подмножество, состоящее из попарно не сравнимых элементов. Нарисуете диаграмму, на ней цепи и антицепи видны будут.

P. P. S. Ну и муторные же задания задают Вашему другу! Зачем так много считать? Понимание идей можно продемонстрировать и на более простых примерах. Им потом самим не лень всё это проверять будет :?:

 
 
 
 
Сообщение13.01.2008, 16:55 
Аватара пользователя
Вот что получилось:
Изображение
Соответсвенно, цепь это путь по стрелочкам, а антицепь - путь против стрелочек?

 
 
 
 
Сообщение13.01.2008, 19:00 
Аватара пользователя
mastedm писал(а):
антицепь - путь против стрелочек?


Антицепь - это подмножество, в котором никакие два элемента не соединены стрелочкой. Например, $\{35,48,6,65,25,88,11\}$.

 
 
 
 
Сообщение16.01.2008, 23:29 
Аватара пользователя
Нужно было найти три максимальных цепи и три максимальных антицепи. Вот что у меня получилось.
Цепи:$\{32, 48, 49\}, \{9, 25, 93\}, \{72, 88, 91\}$
Антицепи:$$\{35, 49, 62, 86, 65, 25, 88, 11\}, \{35, 48, 6, 65, 25, 88, 11\}, \{35, 49, 62, 86, 93, 91\}$$

 
 
 
 
Сообщение20.01.2008, 12:07 
Аватара пользователя
Надо ещё отметить, что диаграмма Хассе немного неверно нарисована. На этих диаграммах стрелки не дублируют. В частности, если есть стрелка из 32 в 48, а также стрелка из 48 в 49, то не нужно рисовать стрелку из 32 в 49, поскольку из 32 в 49 уже можно пройти по стрелкам. На правильной диаграмме стрелок должно быть меньше.

 
 
 
 
Сообщение20.01.2008, 20:54 
Аватара пользователя
Исправленная версия:
Изображение

 
 
 [ Сообщений: 12 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group