Спирина, М.С. Дискретная математика

Рис. 1.14. Движение по прямоугольной решетке Кортежи из нулей и единиц могут быть сообщениями, передаваемыми по некоторому каналу связи с помо­ щью импульсов, каждый из которых принимает одно из двух значений. Со­ общения могут характеризовать ре­ зультаты экспериментов: успех (1) или неудачу (0). Можно описать путь по некоторой прямоугольной решетке, определив, например, шаг направо через едини­ цу, а шаг наверх — через нуль. Тогда любой путь по такой прямо­ угольной решетке можно задать кортежем (рис. 1.14). Кортеж из нулей и единиц используется также для кодировки геометрического изображения. Такая двухцветная черно-белая пря­ моугольная сетка, состоящая из черных столбцов на белом фоне, может быть представлена в виде вектора. В вычислительной технике широко используется точечное рисование как растровый рисунок. Практический прикладной характер кортежей проявляется в использовании штриховых кодов {barcodes), которые широко при­ меняются в различных информационных системах для сообщения определенной информации о характеристике объекта. Например, штрих-кодом снабжены товары на базе или в магазине. Кассовый компьютер быстро считывает зашифрованную в них информацию. Каждый символ специальным образом однозначно кодируется с помощью полосок белого и черного цвета. Кортеж таких полосок однозначно переводится в вектор из 0 и 1. Декартово произведение. Пусть заданы множества Аь Л2, ..., Ап. Декартовым (прямым) произведением этих множеств называется множество Ai* А2 х ... х А„, состоящее из всех кортежей {аи а2, ..., ап) длины к, в которых ак е Ак, где 1 < к < п. Поскольку для задания кортежа важен порядок, то порядок множителей важен и в декар­ товом произведении. Например, декартовым произведением множеств А = {0,1} и В = {X, К Z) будет являться множество пар А х В = ((0; X), (0; У), (0; Z), (1; X), (1; Y), (1; Z)). Скобки для указания пар опускают там, где это не может привести к затруднениям: А х В ={0Х, 0 Y, 0 Z, IX, 1 Y, 1Z). Если множества А = {яь а2, ..., ак} и В ={ЬЬ Ъ2, ..., Ь т} конечны, то их декартово произведение может быть представ­ лено в общем виде таблицей из т столбцов и к строк. (аи Ьх) {аь Ь2) {аь Ьт) {а2, Ьд {а2, Ь2) {а2, Ьт) (ак, Ь\) {ак, Ь2) {ак, Ьт) 36