Informationsteori

Informationsteori er en gren af anvendt matematik , radioteknik (signalbehandlingsteori ) og datalogi , der vedrører måling af mængden af information , dens egenskaber og etablering af begrænsende forhold for datatransmissionssystemer. Som enhver matematisk teori opererer teorien med matematiske modeller og ikke med rigtige fysiske objekter (kilder og kommunikationskanaler ). Anvender hovedsageligt det matematiske apparat for sandsynlighedsteori og matematisk statistik .

De vigtigste grene af informationsteori er kildekodning ( komprimerende kodning ) og kanalkodning ( støjkorrigerende ). Informationsteori er tæt forbundet med informationsentropi , kommunikationssystemer, kryptografi og andre relaterede discipliner.

Feltet er i skæringspunktet mellem matematik , statistik , datalogi , fysik , neurovidenskab , informationsteknik og elektroteknik . Teorien har også fundet anvendelser på andre områder, herunder statistisk inferens , naturlig sprogbehandling , kryptografi , neurovidenskab [1] , menneskesyn [2] , evolution [3] og funktionen [4] af molekylære koder ( bioinformatik ), statistisk model selektion [5] , termisk fysik [6] , kvanteberegning , lingvistik , plagiatdetektion [7] , mønstergenkendelse og anomalidetektion [8] . Vigtige underområder af informationsteori omfatter datakomprimering , kanalkodning , algoritmisk kompleksitetsteori , algoritmisk informationsteori , informationsteoretisk sikkerhed, Gray's relationelle analyse og informationsmåling.

Introduktion

Fremkomsten af informationsteori er forbundet med udgivelsen af Claude Shannon af værket " Matematical Theory of Communication " i 1948 . Fra Shannons synspunkt er informationsteori en gren af den matematiske kommunikationsteori. Informationsteori sætter hovedgrænserne for mulighederne for informationstransmissionssystemer, sætter de indledende principper for deres udvikling og praktiske implementering. Rækken af problemer med informationsteori præsenteres ved hjælp af et blokdiagram, et typisk system til transmission eller lagring af information.

I skemaet er en kilde ethvert objekt i universet , der genererer beskeder, der skal flyttes i rum og tid . Uanset den oprindelige fysiske karakter konverteres alle meddelelser, der skal transmitteres, normalt til form af elektriske signaler , sådanne signaler betragtes som output fra kilden. Kildekoderen repræsenterer informationen i den mest kompakte form. Kanalkoderen behandler informationen for at beskytte meddelelser mod interferens under transmission over kommunikationskanalen eller mulige forvrængninger under informationslagring. Modulatoren konverterer meddelelserne genereret af kanalkoderen til signaler i overensstemmelse med den fysiske natur af kommunikationskanalen eller informationslagringsmediet. Informationsformidlingsmediet ( kommunikationskanalen ) introducerer tilfældig støj i informationstransmissionsprocessen, som forvrænger budskabet og derved gør det svært at læse. Blokkene placeret på modtagersiden udfører de omvendte operationer og giver modtageren information i en form, der er let at forstå .

Historie

Informationsteoriens fødsel forbindes ofte med Claude Shannon 's placering i juli-oktober 1948 af et værk i det amerikanske telefonselskab Bell Systems tidsskrift under titlen "Mathematical Theory of Communication". Men det er værd at nævne, at bidraget til formuleringen og konstruktionen af informationsteori også blev givet af mange andre fremtrædende videnskabsmænd. Shannon selv skrev i begyndelsen af sin artikel "Nogle af de vigtigste bestemmelser i denne teori findes i de vigtige værker af Nyquist og Hartley . På nuværende tidspunkt er teorien blevet udvidet til at omfatte en række nye faktorer, især påvirkningen af støj i kanalen.

Grundlæggende udviklede Shannon retningen for Hartleys arbejde, ved at bruge begrebet "information", men udtrykket i sig selv forklarer ikke, det foreskriver kun, at beskeder kan have en form for "betydning", det vil sige henvise til et system, der har sin egen fysisk eller spekulativ essens ( kybernetisk system). Shannons teori blev oprindeligt betragtet som et præcist formuleret matematisk problem og gjorde det muligt at bestemme gennemløbet af en støjende kommunikationskanal.

Datakodning

Kodning er processen med at overføre en meddelelse ved input af en kommunikationskanal til en meddelelseskode ved output, mens meddelelsens informationsværdi skal forblive uændret. I informationsteori kan der skelnes mellem følgende afsnit:

1. Kodning af diskrete kilder (tabsfri datakodningsmodel).

2. Datakodning, der sikrer deres fejlfri transmission over en støjende kanal.

En kode er unikt afkodebar, hvis en sekvens af tegn fra kodens alfabet (og for det meste 0'er og 1'er) er opdelt i separate ord. Hvis ingen af kodeordene er begyndelsen på et andet, kaldes koden en præfikskode, og den er unikt afkodelig. Derfor er præfiks en tilstrækkelig, men ikke nødvendig betingelse for unik afkodning. Præfikskravet begrænser mængden af længder af kodeord og gør det ikke muligt at vælge kodeord, der er for korte. En nødvendig og tilstrækkelig betingelse for eksistensen af en præfiksvolumenkode med kodeordslængder er opfyldelsen af Krafts ulighed: $M$ $l_1,...,l_M$

\sum _{i=1}^{M}{2}^{-l_{i}}\leqslant {1}

Det er også nødvendigt at overveje Shannon-Fano-koden - en algoritme til præfiks ikke-ensartet kodning. Denne indkodningsmetode bruger redundansen af meddelelsen, som ligger i den uensartede frekvensfordeling af tegnene i dets alfabet, det vil sige, den erstatter koderne for hyppigere tegn med korte binære sekvenser og koderne for sjældnere tegn med længere binære sekvenser. Overvej en kilde, der vælger bogstaver fra et sæt med sandsynligheder . Vi antager, at bogstaverne er ordnet i faldende rækkefølge af sandsynligheder ( ). Kodeordet i Shannon-koden for en besked med et tal er en binær sekvens, som er de første cifre efter decimaltegnet i den binære notation af tallet : $X=M$ $om eftermiddagen$ ${p_1}\geqslant {p_2}\geqslant {p_M}$ $M$ $l=-\log {p_{m))$ $q_M$

{q_{M}}=\sum _{i=1}^{M-1}p_{i}

3. Datakodning for systemer med mange brugere beskriver den optimale interaktion mellem abonnenter ved hjælp af en fælles ressource, for eksempel en kommunikationskanal.

Se også

Noter

↑ F. Rieke; D. Krigsland; R Ruyter van Steveninck; W Bialek. Spikes: Exploring the Neural Code (ubestemt) . - The MIT press, 1997. - ISBN 978-0262681087 .
↑ Delgado-Bonal, Alfonso; Martin-Torres, Javier. Menneskets syn bestemmes ud fra informationsteori // Videnskabelige rapporter. - 2016. - 3. november ( bind 6 , nr. 1 ). — ISSN 2045-2322 . - doi : 10.1038/srep36038 . - . Arkiveret fra originalen den 24. februar 2021.
↑ jf; Huelsenbeck, JP; Ronquist, F.; Nielsen, R.; Bollback, JP Bayesiansk slutning om fylogeni og dens indvirkning på evolutionær biologi (engelsk) // Science : journal. - 2001. - Bd. 294 , nr. 5550 . - S. 2310-2314 . - doi : 10.1126/science.1065889 . - .
↑ Allikmets, Rando; Wasserman, Wyeth W.; Hutchinson, Amy; Smallwood, Philip; Nathans, Jeremy; Rogan, Peter K. Thomas D. Schneider , Michael Dean (1998) Organisation af ABCR-genet: analyse af promotor- og splejsningsforbindelsessekvenser ] // Gene : journal. - Elsevier , 1998. - Vol. 215 , nr. 1 . - S. 111-122 . - doi : 10.1016/s0378-1119(98)00269-8 . Arkiveret fra originalen den 21. august 2008.
↑ Burnham, KP og Anderson DR (2002) Model Selection and Multimodel Inference: A Practical Information-Theoretic Approach, Second Edition (Springer Science, New York) ISBN 978-0-387-95364-9 .
↑ Jaynes, ET Informationsteori og statistisk mekanik // Phys . Rev. : journal. - 1957. - Bd. 106 , nr. 4 . — S. 620 . - doi : 10.1103/physrev.106.620 . - . Arkiveret fra originalen den 30. august 2011.
↑ Bennett, Charles H.; Li, Ming; Mor, Bin. Kædebreve og evolutionære historier (engelsk) // Scientific American . - Springer Nature , 2003. - Vol. 288 , nr. 6 . - S. 76-81 . - doi : 10.1038/scientificamerican0603-76 . — . — PMID 12764940 . Arkiveret fra originalen den 7. oktober 2007.
↑ David R. Anderson. Lidt baggrund om, hvorfor folk i de empiriske videnskaber måske ønsker at forstå de informationsteoretiske metoder bedre (pdf) (1. november 2003). Hentet 23. juni 2010. Arkiveret fra originalen 23. juli 2011. (ubestemt)

Litteratur

Kudryashov B. D. Information Theory, St. Petersburg State University NRU ITMO
Leontiev VK , Gordeev DA Kombinatoriske aspekter af informationsteori . M.: MIPT , 2019.
Fursov V. A. Forelæsninger om informationsteori ISBN 5-7883-0458-X
Claude E. Shannon , Warren Weaver. Den matematiske teori om kommunikation. Univ of Illinois Press, 1963. ISBN 0-252-72548-4
Thomas M. Cover , Joy A. Thomas . Elementer af informationsteori New York: Wiley, 1991.ISBN 0-471-06259-6
R. Landauer , Information er fysisk proc. Workshop om fysik og beregning PhysComp'92 ( IEEE Comp. Sci.Press, Los Alamitos, 1993) pp. 1-4.
Maxwell's Demon: Entropy, Information, Computing, H.S. Leff og A.F. Rex, Editors, Princeton University Press , Princeton, NJ (1990). ISBN 0-691-08727-X
Shannon K. Arbejder med informationsteori og kybernetik. — M.: Udg. udenlandsk lit., 1963. - 830 s.
Kolmogorov AN Tre tilgange til definitionen af begrebet "informationsmængde", Probl. peredachi inform., 1 :1 (1965), 3-11
Mackay, David. Informationsteori, inferens og læringsalgoritmer . - Cambridge University Press, 2003. - ISBN 9780521642989 .

Links

Informationsteori // Encyclopedia " Krugosvet ".
Norbert Wiener . "Kybernetik eller kontrol og kommunikation i dyr og maskine"
K. Shannon . "Bandwagon"
Vigtige publikationer i informationsteori (eng.)
Traditionelle tilgange til informationskvantificering
Synergetisk informationsteori
Holevo A. S. Introduktion til kvanteinformationsteori
Holevo A. S. Kvantesystemer , kanaler, information (c2) M.: MTsNMO , 2014, 327 s. (På forlagets portal, pdf, 2M)
compression.ru
Elektronisk lærebog om informationsteori
Elektronisk lærebog om informationsteori

Ordbøger og encyklopædier

I bibliografiske kataloger
BNE : XX527336 BNF : 119321069 GND : 4026927-9 J9U : 987007550715205171 LCCN : sh85066289 LNB : 000053186 NDL : 00575012 NKC : ph126560

Informatikkens hovedretninger
Matematiske grundlag	matematisk logik mængdeteori talteori grafteori Typeteori Kategori teori Beregningsmatematik Informationsteori Kombinatorik Algebra af logik
Teori om algoritmer	Automateteori Beregnelighedsteori Beregningsmæssig kompleksitetsteori Teori om kvanteberegning
Algoritmer , datastrukturer	Algoritmeanalyse Udvikling af algoritmer Beregningsgeometri
Programmeringssprog , compilere	Parser Tolk proceduremæssig programmering Objektorienteret programmering Funktionel programmering Logisk programmering Programmeringsparadigmer
Samtidig og parallel computing , distribuerede systemer	multibearbejdning Grid computing
Software engineering	Kravanalyse Software design Programmering Formelle metoder Software test Softwareudvikling
Systemarkitektur	Computer arkitektur Computerenhed Operativ system
Telekommunikation , netværk	computer lyd Routing Netværkstopologi Kryptografi
Database	Databasestyringssystemer Relationelle databaser SQL Transaktioner Databaseindeks data mining
Kunstig intelligens	Automatisk generering af domme Beregningslingvistik computersyn evolutionær modellering Ekspertsystemer Maskinelæring naturlig sprogbehandling Robotik
Computer grafik	Visualisering computer animation Billedbehandling
Menneske-computer interaktion	Offentlig tilgængelighed af computeren Brugergrænseflader bærbar computer Pervasive Computing Virtual reality
videnskabelig databehandling	kunstigt liv bioinformatik kognitiv videnskab Beregningskemi Beregningsmæssig neurovidenskab Beregningsfysik Beregningsalgoritmer Symbolsk matematik
Bemærk: Datalogi kan også opdeles i forskellige emner eller grene i henhold til ACM Computing Classification System .