Файл: Дискретная мат-ка_УП.pdf

81

Подстановки и перестановки  
 

В

таблице

подстановки

нижняя

строка

  (

значения

функции

) 

является

перестановкой

элементов

верхней

строки

  (

значения

ар

-

гументов

). 

Если

принять

соглашение

, 

что

элементы

верхней

строки

 (

аргументы

) 

всегда

располагаются

в

определенном

поряд

-

ке

  (

например

, 

по

возрастанию

), 

то

верхнюю

строку

можно

не

указывать

 – 

подстановка

определяется

одной

нижней

строкой

. 

Таким

образом

, 

подстановки

взаимно

однозначно

соответствуют

перестановкам

. 

Перестановку

 (

и

соответствующую

ей

подстановку

) 

элемен

-

тов

 1, 2, …, n 

будем

обозначать

  <a

1

,  a

2

, …, a

n

>, 

где

все

  a

i

 – 

раз

-

личные

числа

из

диапазона

 1.. n. 

 
Инверсии 
 

Если

в

перестановке

 f = <a

1

,  a

2

, …, a

n

> 

для

элементов

  a

i

и

  a

j

имеет

место

неравенство

 a

i

 > a

j

при

 i < j, 

то

пара

 (a

i

, a

j

) 

называется

инверсией. 

Обозначим

число

 I(f) – число инверсий 

в

перестановке

 f. 

Произвольную

подстановку

 f 

можно

представить

в

виде

су

-

перпозиции

 I(f) 

транспозиций

соседних

элементов

. 

Всякая

сорти

-

ровка

может

быть

выполнена

перестановкой

соседних

элементов

. 

 
Генерация перестановок 
 

На

множестве

перестановок

естественным

образом

можно

определить

упорядоченность

элементов

. 

А

именно

, 

говорят

, 

что

перестановка

  <a

1

,  a

2

, …, a

n

>  лексикографически 

предшествует

перестановке

 <b

1

, b

2

, …, b

n

>, 

если

∃ k ≤ n a

k

 < b

k

 & 

∀i < k a

i

 = b

i

. 

Аналогично

, 

говорят

, 

что

перестановка

  <a

1

,  a

2

, …, a

n

>  антилек-

сикографически 

предшествует

перестановке

 <b

1

, b

2

, …, b

n

>, 

если

∃ k ≤ n a

k

 > b

k

 & 

∀i > k a

i

 = b

i

. 

 
Биномиальные коэффициенты 
 

Число

сочетаний

  C(m,  n) – 

это

число

различных

  n-

элементарных

подмножеств

  m-

элементарного

множества

. 

Числа

82

C(m, n) 

встречаются

в

формулах

решения

многих

комбинаторных

задач

. 

Действительно

, 

рассмотрим

следующую

типовую

схему

рассуждений

при

решении

комбинаторной

задачи

. 

Пусть

нужно

определить

число

подмножеств

  m-

элементарного

множества

, 

удовлетворяющих

некоторому

условию

. 

Разобьем

задачу

на

под

-

задачи

: 

рассмотрим

отдельно

 1-

элементные

подмножества

,          

2-

элементные

и

т

.

д

., 

а

затем

сложим

полученные

результаты

. 

К

счастью

, 

числа

  C(m,  n) 

обладают

целым

рядом

свойств

. 

Элемен

-

тарные

тождества

: 

C(m, n) = C(m, m – n). 
C(m, n) = C(m – 1, n) + C(m – 1, n – 1). 
C(n, i) C(i, m) = C(n, m) C(n – m, i – m). 
 
Бином Ньютона 
 

Числа

сочетаний

  C(m,  n) 

называют

также

  биномиальными 

коэффициентами. 

Смысл

этого

названия

устанавливается

сле

-

дующей

теоремой

, 

известной

также

как

формула

 бинома Ньюто-

на. 

(

)

∑

=

−

=

+

m

b

n

m

n

m

y

x

n

m

C

y

x

0

)

,

(

. 

Свойства

: 

m

m

n

n

m

C

2

)

,

(

0

=

∑

=

; 

( )

∑

=

=

−

m

n

n

n

m

C

0

0

)

,

(

1

; 

∑

=

−

=

m

n

m

m

n

m

nC

0

1

2

)

,

(

; 

∑

=

−

=

+

k

i

i

k

n

C

i

m

C

k

n

m

C

0

)

,

(

)

,

(

)

,

(

. 

83

Треугольник Паскаля 
 

1 

    1  1     
     1  2  1      
   1  3  3  1    
 1  4  6  4  1  

.  .  .  .  .  . 

В

данном

равнобедренном

треугольнике

каждое

число

 (

кро

-

ме

единиц

на

боковых

сторонах

) 

является

суммой

двух

чисел

, 

стоящих

над

ним

. 

Число

сочетаний

 C(m, n) 

находится

в

 (m + 1)-

м

ряду

на

 (n + 1)-

м

месте

. 

84

8 

КОДИРОВАНИЕ

Вопросы

кодирования

издавна

играли

заметную

роль

в

ма

-

тематике

.  

 
Пример 
 
1. Десятичная позиционная система счисления – 

это

способ

кодирования

натуральных

чисел

. 

Римские

цифры

 – 

другой

способ

кодирования

натуральных

чисел

, 

причем

гораздо

более

нагляд

-

ный

и

естественный

: 

палец

 – I, 

пятерня

 – V, 

две

пятерни

 – X. 

Од

-

нако

при

этом

способе

кодирования

труднее

выполнять

арифме

-

тические

операции

над

большими

числами

, 

поэтому

он

был

вы

-

теснен

позиционной

десятичной

системой

. 

2. Декартовы координаты – 

способ

кодирования

геометри

-

ческих

объектов

числами

. 

Ранее

средства

кодирования

играли

вспомогательную

роль

и

не

рассматривались

как

отдельный

предмет

математического

изучения

, 

но

с

появлением

компьютеров

ситуация

радикально

изменилась

. 

Кодирование

буквально

пронизывает

информацион

-

ные

технологии

и

является

центральным

вопросом

при

решении

самых

разных

 (

практически

всех

) 

задач

программирования

: 

●

представление

данных

произвольной

природы

 (

например

, 

чисел

, 

текста

, 

графики

) 

в

памяти

компьютера

; 

●

защита

информации

от

несанкционированного

доступа

; 

●

обеспечение

помехоустойчивости

при

передаче

данных

по

каналам

связи

; 

●

сжатие

информации

в

базах

данных

. 

●

составление

текста

программы

. 

Не

ограничивая

общности

, 

задачу

кодирования

можно

сформулировать

следующим

образом

. 

Пусть

заданы

алфавиты

А = {a

i

,...,

а

n

}, В = {b

i

,...,b

m

} 

и

функция

 F: S 

→ В*, 

где

 S – 

некото

-

рое

множество

слов

в

алфавите

 A, S 

⊂ А*. 

Тогда

функция

 F 

назы

-

вается

  кодированием, 

элементы

множества

  S – сообщениями, 

а

элементы

β = F(α), 

α

∈

 S, 

β

∈

 В* – кодами (

соответствующих

со

-

85

общений

). 

Обратная

функция

 F

–1

 (

если

она

существует

!) 

называ

-

ется

 декодированием. 

Если

 |В| = т, 

то

 F 

называется

 т-ичным кодированием. 

Наи

-

более

распространенный

случай

  В  = {0,1} – двоичное 

кодирова

-

ние

. 

Именно

этот

случай

рассматривается

в

последующих

разде

-

лах

; 

слово

 «

двоичное

» 

опускается

. 

Типичная

задача

теории

кодирования

формулируется

сле

-

дующим

образом

: 

при

заданных

алфавитах

 А, В 

и

множестве

со

-

общений

 S 

найти

такое

кодирование

 F, 

которое

обладает

опреде

-

ленными

свойствами

 (

то

есть

удовлетворяет

заданным

ограниче

-

ниям

) 

и

оптимально

в

некотором

смысле

. 

Критерий

оптимально

-

сти

, 

как

правило

, 

связан

с

минимизацией

длин

кодов

. 

Свойства

, 

которые

требуются

от

кодирования

, 

бывают

самой

разнообразной

природы

: 

●

существование

декодирования

 – 

это

очень

естественное

свойство

, 

однако

даже

оно

требуется

не

всегда

. 

Например

, 

транс

-

ляция

программы

на

языке

высокого

уровня

в

машинные

коман

-

ды

 – 

это

кодирование

, 

для

которого

не

требуется

однозначного

декодирования

; 

●

помехоустойчивость

, 

или

исправление

ошибок

: 

функция

декодирования

  F

–1

обладает

таким

свойством

, 

что

  F

–1

  (

β

)  =                

=F

–1

 (

β

’), 

если

β

’ 

в

определенном

смысле

близко

к

β

; 

●

заданная

сложность

  (

или

простота

) 

кодирования

и

деко

-

дирования

. 

Например

, 

в

криптографии

изучаются

такие

способы

кодирования

, 

при

которых

имеется

просто

вычисляемая

функция

F, 

но

определение

функции

 F~

J

требует

очень

сложных

вычисле

-

ний

. 

Большое

значение

для

задач

кодирования

имеет

природа

множества

сообщений

  S. 

При

одних

и

тех

же

алфавитах

  А, B 

и

требуемых

свойствах

кодирования

 F 

оптимальные

решения

могут

кардинально

отличаться

для

разных

 S. 

Для

описания

множества

 S 

(

как

правило

, 

очень

большого

или

бесконечного

) 

применяются

различные

методы

: 

●

теоретико

-

множественное

описание

, 

например

 S = {

α

 | 

α

∈

 А* & |

а

| = n}; 

●

вероятностное

описание

, 

например

 S = А*, 

и

заданы

веро

-

ятности

 p

i

появления

букв

в

сообщении

, 

1

1

=

∑

=

n

i

i

p

;