Задания для самостоятельной работы

1. Выяснить, обладает ли код C свойством префикса:

1. C = {a, ba, bb, bbba};

2. C = {ab, bb, ba, aab};

3. C = {ac, c, bb, abc, bac, abb, abcb};

4. C = {a, ba, cab, acb}.

2. Выяснить, является ли код C с кодирующим алфавитом {0, 1, 2} однозначно декодируемым:

1. C = {01, 201, 112, 122, 0112};

2. C = {001, 021, 102, 201, 001121, 01012101};

3. C = {0, 01, 0010001001};

4. C = {20, 01202, 22, 2001, 2012010, 10201121, 1112};

5. C = {01, 011, 100, 2100, 101210, 001210};

6. C = {01, 011, 100, 2100, 10110, 00112};

7. C = {01, 12, 021, 0102, 10112};

8. C = {01, 12, 012, 111, 0102, 10112, 01112}.

3. Выяснить, является ли слово P в алфавите {0, 1, 2} кодом сообщения в кодировании, задаваемом схемой

Если да, то выяснить, является ли P кодом ровно одного сообщения:

1. P = 10120121012100;

2. P = 1012101201210012;

3. P = 0121001210201;

4. P = 120120121001210;

5. P = 1010122100;

6. P = 12101210012;

7. P = 101212101012;

8. P = 1010012100101.

4. Построить по методу Хэмминга кодовое слово для сообщения:

1. ã = 010;

2. ã = 011;

3. ã = 1001;

4. ã = 1101;

5. ã = 10101011;

6. ã = 111001111;

7. ã = 100010011;

8. ã = 01110111011.

5. По каналу связи передавалось кодовое слово, построенное по методу Хэмминга для сообщения . После передачи по каналу связи, искажающему слово не более чем в одном разряде, было получено слово . Восстановить исходное сообщение:

1) = 110;

2) = 101110;

3) = 011110;

4) = 1001011;

5) = 0101101;

6) = 1011101;

7) = 1100011;

8) = 11011100110;

9) = 1010101010100;

10) = 001011110111111.

ЛИТЕРАТУРА

Основная

1. Яблонский, С. В. Введение в дискретную математику / С. В. Яблонский. – М. : Наука, 1979, 1986 (2-е изд., перераб. и доп.), 2001 (3-е изд., стер.).

2. Яблонский, С. В. Методические разработки по курсу «Элементы дискретной математики» / С. В. Яблонский. – М. : Изд-во МГУ, 1971.

3. Яблонский, С. В. Дискретная математика и математические вопросы кибернетики / С. В. Яблонский, О. Б. Лупанов. – М. : Наука, 1974.

4. Гаврилов, Г. П. Сборник задач по дискретной математике / Г. П. Гаврилов, А. А. Сапоженко. – М. : Наука, 1977, 1991 (2-е изд., перераб. и доп.), 2004 (3-е изд., перераб.).

5. Алексеев, В. Б. Лекции по дискретной математике : учеб. пособие / В. Б. Алексеев. – М. : Изд. отдел фак. ВМиК МГУ им. М. В. Ломоносова, 2004. – 76 с.

6. Михеева, Е. А. Дискретная математика: учебно-методическое пособие для студентов I и II курсов факультета математики и информационных технологий / Е. А. Михеева. – Ульяновск : УлГУ, 2008.

7. Михеева, Е. А. Разделы дискретной математики : электронный учебный курс (2010 ОРЭИ УлГУ) ; № гос. регистрации обяз. экз. электр. изд. 0321101935. – Ульяновск : УлГУ, 2011.

8. Михеева, Е.А. Введение в дискретную математику: учебное пособие для студентов 1 курса факультета математики и информационных технологий / Е.А. Михеева. - Ч. 1. – Ульяновск : УлГУ, 2013.- 102 с.

9. Михеева, Е.А. Конспект лекций по курсу << Дискретная математика >> (первый семестр): электронный учебный курс. Номер гос. регистрации обяз. экз. электр. изд. – 0321304656. – Ульяновск : УлГУ, 2014.

Дополнительная

К разделу 6

1. Новиков, П.С. Элементы математической логики / П.С. Новиков. – 2-е изд. – М.: Наука, 1973.

2. Мендельсон, Э. Введение в математическую логику / Э. Мендельсон. – М.: Наука, 1976.

3. Игошин, В.И. Математическая логика и теория алгоритмов: Учеб. пособие для студ. Высш. учеб. заведений /В.И.Игошин.- М.: Издательский центр << Академия >>, 2004. – 448 с.

4. Игошин, В.И. Задачи и упражнения по математической логике и теории алгоритмов: учеб. пособие для студ. Высш. учеб. заведений / В.И. Игошин. – 3-е изд., стер. - М.: Изд. центр <<Академия >>, 2007. – 304 с.

К разделу 7

Кудрявцев, В.Б. Введение в теорию автоматов / В.Б. Кудрявцев, С.В. Алешин, А.С. Подколзин. – М.: Наука, 1986.

К разделу 8

1. Лавров, И.А. Задачи по теории множеств, математической логике и теории алгоритмов / И.А. Лавров, Л.Л. Максимова. – М.: Наука, 1975.

2. Мальцев, А.И. Алгоритмы и рекурсивные функции / А.И. Мальцев. – М.: Наука, 1965.

3. Роджерс, Х. Теория рекурсивных функций и эффективная вычислимость / Х. Роджерс. – М.: Мир, 1972.

4. Эббинхауз, Г.Д. Машины Тьюринга и рекурсивные функции / Г.Д. Эббинхауз, К. Якобо, Ф.К. Ман, Г.М. Хермес. – М.: Мир, 1972.

5. Ляпунов, А.А. О логических схемах программ / А.А. Ляпунов // Проблемы кибернетики. – Вып. 1. – М.: Физматгиз, 1958. – С. 46-74.

К разделу 9

1. Марков, А.А. Введение в теорию кодирования / А.А. Марков. – М.: Наука, 1982.

2. Смагин, А.А. Модели разбиений: монография / А.А.Смагин. – Ульяновск: УлГУ, 2013. – 207 с.

124