Дискретная математика:
логика, группы, графы, фракталы

Акимов О.Е.

Практические задания по группам

1. Типовой расчет. Произвести полный морфологический анализ группы 32-го порядка (конкретный вид указывается преподавателем), найти все ее подгруппы и построить на них решетку.

2. В соответствии с вашим вариантом по таблице умножения элементов группы 8 × 8 (табл. 2.96) построить группу регулярных подстановок, автоморфную ей группу, изоморфную группу подстановок меньшей размерности, а также привести примеры эндоморфизма и естественного гомоморфизма. Определить образующие элементы группы, их четность, декремент и число инверсий. Найти систему базисных транспозиций. Произвести разбиение на классы сопряженности и смежности по всем подгруппам, составить таблицу умножения классов. Отыскать все собственные подгруппы, установить их индекс и инвариантность. Наконец, указать центр заданной группы.

Таблица 2.96

3. Найти НОД [a(x), b(x)], НОК [a(x), b(x)] для произвольно выбранных многочленов a(x), b(x) в поле GF(p) не ниже пятой степени, например: 

a(x) = x⁷ + x⁵ + x³ + 1, b(x) = x⁵ + x⁴ + x³ + x.

4. Составить полную таблицу неприводимых многочленов для GF(pⁿ) с заданным порождающим многочленом g(x) (табл. 2.97).

Таблица 2.97

5. Исследовать код (n = 15), заданный порождающим (для g(x) код 1) или проверочным (для h(x) код 0) многочленом (табл. 2.98), на помехозащищенность. С этой целью: найти порождающую и проверочную матрицы циклического кода; построить соответствующие им систематические матрицы методом остаточного многочлена; свести циклические матрицы к систематическим путем линейной комбинации строк или столбцов; составить проверочное соотношение и определить коды ошибок; на трех информационных словах проанализировать помехозащищенность кода при одной ошибке и одновременном наложении двух (трех) ошибок.

Таблица 2.98

6. В табл. 2.99 приведены искаженные и истинные кодовые слова. Необходимо для своего варианта искаженного слова найти наиболее подходящее истинное слово.

Таблица 2.99

7. В табл. 2.100 приведены искаженные кодовые слова, записанные с помощью квадратной матрицы. Исправить в кодовом слове своего варианта ошибочный символ.

Таблица 2.100