1. Smysl kontrolních číslic

Způsob používání kontrolní číslice v ISBN a pak letošní změna je snad učebnicovým příkladem pro vysvětlení tohoto principu. Kontrolní číslice označovaná někdy také zkratkou CDV z anglického Check Digit Variable se používá pro zabezpečení číselných řetězců proti nejjednodušším náhodně vzniklým chybám, jež původně vznikaly především při ručním vkládání (typování) čísel.

Kontrolní číslice se začala využívat především v těch případech, kdy by jediná chybně natypovaná cifra znamenala zcela jinou existující položku. Jako nejnázornější příklad se uvádějí čísla bankovních účtů. Stejným příkladem jsou čísla ISBN případně ISSN, která také bývají přidělována (v nějakém rozsahu) těsně za sebou. A kontrolní číslice je v nejčastějším případě další cifra, která způsobuje, že řada postupně přidělovaných čísel je nespojitá, je v ní mnoho mezer. Ony mezery jsou konstruovány tak, aby při chybném natypovaní pouze jedné jediné cifry původně správného čísla jsme se vždy "trefili" do nepřípustného intervalu mezer. Kontrolní mechanismus nás pak okamžitě upozorní na nesprávně vkládaný číselný řetězec.

Druhou nejjednodušší chybou při ručním typování čísel (hlavně profesionálních pracovníků) bývá vzájemné prohození dvou sousedních cifer. Jest patrné, že první typ chyby - nesprávné vložení jedné jediné cifry - je aktuální i při elektronickém čtení nebo přenosu číselných řetězců, na rozdíl od zaměnění dvou sousedních cifer, jež bývalo hlavně spojeno s ručním typováním (převážně na numerické klávesnici). Dobře konstruované CDV by mělo první nebo druhý typ nejjednodušší chyby zachytit. Je třeba zdůraznit, že se ale nedají vždy zachytit už dvě jednoduché chyby, které by se objevily současně.

Princip výpočtu a ověřování kontrolních číslic je postaven na (algebraických) okruzích zbytkových tříd, které se i přes svou jednoduchost (na rozdíl od daleko složitějších derivací a integrálů) ani na vysokých školách běžně v matematických nebo informatických předmětech neprobírají. Přitom podstata je velmi jednoduchá. Mnozí si toho všimli již na základní škole (kde snad jedině je tato problematika v osnovách), že totiž zbytky při dělení nějakým číslem se dají sčítat i násobit, pokud z každého součtu nebo součinu znovu vezmeme zbytek. A jedná-li se o zbytky prvočísla, můžeme ve zbytcích i dělit, a to všemi nenulovými zbytky. Potom dokonce pracujeme v (algebraickém) tělese zbytkových tříd.

2. Princip kontroly

Obecný princip kontroly CDV spočívá v tom, že jsou stanoveny tzv. váhy, kterými se jednotlivé cifry kontrolovaného čísla vynásobí, pak se tyto násobky sečtou a vydělí stanoveným číslem, tak zvaným modulem. Výsledný zbytek je třetí stanovená hodnota, která určuje úspěšně provedenou kontrolu CDV. Poznamenejme, že často se stanoví hodnota zbytku jako nulová, ale zcela obecně tomu tak být nemusí.

Symbolicky tedy uvažujme kontrolu čísel nejvýše n-ciferných. Musí být tedy stanoveny váhy v₁, v₂, ..., v_n, potom zbytek, jenž označíme z, a samozřejmě modul značený p. Pro n-ciferné číslo x₁x₂ . . . x_n je splněna kontrola CDV, právě když platí: v₁.x₁ + v₂.x₂ + . . . + v_n.x_n =^(p) z

Pro přesnost je třeba doplnit, že trochu nezvyklý symbol rovnosti =^(p) určuje rovnost zbytků při dělení (modulem) p. Tedy přesně to, co se v matematice obvykle připisuje k rovnicím vpravo na konec řádku jako (mod p).

Podstatu funkce kontrolních číslic asi nejlépe ilustruje následující úvaha (nebo výpočet) týkající se dvou čísel, která by obě splňovala kontrolu CDV, ale lišila by se jen v jedné jediné cifře, tedy například číslo x₁ . . x_k . . x_n a číslo x₁ . . y_k . . x_n lišící se navzájem jen v k-té cifře. Pokud obě čísla splňují kontrolu CDV, musí platit vztahy:
v₁.x₁ + . . + v_k.x_k + . . + v_n.x_n =^(p) z
v₁.x₁ + . . + v_k.y_k + . . + v_n.x_n =^(p) z
Hned je vidět, že jediný rozdíl způsobí pouze zbytek (podle modulu p) pro k-tý součin. Symbolicky provedeno, obě rovnice odečteme (což je v okruhu zbytkových tříd povoleno) a dostaneme (po vytknutí váhy v_k):
v_k.(x_k-y_k) =^(p) 0

Poslední vztah tedy znamená, že součin váhy a rozdílu dvou cifer je dělitelný modulem p. Pouze za těchto okolností mohou existovat dvě čísla splňující kontrolu CDV a lišící se přitom v jedné jediné cifře. Pokud tedy váhy a modul zvolíme tak šikovně, že ona situace nebude moci nikdy nastat, kromě případu shodných cifer x_k=y_k, máme zabezpečenu kontrolu zabraňující náhodné změně jedné cifry.

Nejjednodušším řešením bude případ, že (modul) p je prvočíslo. (Tedy číslo, které je dělitelné pouze jedničkou a sebou samým.) Potom je součin dvou čísel dělitelný beze zbytku prvočíslem p pouze v případě, že p dělí jednoho nebo druhého činitele (respektive i oba). Nebo pro náš případ opačně, pokud prvočíslo p nedělí (beze zbytku) žádného z činitelů, potom nebude dělit ani jejich součin. Tedy nebude-li p dělit žádnou z vah (v_k) ani žádný z možných rozdílů dvou cifer (x_k-y_k) , nalezli jsme vhodné řešení.

Přitom rozdíl dvou (libovolných) cifer se může rovnat jakémukoliv číslu, ale (v absolutní hodnotě) menšímu než je největší možná cifra. Předpokládáme-li logicky použití cifer 1 až 9, nemůžeme bez zásadních problémů používat jakýkoliv (a to i neprvočíselný modul) menší než 10. Nejbližším možným prvočíslem je tak 11. A pro každou váhu se pak podmínka nesoudělnosti s 11 zredukuje na požadavek, aby byla větší než 0 a menší než 11.

3. Kontrola starého ISBN

Přesně tak vypadala původní kontrola ISBN. Váhy jsou všechna čísla mezi 10 a 1 , zbytek z=0 a modul p=11. Pro úplnost dodejme, že stejně je zkonstruována používaná kontrola ISSN, kde ovšem se využívá jen osm vah, a to hodnoty od 8 do 1.

Nevýhodou použití modulu p=11 je existence nenulového zbytku 10. Pokud chceme v určitém rozsahu využívat spojitou část číselné řady, může se nám při dopočtení kontrolní číslice (aby pak vzniklé číslo splňovalo kontrolu CDV) vyskytnout situace, kdy pro onu číslici vychází právě hodnota 10. To se v zásadě řeší dvěma způsoby. Buď se připustí desátá možná cifra pro zbytek 10, a to jako X (všem známé z ISSN a původního ISBN). Anebo druhý možný přístup, čísla, u kterých by ono X vycházelo jako kontrolní číslice, se vůbec nepřidělí, vynechávají se. Typickým příkladem je přidělování čísel bankovních účtů, kde stejně z původně spojitého základu vznikají při rušení účtů četné mezery. Výhodou druhého řešení je, že všechny znaky v číslech účtů jsou numerické.

Minulé ISBN tedy využívalo první z variant, kde X mohlo být jen v kontrolní číslici na posledním místě. Přitom je potřeba zdůraznit, že odvození podmínek pro kontrolu CDV pouze využívá (těleso) zbytkových tříd modulo prvočíslo. Proto změna jedné jediné cifry se týká i případných hodnot X v celém rozsahu řetězce. Tedy konkrétně je zabezpečeno proti (jediné) náhodné změně i případné X použité na poslední pozici.

Konec konců i samotné požití váhy 10 je v tomto případě dáno stejnou skutečností. Váha 10 je obvykle přiřazována k první cifře (zleva). Ale váhy se dají i zcela převrátit. Pokud si totiž uvědomíme, že zbytek 10 má při dělení (prvočíslem) 11 zcela stejnou funkci jako záporná hodnota -1 , a podobně je zbytek 9 stejný jako -2, 8 je -3 a tak dále. Jelikož používáme zbytek z = 0 , můžeme bez problému (v tělese zbytkových tříd modulo 11 ) rovnici pro kontrolu CDV vynásobit (zbytkem) -1 . Váhy se tak "otočí", neboť i v tělese zbytkový tříd znamená násobení pomocí -1 pouze změnu znaménka. Proto je jedno, zda při kontrole CDV pro (původní) ISBN použijeme váhy od 10 do 1 anebo od 1 do 10. V obou variantách musí být součet násobků dělitelný beze zbytku (prvočíslem) 11. V této souvislosti je třeba upozornit, že takto nelze otočit váhy pro ISSN. Tam podle stejného principu váhy 8, 7, 6, 5, 4, 3, 2, 1 můžeme transformovat jen na 3, 4, 5, 6, 7, 8, 9, 10 .

Jednu významnou výhodu ale obecně použití prvočíselného modulu má (platnou třeba i pro současné ISSN). Zabezpečuje číslo i proti druhému typu náhodných chyb, a to vzájemnému přehození dvou cifer. Odvození je téměř stejně snadné jako pro změnu jedné cifry. Předpokládejme, že čísla x₁ . . x_k . . x_m . . x_n , x₁ . . x_m . . x_k . . x_n splňují obě kontrolu CDV, ale jsou v nich navzájem přehozeny cifry na k-té a m-té pozici. Napíšeme-li si stejně (jako pro první variantu náhodné chyby) obě rovnice vyjadřující kontrolu CDV a znovu rovnice odečteme, dostaneme postupně:
v_k.(x_k-x_m) + v_m.(x_m-x_k) =^(p) 0
(v_k-v_m) . (x_k-x_m) =^(p) 0

Oproti odvození podmínky pro první typ chyby se situace liší pouze v tom, že rozdíl dvou cifer je násoben rozdílem dvou vah. Pokud je modul větší než všechny přípustné cifry, nemůže být jakýkoliv rozdíl dvou různých cifer dělitelný modulem p. A budeme-li i váhy používat menší než p, nebude ani rozdíl dvou různých vah dělitelný p. Tedy pro vzájemné přehození cifer na pozicích s rozdílnými vahami nemůže následně vyjít kontrola CDV. Proto se váhy vždy liší minimálně na sousedních pozicích. Kontrola CDV pak zabrání náhodnému přehození sousedních cifer. ISSN (nebo i původní ISBN) má dokonce všechny váhy odlišné, tedy je chráněno před vzájemným přehozením dvou cifer v libovolných místech (nejen tedy sousedních).
Podmínku rozdílnosti pouze sousedních vah například využívají naše 10ti místná rodná čísla, kde se jako váhy střídají čísla 10, 1, 10, 1, ...

4. Kontrola nového ISBN

Daleko těžší je stanovit váhy při neprvočíselném modulu p. To je bohužel případ nově zavedené kontroly pro třináctimístné ISBN, kde je použit (analogicky EAN) modul p=10. Přes všechnu snahu je ale možné zabezpečit jen první tvar náhodné chyby. Proto se většinou od modulu 10 ustoupilo, vyjma historicky zavedených kontrol.

Vyjděme z poslední rovnice pro vzájemné přehození dvou cifer:
(v_k-v_m) . (x_k-x_m) =⁽¹⁰⁾ 0
Bude-li rozdíl vah sudé číslo, nejsme schopni zachytit vzájemné přehození cifer, jejichž rozdíl je 5. Tedy třeba dvojici (sousedních) cifer 16 omylem natypovaných jako 61. Sudé číslo násobené 5 je totiž vždy dělitelné 10. Vzápětí ale uvidíme, že všechny váhy musí být jen lichá čísla, takže rozdíl vah bude vždy sudý. Proto nikdy spolehlivě nezabezpečíme vzájemné přehození dvou cifer.

Zkusme tedy hledat alespoň váhy, které by byly schopny ochránit před (náhodnou) změnou jedné jediné cifry. V tomto případě má rovnice tvar:
v_k.(x_k-y_k) =⁽¹⁰⁾ 0
Rozdíl původní a změněné cifry může být jakékoliv (celé) číslo od -9 do 9. Přitom modul 10 lze rozložit na součin prvočísel 2.5 = 10. Aby rovnice nemohla začít platit pro nějakou změnu jedné cifry, nesmí být použitá váha násobkem 2 nebo 5. Takovéto možné váhy (menší než 10) jsou pouze čtyři: 1, 3, 7, 9 (tak zvaní nedělitelé nuly). A samozřejmě jsou to jen lichá čísla. Podstatné ovšem je, že žádné číslo (v absolutní hodnotě) menší než 10 nedává s jejich násobkem číslo dělitelné 10. (Protože podle prvočíselného rozkladu by nevyhnutelně muselo být nějakým způsobem vynásobeno buď 5 anebo sudým číslem, tedy násobkem 2.)

Nově používaná kontrola (třináctimístného) ISBN používá (střídající se) váhy: 1, 3, 1, 3, 1, ..., 3, 1 a modul p=10 (zbytek z=0). Pro splnění kontroly CDV tak součet všech násobků musí dávat číslo dělitelné 10.

Jednoduchý je i výpočet kontrolní číslice. Předpokládejme, že známe 9 (přidělovaných) cifer ISBN x₁x₂ . . x₈ x₉ , poslední (kontrolní) cifru x_ean budeme chtít vypočítat. Uvažujeme-li ještě obvyklý (trojciferný) prefix 978, musí platit vztah:
1.9 + 3.7 + 1.8 + 3.x₁ + 1.x₂ + . . + 1.x₈ + 3.x₉ + 1.x_ean =⁽¹⁰⁾ 0
Z čehož při drobných úpravách dostáváme:
38 + 3.x₁ + 1.x₂ + . . + 1.x₈ + 3.x₉ =⁽¹⁰⁾ -1.x_ean
- x_ean =⁽¹⁰⁾ 8 + 3.x₁+ 1.x₂ + . . + 1.x₈ + 3.x₉
Postup výpočtu kontrolní cifry (po zahrnutí zbytku standardního prefixu) vypadá tak, že 9 známých cifer násobíme vahami 3, 1,.., 1, 3, přičteme 8 a zbytek při dělení 10 (tj. poslední číslici celé sumy) odečteme od 10 (samozřejmě, pokud již onen zbytek nebyl nulový).

Tak například ISBN 978‑953‑266‑00 4‑6 je chybné. Budeme-li podle zmíněného algoritmu počítat poslední kontrolní číslici, stačí u násobků sčítat jen poslední cifry: 8 + 27+5+9 + 2+18+6 + 0+0+12 =⁽¹⁰⁾ 47, kontrolní číslice tedy má být 3. Příklad je chybným ISBN v databázi NKC Národní knihovny a je u něj dokonce poznámka (chyb.) , která se ale objevuje často, i když kontrola CDV vychází správně. Povětšinou se tak děje v případech, kdy nové (formálně správné) ISBN je u knih vydaných před rokem 2007. (Někdy ale i toto upozornění chybí, jako třeba pro následující ISBN 978‑9955‑704‑ 16‑4 kontrolu CDV splňující: 8 + 27+9+15+5 + 21+0+12 + 1+18 + 4 =⁽¹⁰⁾ 0.)

5. Programová realizace

Pochopitelně bude v dnešní době málokdo kontrolu provádět ručně. Realizace výpočtu kontrolní číslice v nějakém programovém prostředí je obecně velmi jednoduchá. V programovém prostředí je snad jedině potřeba, aby bylo nějak možno vypočítat zbytek (protože sčítat a násobit je možno prakticky všude). Pravda, bývá také potřeba, aby šlo nějak programově realizovat podmínku (if). Pro ISSN (či staré ISBN) to dokonce bylo nezbytné, neboť se zbytek 10 musel převádět na X. Pro třináctimístné ISBN ovšem není ani potřeba podmínkou rozlišovat, zda zbytek již je 0 či se teprve musí odečíst od 10. Funkce záporné hodnoty se totiž dá nahradit násobením 9 , což je -1. Takto je také výpočet realizován v javascriptu spustitelném snad v každém grafické WWW-prohlížeči (a to dokonce i ze souboru uloženém disku).
Pro úplnost je třeba uvést, že script spočítá kontrolní číslici pro staré i nové ISBN (řídí se úvodním trojčíslím) a jako službu navíc je schopen knihu podle ISBN vyhledat v knihovním katalogu VŠE. Pro ilustraci výpočtu v něm byly použity jen ty nejjednodušší příkazy.

Pro výpočet kontrolní číslice není tedy nutné se obracet na nějaký server. Výpočet kontrolní číslice je dokonce možné realizovat i v Excelu. Zbytek (funkce MOD) a podmínku (KDYŽ) Excel umí. Proto je poměrně překvapivé, že si u nás skoro nikdo není schopen program pro kontrolu CDV sám vytvořit v prostředí, které mu pro jeho práci nejvíce vyhovuje. A raději třeba každé ISBN kontroluje v nějakém katalogu. Protože se mi tato věc zdála poněkud podivná, zkusil jsem v prvním semestru na VŠE, ovšem studentům ekonomie, nikoliv informatiky, zadat jako úkol nalezení algoritmu v Internetu a realizaci výpočtu kontrolní číslice ISBN v Excelu (v rámci zcela úvodního kurzu Informatiky). Překvapením bylo, že to většina studentů za domácí úkol zvládla snad samostatně, nebo mi přinejmenším byli přesně schopni vysvětlit, co v jaké buňce mají uloženo. (Musím bohužel litovat zavedení nového ISBN, kde je možno se vyhnout použití podmínky.) Ovšem ještě musím doplnit nemilé zjištění, že snad obtížnější se jevila úloha některým vyučující než studentům.

Zároveň onen příklad uvádím na podporu tvrzení, že úroveň výuky na středních školách není zdaleka špatná. Spíše se něco chybného děje ve výuce Informatiky (a možná i matematiky) na školách vysokých. Především se totiž na vysokých školách nedostatečně rozšiřují základy algebry a konečné matematiky, které hrají v informatických předmětech mnohem větší roli než zmiňované základy diferenciálního a integrálního počtu. A když posléze někdo někdy na typicky algebraický problém v informatice narazí (a to i specialista informatik), snaží se obvykle situaci vyřešit odkazem nebo programem někde na Internetu. Na střední (nebo i základní) školu si každý těžko vzpomíná, ale hlavně ho poslední dobou učili o počítačích převážně přes definice pojmů a vyhledávání v Menu.

Obávám se, že toto je největší problém, se kterým se u nás bude muset informatická výuka (možná lépe počítačová výuka) vypořádat. Totiž se stereotypem popisné výuky, který přetrvává z období ASŘ (Automatizovaných Systémů Řízení). Místo aby výuka směřovala od používání nástrojů k jednoduchým algoritmů a jejich programové realizaci, učí se studenti třeba 20 let starou definici Internetu, protože přednášející si ani definici Internetu nezkusil na Internetu vyhledat. Před časem jsem četl v novinách článek, v němž se autor pohoršoval nad tím, jak někdo píše doktorskou práci o francouzské literatuře, a přitom vůbec neumí francouzsky. Ale to je při počítačové výuce běžné. Kolik profesorů informatiky vůbec někdy programovalo. A kolik dalších vyučujících si i své osobní home-stránky nechá udělat od studentů. Což je typická ukázka, jak většina absolventů informatiky jsou hlavně samoukové. Proč se tedy divit lidem, jejichž hlavním oborem není informatika, že se jako vysokoškolští absolventi (a dobří samoukové) sami hned nepouštějí do výpočtu kontrolních číslic. I když staré a nové ISBN je pro "samouky informatiky" lepší počítačová kvalifikace než pověstný "Řidičák na počítač".