Binární logaritmus - Binary logarithm

Graf log2 X jako funkce kladného reálného čísla X

v matematika, binární logaritmus (log2 n) je Napájení na které číslo 2 musí být zvednutý k získání hodnotyn. To znamená pro jakékoli skutečné číslo X,

Například binární logaritmus 1 je 0, binární logaritmus 2 je 1, binární logaritmus 4 je2a binární logaritmus 32 je5.

Binární logaritmus je logaritmus na základnu 2. Funkce binárního logaritmu je inverzní funkce z síla dvou funkce. Stejně jako log2, alternativní zápisy pro binární logaritmus zahrnují lg, ld, lb (notace upřednostňovaná ISO 31-11 a ISO 80000-2 ) a (s předchozím prohlášením, že výchozí základna je 2) log.

Historicky byla první aplikace binárních logaritmů v hudební teorie tím, že Leonhard Euler: binární logaritmus frekvenčního poměru dvou hudebních tónů udává počet oktávy čímž se liší tóny. Binární logaritmy lze použít k výpočtu délky zastoupení čísla v binární číselná soustava nebo počet bity potřebné k zakódování zprávy teorie informace. v počítačová věda, spočítají počet kroků potřebných pro binární vyhledávání a související algoritmy. Mezi další oblasti, ve kterých se často používá binární logaritmus, patří kombinatorika, bioinformatika, design sportu turnaje, a fotografování.

Standard obsahuje binární logaritmy C matematické funkce a další matematické softwarové balíčky. Celočíselnou část binárního logaritmu najdete pomocí najít první sadu operace s celočíselnou hodnotou nebo vyhledáním exponentu a plovoucí bod Frakční část logaritmu lze vypočítat efektivně.

Dějiny

Hlavní článek: Historie logaritmů
Leonhard Euler jako první použil binární logaritmy na hudební teorie, v roce 1739.

The pravomoci dvou jsou známí již od starověku; například se objevují v Euklidova Elementy, Rekvizity. IX.32 (na faktorizace pravomocí dvou) a IX.36 (polovina Euklidova – Eulerova věta, na struktuře sudých perfektní čísla ). A binární logaritmus síly dvou je pouze její poloha v uspořádané posloupnosti sil dvou. Na tomto základě Michael Stifel byl připočítán s publikováním první známé tabulky binárních logaritmů v roce 1544. Jeho kniha Arithmetica Integra obsahuje několik tabulek, které ukazují celá čísla s jejich odpovídajícími pravomocemi dvou. Obrácení řádků těchto tabulek umožňuje jejich interpretaci jako tabulek binárních logaritmů.[1][2]

Dříve než Stifel, 8. století Jain matematik Virasena je připsán předchůdce binárního logaritmu. Virasenův koncept ardhacheda byl definován jako počet případů, kdy lze dané číslo rozdělit rovnoměrně dvěma. Tato definice dává vzniknout funkci, která se shoduje s binárním logaritmem o síle dvou,[3] ale u jiných celých čísel je to jiné, dává 2-adic pořadí spíše než logaritmus.[4]

Moderní formu binárního logaritmu, vztahující se k jakémukoli číslu (nejen mocninám dvou), explicitně zvažoval Leonhard Euler v roce 1739. Euler zavedl aplikaci binárních logaritmů na hudební teorii, dlouho předtím, než byly známy jejich aplikace v teorii informací a počítačové vědě. V rámci své práce v této oblasti publikoval Euler tabulku binárních logaritmů celých čísel od 1 do 8, na sedm desetinných míst přesnosti.[5][6]

Definice a vlastnosti

Funkce binárního logaritmu může být definována jako inverzní funkce do síla dvou funkce, což je přísně rostoucí funkce nad kladným reálná čísla a proto má jedinečnou inverzi.[7]Alternativně to může být definováno jako ln n/ ln 2, kde ln je přirozený logaritmus, definované jakýmkoli ze svých standardních způsobů. Za použití komplexní logaritmus v této definici umožňuje rozšířit binární logaritmus na komplexní čísla.[8]

Stejně jako u jiných logaritmů se binární logaritmus řídí následujícími rovnicemi, které lze použít ke zjednodušení vzorců kombinujících binární logaritmy s násobením nebo umocněním:[9]

Více viz seznam logaritmických identit.

Zápis

V matematice binární logaritmus čísla n je často psáno jako log2 n.[10] Bylo však použito nebo navrženo několik dalších notací pro tuto funkci, zejména v aplikačních oblastech.

Někteří autoři píší binární logaritmus jako lg n,[11][12] zápis uvedený v Chicago Style Style.[13] Donald Knuth připíše tuto notaci na návrh Edward Reingold,[14] ale jeho použití jak v teorii informací, tak v informatice se datuje do doby, než byl Reingold aktivní.[15][16] Binární logaritmus byl také zapsán jako log n s předchozím prohlášením, že výchozí základna pro logaritmus je2.[17][18][19] Další notace, která se často používá pro stejnou funkci (zejména v německé vědecké literatuře), je ld n,[20][21][22] z latinský logaritmus dualis[20] nebo logarithmus dyadis.[20]The DIN 1302 [de ], ISO 31-11 a ISO 80000-2 standardy doporučují ještě další notaci, lb n. Podle těchto standardů lg n by neměl být použit pro binární logaritmus, protože je místo toho vyhrazen pro společný logaritmus log10 n.[23][24][25]

Aplikace

Viz také: Zdvojnásobení času

Informační teorie

Počet číslic (bity ) v binární reprezentace kladného celého čísla n je nedílná součást z 1 + log2 n, tj.[12]

V teorii informací je definice množství vlastní informace a informační entropie je často vyjádřen binárním logaritmem, což odpovídá tomu, že se bit stal základní jednotkou informací. Nicméně přirozený logaritmus a nat jsou také používány v alternativních zápisech pro tyto definice.[26]

Kombinatorika

16 hráčů jediná eliminace turnajová závorka se strukturou a kompletní binární strom. Výška stromu (počet kol turnaje) je binární logaritmus počtu hráčů zaokrouhlený na celé číslo nahoru.

Ačkoli přirozený logaritmus je důležitější než binární logaritmus v mnoha oblastech čisté matematiky, jako je teorie čísel a matematická analýza,[27] binární logaritmus má několik aplikací ve Windows kombinatorika:

  • Každý binární strom s n listy mají minimálně výšku log2 n, s rovností kdy n je síla dvou a strom je a kompletní binární strom.[28] Souvisejícím způsobem je Strahlerovo číslo říčního systému s n přítoků je maximálně log2 n + 1.[29]
  • Každý rodina sad s n různé sady má alespoň log2 n prvky v jeho unii, s rovností, když je rodina a napájecí sada.[30]
  • Každý částečná kostka s n vrcholy má alespoň izometrický rozměr log2 n, a má maximálně 1/2 n log2 n hrany, s rovností, když je částečná kostka a hyperkrychlový graf.[31]
  • Podle Ramseyova věta, každý n-vrchol neorientovaný graf má buď a klika nebo nezávislá sada logaritmické velikosti v n. Přesná velikost, kterou lze zaručit, není známa, ale nejlepší hranice známé její velikosti zahrnují binární logaritmy. Zejména všechny grafy mají alespoň kliky nebo nezávislé množiny velikostí 1/2 log2 n (1 − Ó(1)) a téměř všechny grafy nemají větší velikost kliky nebo nezávislé sady 2 log2 n (1 + Ó(1)).[32]
  • Z matematické analýzy Gilbert – Shannon – rákosový model z náhodného zamíchání lze ukázat, že kolikrát je třeba zamíchat nbalíček karet pomocí, riffle shuffles, získat distribuci na permutacích, která je blízká rovnoměrně náhodnému, je přibližně 3/2 log2 n. Tento výpočet tvoří základ pro doporučení, aby balíčky s 52 kartami byly zamíchány sedmkrát.[33]

Výpočetní složitost

Binární vyhledávání v seřazeném poli, algoritmus, jehož časová složitost zahrnuje binární logaritmy

Binární logaritmus se také často objevuje v analýza algoritmů,[19] nejen kvůli častému používání aritmetiky binárního čísla v algoritmech, ale také proto, že binární logaritmy se vyskytují při analýze algoritmů založených na oboustranném větvení.[14] Pokud problém zpočátku má n volby pro jeho řešení a každá iterace algoritmu snižuje počet voleb o faktor dva, pak je počet iterací potřebných k výběru jedné volby opět nedílnou součástí log2 n. Tato myšlenka se používá při analýze několika algoritmy a datové struktury. Například v binární vyhledávání, velikost problému, který má být vyřešen, se při každé iteraci sníží na polovinu, a tedy zhruba log2 n k získání řešení problému s velikostí jsou nutné iterace n.[34] Stejně tak dokonale vyvážený binární vyhledávací strom obsahující n prvků má výšku log2(n + 1) − 1.[35]

Doba trvání algoritmu je obvykle vyjádřena v velká O notace, který se používá ke zjednodušení výrazů vynecháním jejich konstantních faktorů a výrazů nižšího řádu. Protože logaritmy v různých základnách se od sebe liší pouze konstantním faktorem, běží algoritmy Ó(log2 n) lze také říci, že běží čas, řekněme Ó(log13 n) čas. Základ logaritmu ve výrazech jako např Ó(log n) nebo Ó(n log n) není proto důležité a lze jej vynechat.[11][36] U logaritmů, které se objevují v exponentu časové vazby, však nelze základ logaritmu vynechat. Například, Ó(2log2 n) není totéž jako Ó(2ln n) protože první se rovná Ó(n) a ten druhý Ó(n0.6931...).

Algoritmy s dobou chodu Ó(n logn) jsou někdy nazývány linearithmic.[37] Některé příklady algoritmů s dobou chodu Ó(log n) nebo Ó(n log n) jsou:

Binární logaritmy se u některých také vyskytují v exponentech časových mezí algoritmy rozděl a panuj, tak jako Algoritmus Karatsuba pro násobení n-bitová čísla v čase Ó(nlog2 3),[42]a Strassenův algoritmus pro násobení n × n matice v časeÓ(nlog2 7).[43] Výskyt binárních logaritmů v těchto dobách chodu lze vysvětlit odkazem na hlavní věta o opakování rozděli a panuj.

Bioinformatika

A microarray pro přibližně 8700 genů. Míry exprese těchto genů jsou porovnávány pomocí binárních logaritmů.

v bioinformatika, mikročipy se používají k měření, jak silně jsou různé geny exprimovány ve vzorku biologického materiálu. Různé rychlosti exprese genu jsou často srovnávány použitím binárního logaritmu poměru rychlostí exprese: log poměr dvou rychlostí exprese je definován jako binární logaritmus poměru těchto dvou rychlostí. Binární logaritmy umožňují pohodlné srovnání expresních rychlostí: zdvojnásobenou expresní rychlost lze popsat logaritmickým poměrem 1, lze snížit rychlost vyjádření na polovinu logaritmickým poměrem −1a nezměněnou rychlost vyjádření lze popsat například logaritmickým poměrem nula.[44]

Takto získané datové body jsou často vizualizovány jako a bodový diagram ve kterém jedna nebo obě souřadnicové osy jsou binární logaritmy poměrů intenzity, nebo ve vizualizacích, jako je MA spiknutí a RA spiknutí které tyto scatterploty s logaritmickým poměrem otáčejí a mění jejich velikost.[45]

Hudební teorie

v hudební teorie, interval nebo percepční rozdíl mezi dvěma tóny je určen poměrem jejich frekvencí. Intervaly vycházející z racionální číslo poměry s malými čitateli a jmenovateli jsou vnímány jako obzvláště euforické. Nejjednodušší a nejdůležitější z těchto intervalů je oktáva, frekvenční poměr 2:1. Počet oktáv, o které se dva tóny liší, je binární logaritmus jejich frekvenčního poměru.[46]

Studovat tuningové systémy a další aspekty hudební teorie, které vyžadují jemnější rozdíly mezi tóny, je užitečné mít míru velikosti intervalu, která je jemnější než oktáva a je aditivní (jak jsou logaritmy), spíše než multiplikativní (jako jsou frekvenční poměry). To znamená, že pokud tóny X, y, a z tvoří stoupající posloupnost tónů, pak měřítko intervalu od X na y plus míra intervalu od y na z by se měla rovnat míře intervalu od X na z. Takové opatření stanoví cent, který rozdělí oktávu na 1200 stejné intervaly (12 půltóny z 100 každý cent). Matematicky dané tóny s frekvencemi F1 a F2, počet centů v intervalu od F1 na F2 je[46]

The milioctave je definován stejným způsobem, ale s multiplikátorem 1000 namísto 1200.[47]

Plánování sportu

V soutěžních hrách a sportech zahrnujících dva hráče nebo týmy v každé hře nebo zápase binární logaritmus označuje počet kol nutných v single-eliminační turnaj k určení vítěze. Například turnaj o 4 hráči vyžadují log2 4 = 2 kola k určení vítěze, turnaj o 32 týmy vyžadují log2 32 = 5 nábojů atd. V tomto případě pro n hráči / týmy kde n není síla 2, log2 n se zaokrouhluje nahoru, protože je nutné mít alespoň jedno kolo, ve kterém nehrají všichni zbývající soutěžící. Například, log2 6 je přibližně 2.585, která se zaokrouhluje na 3, což naznačuje, že turnaj o 6 týmy vyžadují 3 kola (buď první tým sedí dva týmy, nebo druhý tým jeden tým). Stejný počet kol je také nezbytný k určení jasného vítěze v a Turnaj ve švýcarském systému.[48]

Fotografování

v fotografování, hodnoty expozice se měří jako binární logaritmus množství světla dopadajícího na film nebo senzor v souladu s Weber – Fechnerův zákon popisující logaritmickou odezvu lidského vizuálního systému na světlo. Jedna zastávka expozice je jedna jednotka na základně2 logaritmická stupnice.[49][50] Přesněji je hodnota expozice fotografie definována jako

kde N je clonové číslo měření clona - objektivu během expozice a - t je počet sekund expozice.[51]

Binární logaritmy (vyjádřené jako zastávky) se také používají v denzitometrie, vyjádřit dynamický rozsah materiálů citlivých na světlo nebo digitálních senzorů.[52]

Výpočet

TI SR-50 vědecká kalkulačka (1974). Klávesy ln a log jsou ve druhé řadě; neexistuje žádný protokol2 klíč.

Konverze z jiných základen

Snadný způsob výpočtu log2 n na kalkulačky které nemají log2 funkcí je použít přirozený logaritmus (ln) nebo společný logaritmus (log nebo log10) funkce, které najdete na většině vědecké kalkulačky. Konkrétní změna základny logaritmu vzorce k tomu jsou:[50][53]

nebo přibližně

Zaokrouhlení na celé číslo

Z binárního logaritmu lze vytvořit funkci z celých čísel a celých čísel pomocí zaokrouhlování nahoru nebo dolů. Tyto dvě formy celočíselného binárního logaritmu souvisí s tímto vzorcem:

[54]

Definici lze rozšířit definováním . Takto rozšířená tato funkce souvisí s počet úvodních nul 32bitové nepodepsané binární reprezentace X, nlz (X).

[54]

Celočíselný binární logaritmus lze interpretovat jako nulový index nejvýznamnějšího 1 bit na vstupu. V tomto smyslu je doplňkem najít první sadu operace, která najde index nejméně významného 1 bit. Mnoho hardwarových platforem zahrnuje podporu pro zjištění počtu předních nul nebo ekvivalentních operací, které lze použít k rychlému nalezení binárního logaritmu. The fls a flsl funkce v Linuxové jádro[55] a v některých verzích libc softwarová knihovna také počítá binární logaritmus (zaokrouhlený na celé číslo, plus jedno).

Iterativní aproximace

Pro generála kladné reálné číslo, binární logaritmus lze vypočítat ve dvou částech.[56]Nejprve spočítáme celá část, (nazývá se charakteristika logaritmu). Tím se problém sníží na jeden, kde je argument logaritmu v omezeném rozsahu, interval [1, 2], což zjednodušuje druhý krok výpočtu zlomkové části (mantisa logaritmu) ) .Pro všechny X > 0, existuje jedinečné celé číslo n takhle 2n ≤ X < 2n+1nebo ekvivalentně 1 ≤ 2−nX < 2. Nyní je celá část logaritmu jednoduše na zlomková část je log2(2−nX).[56] Jinými slovy:

Pro normalizované plovoucí bod čísla, celočíselná část je dána exponentem s plovoucí desetinnou čárkou,[57] a pro celá čísla to lze určit provedením a počítat úvodní nuly úkon.[58]

Částečná část výsledku je log2 y a lze jej vypočítat iterativně, pouze s použitím elementárního násobení a dělení.[56]Algoritmus pro výpočet zlomkové části lze popsat v pseudo kód jak následuje:

  1. Začněte skutečným číslem y v polootevřeném intervalu [1, 2). Li y = 1, pak je algoritmus hotový a zlomková část je nulová.
  2. Jinak čtvercový y opakovaně až do výsledku z leží v intervalu [2, 4). Nechat m počet potřebných čtverců. To znamená, z = y2m s m vybral tak, že z je v [2, 4).
  3. Vezmeme-li logaritmus obou stran a provedeme nějakou algebru:
  4. Ještě jednou z/2 je reálné číslo v intervalu [1, 2). Vraťte se ke kroku 1 a spočítejte binární logaritmus z/2 stejnou metodou.

Výsledek je vyjádřen následujícími rekurzivními vzorci, ve kterých je počet čtverců požadovaných v i-tá iterace algoritmu:

Ve zvláštním případě, kdy se v kroku 1 zjistí, že dílčí část je nula, je to a konečný sekvence v určitém okamžiku končí. Jinak je to nekonečná řada že konverguje podle poměrový test, protože každý termín je přísně menší než ten předchozí (protože každý mi > 0). Pro praktické použití musí být tato nekonečná řada zkrácena, aby bylo dosaženo přibližného výsledku. Pokud je série po i-tý termín, pak je chyba ve výsledku menší než 2−(m1 + m2 + ... + mi).[56]

Podpora softwarové knihovny

The log2 funkce je součástí standardu C matematické funkce. Výchozí verze této funkce trvá dvojnásobná přesnost argumenty, ale jeho varianty umožňují, aby byl argument přesný nebo byl a dlouhý dvojitý.[59] v MATLAB, argument k log2 funkce může být a záporné číslo, a v tomto případě bude výsledkem a komplexní číslo.[60]

Reference

  1. ^ Groza, Vivian Shaw; Shelley, Susanne M. (1972), Precalculus matematika, New York: Holt, Rinehart a Winston, s. 182, ISBN  978-0-03-077670-0.
  2. ^ Stifel, Michael (1544), Arithmetica integra (v latině), s. 31. Kopie stejné tabulky se dvěma dalšími položkami se objeví na str. 237 a další kopie rozšířená na záporné síly se objeví na str. 249b.
  3. ^ Joseph, G. G. (2011), The Crest of the Peacock: Non-European Roots of Mathematics (3. vyd.), Princeton University Press, str.352.
  4. ^ Viz např. Shparlinski, Igor (2013), Kryptografické aplikace teorie analytického čísla: složitost dolní hranice a pseudonáhodnost Pokrok v informatice a aplikované logice, 22, Birkhäuser, s. 35, ISBN  978-3-0348-8037-4.
  5. ^ Euler, Leonhard (1739), „Kapitola VII. De Variorum Intervallorum Receptis Appelationibus“, Tentamen novae theoriae musicae ex certissismis harmoniae principiis dilucide expositae (v latině), Petrohradská akademie, s. 102–112.
  6. ^ Tegg, Thomas (1829), "Binary logarithms", Encyklopedie v Londýně; nebo Univerzální slovník vědy, umění, literatury a praktické mechaniky: obsahující populární pohled na současný stav poznání, svazek 4, s. 142–143.
  7. ^ Batschelet, E. (2012), Úvod do matematiky pro vědce o životě, Springer, str. 128, ISBN  978-3-642-96080-2.
  8. ^ Například, Microsoft Excel poskytuje IMLOG2 funkce pro komplexní binární logaritmy: viz Bourg, David M. (2006), Vědecká a technická kuchařka Excel O'Reilly Media, str. 232, ISBN  978-0-596-55317-3.
  9. ^ Kolman, Bernard; Shapiro, Arnold (1982), "11.4 Vlastnosti logaritmů", Algebra pro studenty vysokých škol „Academic Press, s. 334–335, ISBN  978-1-4832-7121-7.
  10. ^ Například toto je notace použitá v Encyclopedia of Mathematics a Princetonský společník matematiky.
  11. ^ A b Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990], Úvod do algoritmů (2. vyd.), MIT Press a McGraw-Hill, str. 34, 53–54, ISBN  0-262-03293-7
  12. ^ A b Sedgewick, Robert; Wayne, Kevin Daniel (2011), Algoritmy, Addison-Wesley Professional, s. 185, ISBN  978-0-321-57351-3.
  13. ^ Chicago Style Style (25. vydání), University of Chicago Press, 2003, s. 530.
  14. ^ A b Knuth, Donald E. (1997), Základní algoritmy, Umění počítačového programování, 1 (3. vyd.), Addison-Wesley Professional, ISBN  978-0-321-63574-7, str. 11. Stejná notace byla ve 2. vydání stejné knihy z roku 1973 (str. 23), ale bez zásluhy Reingolda.
  15. ^ Trucco, Ernesto (1956), „Poznámka k informačnímu obsahu grafů“, Býk. Matematika. Biophys., 18 (2): 129–135, doi:10.1007 / BF02477836, PAN  0077919.
  16. ^ Mitchell, John N. (1962), „Počítačové násobení a dělení pomocí binárních logaritmů“, Transakce IRE na elektronických počítačích, EC-11 (4): 512–517, doi:10.1109 / TEC.1962.5219391.
  17. ^ Fiche, Georges; Hebuterne, Gerard (2013), Matematika pro inženýry, John Wiley & Sons, str. 152, ISBN  978-1-118-62333-6, V následujícím textu, pokud není uvedeno jinak, notace log X vždy znamená logaritmus k základně 2 z X.
  18. ^ Cover, Thomas M.; Thomas, Joy A. (2012), Základy teorie informace (2. vyd.), John Wiley & Sons, str. 33, ISBN  978-1-118-58577-1, Pokud není uvedeno jinak, vezmeme všechny logaritmy do základny 2.
  19. ^ A b Goodrich, Michael T.; Tamassia, Roberto (2002), Návrh algoritmu: základy, analýza a příklady internetu, John Wiley & Sons, str. 23, Jedním ze zajímavých a někdy i překvapivých aspektů analýzy datových struktur a algoritmů je všudypřítomná přítomnost logaritmů ... Jak je ve výpočetní literatuře zvykem, vynecháme psaní základny b logaritmu, když b = 2.
  20. ^ A b C Tafel, Hans Jörg (1971), Einführung in die digitale Datenverarbeitung [Úvod do digitálního zpracování informací] (v němčině), Mnichov: Carl Hanser Verlag, s. 20–21, ISBN  3-446-10569-7
  21. ^ Tietze, Ulrich; Schenk, Christoph (1999), Halbleiter-Schaltungstechnik (v němčině) (1. opravený dotisk, 11. vydání), Springer Verlag, str.1370, ISBN  3-540-64192-0
  22. ^ Bauer, Friedrich L. (2009), Počátky a základy výpočetní techniky: Ve spolupráci s Heinz Nixdorf MuseumsForum, Springer Science & Business Media, str. 54, ISBN  978-3-642-02991-2.
  23. ^ Pro DIN 1302 viz Brockhaus Enzyklopädie in zwanzig Bänden [Encyklopedie Brockhaus ve dvaceti svazcích] (v němčině), 11, Wiesbaden: F.A. Brockhaus, 1970, s. 554, ISBN  978-3-7653-0000-4.
  24. ^ Pro ISO 31-11 viz Thompson, Ambler; Taylor, Barry M (březen 2008), Příručka pro použití mezinárodního systému jednotek (SI) - vydání NIST Special Publication 811, 2008 - druhé vydání (PDF), NIST, str. 33.
  25. ^ Pro ISO 80000-2 viz „Veličiny a jednotky - Část 2: Matematické znaky a symboly používané v přírodních vědách a technologiích“ (PDF), Mezinárodní norma ISO 80000-2 (1. vyd.), 1. prosince 2009, část 12, Exponenciální a logaritmické funkce, s. 1. 18.
  26. ^ Van der Lubbe, Jan C. A. (1997), Teorie informací, Cambridge University Press, str. 3, ISBN  978-0-521-46760-5.
  27. ^ Stewart, Iane (2015), Zkrocení nekonečna, Quercus, str. 120, ISBN  9781623654733, v pokročilé matematice a přírodních vědách je jediným důležitým logaritmem přirozený logaritmus.
  28. ^ Leiss, Ernst L. (2006), Programátorův společník k analýze algoritmů, CRC Press, str. 28, ISBN  978-1-4200-1170-8.
  29. ^ Devroye, L.; Kruszewski, P. (1996), „Na Hortonově – Strahlerově čísle pro náhodné pokusy“, RAIRO Informatique Théorique et Applications, 30 (5): 443–456, doi:10.1051 / ita / 1996300504431, PAN  1435732.
  30. ^ Ekvivalentně, rodina s k odlišné prvky má nanejvýš 2k odlišné sady, s rovností, když se jedná o sadu energie.
  31. ^ Eppstein, David (2005), „Mřížková dimenze grafu“, European Journal of Combinatorics, 26 (5): 585–592, arXiv:cs.DS / 0402028, doi:10.1016 / j.ejc.2004.05.001, PAN  2127682.
  32. ^ Graham, Ronald L.; Rothschild, Bruce L.; Spencer, Joel H. (1980), Ramseyova teorie, Wiley-Interscience, s. 78.
  33. ^ Bayer, Dave; Diaconis, Persi (1992), „Trailing the rybet shuffle to its brir“, Annals of Applied Probability, 2 (2): 294–313, doi:10.1214 / aoap / 1177005705, JSTOR  2959752, PAN  1161056.
  34. ^ Mehlhorn, Kurt; Sanders, Peter (2008), "2.5 Příklad - binární vyhledávání", Algoritmy a datové struktury: Základní sada nástrojů (PDF), Springer, str. 34–36, ISBN  978-3-540-77977-3.
  35. ^ Roberts, Fred; Tesman, Barry (2009), Aplikovaná kombinatorika (2. vydání), CRC Press, str. 206, ISBN  978-1-4200-9983-6.
  36. ^ Sipser, Michael (2012), „Příklad 7.4“, Úvod do teorie výpočtu (3. vyd.), Cengage Learning, s. 277–278, ISBN  9781133187790.
  37. ^ Sedgewick & Wayne (2011), str. 186.
  38. ^ Cormen a kol., Str. 156; Goodrich & Tamassia, str. 238.
  39. ^ Cormen a kol., Str. 276; Goodrich & Tamassia, str. 159.
  40. ^ Cormen a kol., Str. 879–880; Goodrich & Tamassia, str. 464.
  41. ^ Edmonds, Jeff (2008), Jak přemýšlet o algoritmech, Cambridge University Press, str. 302, ISBN  978-1-139-47175-6.
  42. ^ Cormen a kol., Str. 844; Goodrich & Tamassia, str. 279.
  43. ^ Cormen a kol., Oddíl 28.2.
  44. ^ Causton, Helen; Quackenbush, John; Brazma, Alvis (2009), Analýza dat mikročipové genové exprese: Průvodce pro začátečníky, John Wiley & Sons, str. 49–50, ISBN  978-1-4443-1156-3.
  45. ^ Eidhammer, Ingvar; Barsnes, Harald; Eide, Geir Egil; Martens, Lennart (2012), Výpočtové a statistické metody pro kvantifikaci proteinů hmotnostní spektrometrií, John Wiley & Sons, str. 105, ISBN  978-1-118-49378-6.
  46. ^ A b Campbell, Murray; Greated, Clive (1994), Hudebníkův průvodce akustikou Oxford University Press, s. 78, ISBN  978-0-19-159167-9.
  47. ^ Randel, Don Michael, vyd. (2003), Harvardský hudební slovník (4. vydání), The Belknap Press of Harvard University Press, str. 416, ISBN  978-0-674-01163-2.
  48. ^ Francie, Robert (2008), Úvod do tělesné výchovy a sportu „Cengage Learning, str. 282, ISBN  978-1-4180-5529-5.
  49. ^ Allen, Elizabeth; Triantaphillidou, Sophie (2011), Manuál fotografie, Taylor & Francis, s. 228, ISBN  978-0-240-52037-7.
  50. ^ A b Davis, Phil (1998), Beyond the Zone System, CRC Press, str. 17, ISBN  978-1-136-09294-7.
  51. ^ Allen & Triantaphillidou (2011), str. 235.
  52. ^ Zwerman, Susan; Okun, Jeffrey A. (2012), Příručka společnosti pro vizuální efekty: Pracovní postup a techniky, CRC Press, str. 205, ISBN  978-1-136-13614-6.
  53. ^ Bauer, Craig P. (2013), Secret History: The Story of Cryptology, CRC Press, str. 332, ISBN  978-1-4665-6186-1.
  54. ^ A b Warren Jr., Henry S. (2002), Hacker's Delight (1. vyd.), Addison Wesley, str. 215, ISBN  978-0-201-91465-8
  55. ^ fls, Linux kernel API, kernel.org, vyvoláno 2010-10-17.
  56. ^ A b C d Majithia, J. C .; Levan, D. (1973), "Poznámka k výpočtům logaritmu základny 2", Sborník IEEE, 61 (10): 1519–1520, doi:10.1109 / PROC.1973.9318.
  57. ^ Stephenson, Ian (2005), „9.6 Funkce rychlého napájení, Log2 a Exp2“, Vykreslování výroby: návrh a implementace, Springer-Verlag, str. 270–273, ISBN  978-1-84628-085-6.
  58. ^ Warren Jr., Henry S. (2013) [2002], „11-4: Integer Logarithm“, Hacker's Delight (2. vyd.), Addison Wesley – Pearson Education, Inc., str. 291, ISBN  978-0-321-84268-8, 0-321-84268-5.
  59. ^ "7.12.6.10 Funkce log2", Specifikace ISO / IEC 9899: 1999 (PDF), str. 226.
  60. ^ Redfern, Darren; Campbell, Colin (1998), Příručka Matlab® 5 Springer-Verlag, str. 141, ISBN  978-1-4612-2170-8.

externí odkazy