Дискретная математика
2
Автор: Борис Веретенников, Вероника Белоусова, Александр Веретенников
Форматы: PDF
Издательство: Издательство Уральского университета
Год: 2017
Место издания: Екатеринбург
ISBN: 978-5-7996-2165-0 (ч. II). – ISBN 978-5-7996-1195-8
Страниц: 87
Артикул: 99571
Краткая аннотация книги "Дискретная математика"
Данное учебное пособие является продолжением учебного пособия «Дискретная математика», Ч. I (авторы: Б. М. Веретенников, В. И. Белоусова). Работа включает в себя следующие разделы дискретной математики: многочлены над конечными полями, коды, исправляющие ошибки и элементы теории графов. Предлагаются упражнения для самостоятельного решения. Пособие предназначено для студентов инженерных направлений и специальностей ИРИТ–РтФ УрФУ.
Содержание книги "Дискретная математика"
Глава I. Многочлены над конечными полями
§ 1. Обзор общей теории многочленов
§ 2. Теория сравнений для многочленов и примеры построения полей небольшого составного порядка
§ 3. Основные теоремы о многочленах над конечными полями
Глава II. Коды, исправляющие ошибки
§ 1. Линейные коды
1.2. Вычисление проверочной матрицы с помощью систематической порождающей матрицы
1.3. Дуальные коды
1.4. Примеры специальных кодов
Упражнения для самостоятельной подготовки
§ 2. Линейные коды, исправляющие ошибки
2.1. Декодирование линейных кодов с помощью смежных классов
2.2. Декодирование с помощью синдромов
2.3. Код Хэмминга и расширенный код Хэмминга
2.5. Циклические коды
2.6. Нахождение систематической порождающей матрицы циклического кода
2.7. Специальный вид проверочной матрицы циклического кода
2.8. Коды, порожденные элементами из расширения основного поля
2.9. Коды БЧХ
2.10. Примеры кодов БЧХ
2.11. Декодирование кодов БЧХ
Глава III. Элементы теории графов
§ 1. Основные понятия теории графов
1.1. Матрицы графов
§ 2. Алгоритмы на графах
2.1. Поиск в глубину
2.2. Поиск в ширину
2.3. Минимальный остов графа
2.4. Наибольшее паросочетание в двудольном графе
Список литературы
Все отзывы о книге Дискретная математика
Отрывок из книги Дискретная математика
24Глава II. Коды, исправляющие ошибки В дальнейшем коды над F2 и F3 будем называть бинарными и тернарными соответственно.Определение. Проверочной матрицей линейного ()n,k-кода C над Fq при всех k n< называется матрица H размера (),n kn-ґ такая, что при x FqnО условие x СО равносильно условию Hxt=0, где xt — столбец, полученный транспонированием вектора x.Теорема 1.1. Если H — проверочная матрица ()n,k-кода C, то rank H n k= -.2. Пусть M — матрица размера (),n kn-ґ rank M n k= - и G — порождающая матрица ()n,k-кода C. Тогда M — проверочная матрица в том и только том случае, когда MGOt=, где О — ну-левая матрица.Доказательство. 1. По условию C — подпространство вектор-ных решений однородной линейной системы уравнений (ОЛСУ) с матрицей H. Тогда по известной теореме линейной алгебры kC nH== -dim,rank откуда rank.H n k= -2. Ввиду того, что строки G образуют базис C, заключаем, что условие MGOt= равносильно условию " О=c Mct0. (1)С другой стороны, пространство решений ОЛСУ с матрицей М имеет размерность n n kkC( )dim .= = Поэтому условие (1) равносильно тому, что это пространство совпадает с C, что рав-носильно, в свою очередь, тому, что М — проверочная матри-ца кода С.1.2. Вычисление проверочной матрицы с помощью систематической порождающей матрицыСделаем сначала ряд определений и замечаний.Определение. Порождающая матрица ()n,k-кода называется систематической, если она имеет вид E Bk|,() где Ek — единич-
С книгой "Дискретная математика" читают
Посмотреть
Посмотреть
Посмотреть
Посмотреть
Посмотреть
Посмотреть
Посмотреть
Посмотреть
Посмотреть
Посмотреть
Бестселлеры нон-фикшн
Посмотреть
Посмотреть
Посмотреть
Посмотреть
Посмотреть
Посмотреть
Посмотреть
Посмотреть
Посмотреть
Посмотреть
Посмотреть
Посмотреть
Посмотреть
Новинки книги нон-фикшн
Посмотреть
Посмотреть
Посмотреть
Посмотреть
Посмотреть
Посмотреть
Посмотреть
Посмотреть
Посмотреть
Посмотреть
Посмотреть
Посмотреть
Посмотреть
Веретенников Б. М. другие книги автора
и мы свяжемся с вами в течение 15 минут
за оставленную заявку