Kolik možností má kombinační zámek?
Podívejme se stručně na pojmy a vzorce nezbytné k vyřešení úkolu 10 jednotné státní zkoušky.
Měření množství informací
Jednotky:
1 bytů (bajt) = 8 bitů
1 Kb (kilobajt) = 1024 bajtů
1 MB (megabajt) = 1024 kB
1 GB (gigabajt) = 1024 MB
1 TB (terabajt) = 1024 GB
1 Pb (petabajt) = 1024 TB
1024=2 10
Podívejme se na několik dalších definic:
- Kódování je prezentace informací ve formě vhodné pro jejich uložení, přenos a zpracování. Pravidlo pro převod informací na takovou reprezentaci se nazývá kód.
- Bit 1 je množství informací, které lze přenést pomocí jednoho znaku v binárním kódu ( nebo 1).
Binární kódování zpráv (stejně pravděpodobné události)
Při výpočtu množství informací ve zprávě pro stejně pravděpodobné události, jejichž celkový počet se rovná N, používá se vzorec:
N=2I
* Je třeba mít na paměti, že jsou akceptovány také následující zápisy: Q = 2 k
Příklad 2: Zašifrujeme písmena A, B, C, D pomocí binárního kódování s jednotným kódem a spočítat počet možných zpráv:
Tak jsme dostali jednotný kódProtože délka každého kódového slova je stejná pro všechny kódy (2).
A počet zpráv o délce I bitů:
N=2I
Tito. počet zpráv délka 2 bit, jako v příkladu s našimi písmeny, bude roven Q = 2 2 = 4
Počet různých zpráv v abecedě různých mocností
Zvažte možnost s 5 dopisy (síla abecedy = 5), který musí být umístěn ve zprávě o délce 2 symbol:
Pojďme najít vzorec pro zjištění počtu různých zpráv v abecedě různé mohutnosti:
Pokud je mohutnost některé abecedy N, pak počet různých zpráv o délce L znaků:
- N – síla abecedy
- L – délka zprávy
- Q – počet různých zpráv
Příklad: Kolik různých třípísmenných slov je v angličtině?
řešení:
V anglické abecedě je 26 písmen. Prostředek síla abecedy = 26. Délka zprávy = 3. Najdeme to pomocí vzorce počet třípísmenných slov:
Q = 26 3
- Pokud se slovo skládá z L písmen a existuje n1 možností pro výběr prvního písmene, n2 možností pro výběr druhého písmene atd., pak se počet možných slov vypočítá jako součin:
N = n1 * n2 * … * nL
Počet zpráv s různým výskytem písmen
Někdy v úkolech 10 musíte použít kombinatorický vzorec pro kontrolu získaných výsledků vyhledávání. Počet kombinací n prvků z k prvků:
Počet kombinací n prvků
k prvků každý
- I – množství informací v bitech
- N – počet možností
Příklad: Kolik různých typů existuje? pět písmen slova v 4písmenné abecedě: A, B, C, D, je-li známo, že písm А schází rovnou dvakrát?
dvakrát písmeno A, na jiných místech - jedno ze tří zbývajících písmen: А А 3 3 = 3 * 3 = 32 = 9 А 3 А 3 А 3 3 А 3 А А 3 3 А 3 А 3 3 А А
Počet kombinací n prvky podle k Prvky:
C k n=n!/(n!*(nk)!)
C24 = 4!/(2!*(4-2)!) = 24/(2*2) = 6 možností Faktoriál čísla n! = 0*1*2*3..*n
6 * 9 = 54 - Délka zprávy = 4. Síla abecedy = 4. Ale překáží podmínka: dopis А schází rovnou dvakrát.
- V takových úlohách se používá metoda výčtu všech možných možností:
- Obdrželi jste 6 variant, z nichž každý je roven 9.
- Zkontrolujeme vzorec pro počet kombinací:
- Tito. ověření proběhlo úspěšně, dostali jsme 6 možností.
- Zbývá spočítat počet všech zpráv:
Další vzorce
Množství informací a stejně pravděpodobné události
Při určování množství informací pro stejně pravděpodobné události mohou být zapotřebí dva vzorce:
- x — množství informací ve zprávě události
- p — pravděpodobnost události
- Vzorec pro pravděpodobnost náhodné události:
- m — počet příznivých výsledků (počet případů přispívajících k události A)
- n — počet společných výsledků (celkový počet stejně možných případů)
Množství informací a nestejně pravděpodobné události
Při použití nejednotné události, jejíž pravděpodobnost je p, se pro výpočet množství informace použije vzorec:
*hranaté závorky znamenají nejbližší celé číslo menší nebo rovné hodnotě výrazu v závorce
Hartleyho vzorec:
- I – množství informací v bitech
- N – počet možností
Abecední přístup:
Informační objem zprávy o délce L:
Jednotná státní zkouška z informatiky 2017 úkol 10 FIPI varianta 1 (Krylov S.S., Churkina T.E.): Šifra kombinačního zámku je posloupnost pět znaků, z nichž každá je číslo od 1 do 6. Kolik různých možností šifry lze zadat, pokud je známo, že se v kódu musí objevit číslo 1? přesně 1krát, a každá z dalších platných číslic se může v šifře objevit libovolněkrát nebo se nevyskytuje vůbec?
řešení:
Co tedy z tohoto vzorce máme:
1 5 5 5 5 -1 * Q=54= 625 5 1 5 5 5 -1 * Q=54= 625 5 5 1 5 5 -1 * Q=54= 625 5 5 5 1 5 -1 * Q=54= 625 5 5 5 5 1 -1 * Q=54= 625
625 * 5 = 3125 - Vzorec pro počet různých zpráv:
- Délka zprávy (L) = 5 znaků
- Počáteční mocnina abecedy (N) = 6 (číslice 1 až 6). Ale protože číslo 1 se objeví přesně jednou a zbývajících 5 číslic – libovolněkrát, budeme předpokládat, že N = 5 (čísla od 2 do 6)
- Počet různých zpráv (volby šifry) = Q = ?
- Podle podmínky získáme následující možnosti umístění (umístíme 5 číslic na 4 pozice):
- V důsledku toho získáme:
Výsledek: 3125
Jednotná státní zkouška z informatiky 2017 úkol 10 FIPI varianta 5 (Krylov S.S., Churkina T.E.):
Šifra kombinačního zámku je posloupnost pět znaků, z nichž každé je jedno z písmen X, Y nebo Z. Kolik různých variant šifry lze zadat, pokud je známo, že se v kódu musí objevit písmeno X? přesně 2xa každé z ostatních platných písmen se může v šifře objevit kolikrát, nebo se nemusí objevit vůbec?
řešení:
Co tedy z tohoto vzorce máme:
Výčet všech možností:
XX? ? ? -12 * Q=23= 8 X? X? ? -12 * Q=23= 8 X? ? X? -12 * Q=23= 8 X? ? ? X -12 * Q=23= 8 ? XX? ? -12 * Q=23= 8 ? X? X? -12 * Q=23= 8 ? X? ? X -12 * Q=23= 8 ? ? XX? -12 * Q=23= 8 ? ? X? X -12 * Q=23= 8 ? ? ? XX -12 * Q=23= 8
Počet kombinací n prvky podle k Prvky:
C k n=n!/(n!*(nk)!)
C25 = 5!/(2!*(5-2)!) = 120/(12) = 10 variant * Faktorové číslo: n = 0*1*2*3..*n 8 * 10 = 80 - Vzorec pro počet různých zpráv:
- Počáteční mocnina abecedy (N) = 3 (písmena X, Y, Z). Ale od dopisu X se vyskytuje přesně dvakrát, pak to budeme uvažovat samostatně a zbývající 2 písmena – libovolný počet opakování, což znamená, že budeme předpokládat, že N = 3-1 = 2 (Y a Z)
- Na základě předchozího bodu se také zkrátí délka zprávy: ( L ) = 5-2 = 3 znaky (zbývající dva znaky budou přiděleny umístění X)
- Počet různých zpráv (volby šifry) = Q = ?
- Podle podmínky získáme následující možnosti umístění:
- Výsledný počet možností zkontrolujme pomocí vzorce pro zjištění počtu kombinací.
- Počet zaškrtnutých možností (=10). V důsledku toho dostaneme:
Výsledek: 80
Jednotná státní zkouška z informatiky 2017 úkol 10 FIPI varianta 10 (Krylov S.S., Churkina T.E.):
Šifra kombinačního zámku je posloupnost pět znaků, z nichž každé je buď písmeno (A nebo B) nebo číslo (1, 2 nebo 3). Kolik různých možností šifry lze zadat, pokud je známo, že kód obsahuje přesně jedno písmeno, a všechno ostatní znaky jsou čísla?
řešení:
Vzorec pro počet různých zpráv:
Q = 2 * 34 = 162
"2" znamená jedno ze dvou písmen: A nebo B, "3" - jedno ze tří čísel: 2 3 3 3 3 -> Q = 2 * 34 = 162 3 2 3 3 3 -> Q = 2 * 34 = 162 3 3 2 3 3 -> Q = 2 * 34 = 162 3 3 3 2 3 -> Q = 2 * 34 = 162 3 3 3 3 2 -> Q = 2 * 34 = 162
- Protože čísla (1, 2, 3) mohou obsadit 4 pozice z pěti a dvě písmena (A a B) mohou obsadit jednu z pozic, znamená to:
- Podle podmínky získáme následující možnosti umístění:
- Dostali jsme 5 možností, každou s písmeny A a B
- Zbývá vynásobit: 5*162 = 810
Výsledek: 810