Избранные задачи прикладной дискретной геометрии (160,00 руб.)

Жуков, П.Г. Ключарев ИЗБРАННЫЕ ЗАДАЧИ ПРИКЛАДНОЙ ДИСКРЕТНОЙ ГЕОМЕТРИИ Рекомендовано Научно-методическим советом МГТУ им. <...> Избранные задачи прикладной дискретной геометрии : учеб. пособие / Д. А. Жуков, П.Г. Ключарев. <...> Рассмотрены алгебраические и комбинаторные свойства различных подмножеств булева куба, нашедшие применение в теории булевых функций, теории сложности, защите информации и теории кодирования. <...> Приведены задачи с подробными решениями и упражнения различной степени сложности, предназначенные как для первоначального, так и для углубленного освоения методов дискретной математики и комбинаторного анализа. <...> УДК 519.1(075.8) ББК 22.176 Учебное издание Жуков Дмитрий Александрович Ключарев Петр Георгиевич ИЗБРАННЫЕ ЗАДАЧИ ПРИКЛАДНОЙ ДИСКРЕТНОЙ ГЕОМЕТРИИ Редактор О.М. <...> Одним из наиболее замечательных объектов комбинаторики является многомерный булев куб. <...> Комбинаторные свойства булева куба находят многочисленные приложения при передаче и защите информации, в дискретной геометрии и теории алгоритмов, в теории графов и комбинаторном анализе, в теории булевых функций и параллельных вычислениях и с развитием этих дисциплин становятся неотъемлемой частью обязательных университетских курсов. <...> На многочисленных примерах разобраны метрические свойства подмножеств булева куба, рассмотрены код Хемминга и код Грея, доказана теорема Шпернера. <...> Функция ρ называется метрикой, или расстоянием, на множестве X, если она удовлетворяет трем свойствам, которые называются аксиомами метрики: Пусть X — произвольное множество и ρ :XЧX → R — неко2 |=2n при всех n ∈ N. + ρ(y, z). <...> Пара (X, ρ) называется в этом случае метрическим простран=0⇔x=y; 3) неравенство треугольника: ∀ x, y, z ∈X ρ(x, z) ≤ ρ(x, y)+ 1) симметричность: ∀ x, y ∈X ρ(x, y)= ρ(y,x); 2) неотрицательность: ∀ x, y ∈X ρ(x, y)≥0, причем ρ(x, y)= упорядоченных наборов нулей и единиц длины n, называется булевым кубом размерности n. <...> Его элементы — двоичные наборы — будем обозначать греческими <...>