Teorijska računarska nauka

Umetnički prikaz Tjuringove mašine.^[1]^[2]^[3] Tjuringove mašine se koriste za modelovanje opštih računarskih uređaja.

Teorijska računarska nauka, ili TCS, podskup je opšte računarske nauke i matematike koji se fokusira na više matematematičkih i računarskih tema, uključujući teoriju računanja, lambda račun^[4] i teoriju tipova.^[5]

TCS pokriva široku lepezu tema, uključujući algoritme, računarsku složenost, paralelno distributivno računanje, probabilističko računanje, kvantno računanje, teoriju automatizacije, teoriju informacija, kriptografiju, program semantike i strukture podataka, mašinsko učenje, računarsku biologiju, računsku ekonomiju, geometriju, računarsku teoriju brojeva i algebru. Rad na ovom području često se razlikuje po naglasku na matematičkoj tehnici i strogosti.

Na ovoj listi ACM-ov časopis Transakcije o teoriji računanja uključuje teoriju kodiranja i teoriju računarskog učenja, kao i teorijske aspekte računarske nauke u područjima kao što su baze podataka, pronalaženje informacija, ekonomski modeli i mreže. Uprkos tom širokom opsegu, "teorijski ljudi" u računarskoj nauci se identifikuju kao različiti od "primenjenih ljudi". Prvi se karakterišu kao da rade "(temeljniju)" nauku "koja leži u oblasti računalstva." Drugii "primenjeni ljudi" sugerišu da je nemoguće odvojiti teoriju i primenu. To znači da takozvani "teorijski ljudi" redovno koriste eksperimentalne nauke u manje teorijskim oblastima kao što je istraživanje softverskih sistema. To takođe znači da postoji više koordiniranja, nego međusobno isključive konkurencije između teorije i primene.

Istorija računarstva

Dok su logičko zaključivanje i matematički dokaz postojali ranije, Kurt Godel je 1931. dokazao svojom teoremom nepotpunosti da postoje osnovna ograničenja u vezi s tim da se izjave mogu dokazati ili odbaciti.

Ovi događaji doveli su do savremenog proučavanja logike i računanja, a zapravo i oblasti teorijske računarske nauke u celini. Teorija informacija je dodata matematičkoj teoriji komunikacije Clarie Shannon iz 1948. godine. U istoj deceniji, Donnald Hebb predstavio je matematički model učenja u mozgu. Uz montažu bioloških podataka koji podupiru ovu hipotezu sa nekim izmenama, uspostavljena su polja neuronskih mreža i paralelna distribuirana obrada. Godine 1971. Stephen Cook i nezavisno radeći Leonid Levin dokazali su da postoje praktični relevantni problemi koji su NP-komletni - značajan rezultat računarske teorije složenosti. S razvojemm kvantne mehanike na početku 20. veka došlo je do koncepcije da se matematička operacija može izvesti na celoj talasoj funkciji čestica. Drugim rečima, mogla bi se istovremeno računati funkcije na više stanja. To je dovelo do koncepta kvantnog računara u drugoj polovini 20. veka koji je započeo 1990. kada je Peter Shor pokazao da se takve metode mogu koristiti za faktor velikih brojeva u polinomijalnom vremenu, koji bi ukoliko se implementira, učinio najsavremeniji kriptografski sistem javnog ključa beskorisno nesigurnim.

Savremena teorijska istraživanja računarstva je zasnovana na ovim osnovnim događajima, ali obuhvata i mnoge druge matematičke i interdisciplinarne probleme koji su postavljeni, kao što je prikazano u nastavku:

P→Q

P = NP

Matematička logika Teorija automatizma Teorija brojeve Teorija grafova Kompatibilnost Teorija složenosti

GNITIRW-TERCES Г ├ x : Int Kriptografija Teorija tipa Teotija kategorije Računarska geometrija Kombinatorna optimizacija Kvantna komp. teotija

Algoritam

Algoritam je korak-po-korak postupak rešavanja. Algoritmi se koriste za obračun, obradu podataka i automatsko zaključivanje.

Algoritam je efikasna metoda koja se izražava kao konačna lista jasno definisanih instrukcija za izračunavanje funkcije. Polazeći od početnog stanja i početnog unosa (možda praznog), instrukcije opisuju računanje koje, kada se izvrši, prolazi kroz konačan broj dobro definisanih sukcesivnih stanja, a na kraju proizvodi "izlaz" i završava u konačnom završnom stanju. Prelaz iz jedneog stanja u drugo nije nužno determinističan; neki algoritmi, poznati kao randomizirani algoritmi, uključuju slučajni ulaz.

Struktura podataka

Struktura podataka je poseban način organizovanja podataka u računaru kako bi se mogli efikasno koristiti.

Različite vrste struktura podataka odgovaraju različitim vrstama aplikacija, a neke su vrlo specijalizovane za određene zadatke. Na primer, baze podataka koriste indekse B-stabla za male procente prikupljanja podataka i kompajlera i koriste dinamičke tabele sa rešenjima kao tabele potražnje.

Računarska teorija složenosti

Računarska teorija složenosti je grana teorije računarstva koja se fokusira na klasifikovanje računarskih problema u skladu sa njihovom težinom i povezivanje klasa jednih sa drugima. Problem se smatra nelogično teškim ako njegovo rešenje zahteva značajne resurse, bez obzira na algoritam koji se koristi. Teorija formalizuje ovu intuiciju, uvođenjem matematičkih modele računanja za proučavanje tih problema i kvantovanja količine resursa potrebnih za njihovo rešavanje, kao što su vreme i skladištenje. Takođe se koriste i druge mere složenosti, kao što su količina komunikacije (koristi se u komunikacijskoj složenosti), broj ulaza u sklopu (koristi se u složenosti sklopa) i broj procesora (koristi se u paralelnom računarstvu).

Distributivni račun

Distributivna računarska proučavanja distribuiraju sisteme. Distributivni sistem je softverski sistem u kojem komponente koje se nalaze na umreženim računarima komuniciraju i koordiniraju svoje postupke prenošenjem poruka. Komponente međusobno komuniciraju kako bi postigle zajednički cilj. Tri značajne karakteristike distributivnih sistema su: konkurentnost komponenti, nedostatak globalnog sata i nezavisni otkaz komponenata. Primeri distribuiranih sistema variraju od SOA-baziranih sistema preko masivnih multiigračkih onlajn aplikacija.

Paralelno računanje

Paralelno računanje je oblik računanja u kojem se istovremeno izvodi više operacija. Funkcioniše na principu da se veliki problemi često mogu podeliti na manje, a zatim se paralelno rešavati. Postoji nekoliko različitih oblika paralelnog računanja: bitni nivo, nivo instrukcija, podaci i paralelizam zadataka. Kako je potrošnja energije (i time i zagrevanje) računara postalo zabrinjavajuće poslednjih godina, paralelno računanje postalo je dominantna paradigma u računarskoj arhitekturi, uglavnom u obliku višejezgrenih procesora. Paralelni računarski programi su teži za pisnje od sekvencijalnih, jer uvode nekoliko novih klasa potencijalnih softverskih grešaka. Komunikacija i sinhronizacija između različitih potprograma obično su neke od najvećih prepreka za dobijanje dobrih performansi paralelnog programa.

Najveće moguće ubrzanje jednog programa kao rezultat paralelizacije poznat je kao Amdahlov zakon.

Veoma velika integracija

Veoma velika integracija (VLSI) je proces stvaranja integralnog kola (IC) kombinujući hilade tranzistora u jedan čip. VLSI je započeo sedamdesetih godina kada su se razvile složene poluprovodničke i komunikacijske tehnologije. Mikroprocesor je VLSI uređaj. Elektronsko kolo se može sastojati od procesora, RAM memorije, ROM memorije i dr. VLSI tehnologija omogićava da se sve ove tehnologije spakuju u jedan čip.

Mašinsko učenje

Mašinsko učenje je naučna disciplina koja se bavi izradom i proučavanjem algoritama koji mogu učiti iz podataka. Mašinsko učenje može se smatrati delom informatičke nauke i statistike. Ono ima snažne veze s veštačkom inteligencijom i optimizacijom, koje daju metode, teoriju i primenu na terenu. Primeri aplikacija uključuju filtriranje neželjenih poruka, optičko prepoznavanje znakova (OCR), pretraživače i računarski vid. Mašinsko učenje ponekad se povezuje sa rudarenjem podataka, iako se to više fokusira na istraživačku analizu podataka.

Računarska biologija

Računarska biologija uključuje razvoj i primenu analitičkih i teorijskih metoda, matematičkog modeliranja i računarske simulacijske tehnike za proučavanje bioloških, bihevioralnih i društvenih sistema. Područje je široko definisano i uključuje osnove računarstva, primenjene matematike, animacije, statistike, biohemije, hemije, biofizike, molekularne biologije, genetike, genomike, ekologije, evolucije, anatomije, neurologije i vizualizacije.

Računarska geometrija

Računarska geometrija je grana računarskih nauka posvećena proučavanju algoritama koji se mogu izraziti u vidu geometrije. Neki čisto geometrijski problemi proizlaze iz proučavanja računarskih geometrijskih algoritama, a takvi se problemi takođe smatraju delom računarske geometrije. Dok je moderna računarska geometrija nedavno razvijena, klasicna geometrija je jedna od najstarijih oblasti računarstva, sa istorijom koja se proteže do antike. Drevna preteča je sanskrtska rasprava Shulba Sutra, ili "Pravila akorda", knjiga algoritama napisanih u 800. pne.

Druge važne primene računarske geometrije uključuju robotiku (probleme pri planiranju ividljivosti), geografski informacioni sistemi (geometrijsko lociranje i pretraživanje, planiranje rute), dizajn integralnih kola (dizajn i verifikacija IC geometrije), računarsko inženjerstvo (CAE) (mrežna generacija), računarska vizija (3D rekonstrukcija).

Teorija informacija

Teorija informacija je grana primenjene matematike, elektrotehnike i računarske nauke koja uključuje kvantovanje informacija. Teoriju informacija razvio je Claude E. Shannon kako bi pronašao osnovne granice na operacijama obrade signala, kao što su kompresija podataka, pouzdano čuvanje i komuniciranje podataka. Primena osnovnih tema teorije informacija uklučuje kompresiju podataka bez gubitaka (npr.ZIP datoteke), kompresiju gubitka podataka (npr.MP3 i JPEG) i kodiranje kanala (npr. Za Digital Subscriber Line (DSL). Njen je uticaj bio presudan za uspeh Voyagerovih misija u svemir, izum kompakt diska, mobilnih telefona, razvoj Interneta, proučavanje lingvistike i ljudske percepcije, razumevanje crnih rupa, i brojna druga područja. Važne oblasti teorije informacija su izvorno kodiranje, kodiranje kanala, algoritamska teorija složenosti, algoritamska teorija informacija, informacijsko-teorijska sigurnost i mere informacija.

Kriptografija

Kriptografija je praksa i proučavanje tehnika sigurne komunikacije u prisustvu trećih strana (nazvanih protivnicima). Grubo govoreći, radi se o konstruirsanju i analiziranju protokola koji prevladavaju uticaj protivnika i koji se odnose na različite aspekte informacijske sigurnosti kao što su poverljivost podataka, integritet podataka, računarske lozinke, tačnost i neizvršenje. Savremena kriptografija se prepliće sa matematikom, računarstvom i elektrotehnikom. Primena kriptografije uključuje ATM kartice, i elektronsku trgovinu.

Kvantno računanje

Kvantni računar je računarski sistem koji za obradu podataka direktno koristi kvantno-mehaničke pojave, kao što su superpozicija i zaplet. Dok digitalni računari zahtevaju da se podaci kodiraju u binarne cifre (bitove), od kojih je svaka uvek u jednoj od dva određena stanja (0 ili 1), kvantno računanje koristi qubits (kvantne bitove), koji mogu biti u superpozicijama stanja. Teorijski model je kvantna Turingova masina, poznat kao univerzalni kvantni računar. Područje kvantnog računanja prvi put su uveli Jurij Manin 1980. i Richard Feynman 1982Od 2014. godine, kvantno računanje je još uvek u povoju, ali izvedeni su eksperimenti u kojima su kvantne računarske operacije izvršene na vrlo malom broju qubita. Mnoge nacionalne vlade i agencije za finansiranje podržavaju kvantno računarsko istraživanje kao što je kriptoanaliza za razvoj kvantnih računara, kako za civilnu tako i za nacionalnu bezbedbost.

Informaciona složenost

Informaciona kompleksnost (IBC) proučava optimalne algoritme i računarsku složenost za kontinuirane probleme. IBC proučava integraciju putanje, parcijalne diferencijalne jednačine, sisteme običnih diferencijalnih jednalina, nelinearne jednačine, integralne jednačine i vrlo visoku dimenzionalnu integraciju.

Računarska teorija brojeva

Računarska teorija brojeva, takođe poznata kao algoritamska teorija brojeva, je proučavanje algoritama za izvođenje brojnih teorijskih proračuna. Najpoznatiji problem u ovoj oblasti je faktorizacija celog broja.

Računarska algebra

Simbolički proračun Uređivanje Računarska algebra, koja se naziva i simboličko računanje ili algebarsko računanje, je naučna oblast koja se odnosi na proučavanje i razvoj algoritama i softvera za rad sa matematičkim izrazima i drugim matematičkim objektima).

Semantika programa

U teoriji programskog jezika, semantika je područje koje se bavi matematičkim istraživanjem značenja programskih jezika. To čini tako što ocenjuje značenje sintaktički pravilnih nizova definisanih određenim programskim jezikom. U slučaju ako bi procena bila da su nizovi sintaktički nepravilni, rezultat bi bio ne-izračunavanje.

Formalne metode

Formalne metode predstavljaju posebnu tehniku baziranu na matematici a služe za specifikaciju, razvoj i verifikaciju softverskih i hardverskih sistema. Upotreba formalnih metoda za dizajn softvera i hardvera motivisano je očekivanjem da, kao i kod drugih inženjerskih disciplina, obavljanje odgovarajuće matematičke analize može doprineti pouzdanosti i kvalitetu dizajna.

Teorija automata

Teorija automata je proučavanje apstraktnih mašina i automatizma, kao i računarskih problema koji se mogu rešiti koristeči ih.

Teorija kodiranja

Teorija kodiranja je proučavanje osobina kodova i njihovih sposobnosti za određenu aplikaciju. Kodovi se koriste za kompresiju podataka, kriptografiju, ispravljanje grešaka, a od nedavno i kod mrežnog kodiranja. Kodovi se proučavaju u raznim naučnim disciplinama, kao što su teorija informacija, elektrotehnika, matematika i , radi oblikovanja efikasnih i pouzdanih metoda prenosa podataka.

Teorija mašinskog učenja

Teorijski rezultati mašinskog učenja uglavnom se bave tipom induktivnog učenja pod nazivom nadgledano učenje. U nadgledranom učenju algoritmu se daju uzorci koji su označeni na neki koristan način. Na primer, uzorci mogu biti opisi gljiva, a nalepnice mogu biti jesu ili nisu jestive. Algoritam uzima ove prethodno označene uzorke i koristi ih da indukuje klasifikator. Cilj nadgledanog učenja za algoritam je optimizacija nekog izvršavanja kao što je smanjenje broja grešaka na novim uzorcima.

Reference

^ Minsky 1967:107 "In his 1936 paper, A. M. Turing defined the class of abstract machines that now bear his name. A Turing machine is a finite-state machine associated with a special kind of environment -- its tape -- in which it can store (and later recover) sequences of symbols," also Stone 1972:8 where the word "machine" is in quotation marks.
^ Stone 1972:8 states "This "machine" is an abstract mathematical model", also cf. Sipser 2006:137ff that describes the "Turing machine model". Rogers 1987 (1967):13 refers to "Turing's characterization", Boolos Burgess and Jeffrey 2002:25 refers to a "specific kind of idealized machine".
^ Sipser 2006:137 "A Turing machine can do everything that a real computer can do".
^ Turing, Alan M. (децембар 1937). „Computability and λ-Definability”. The Journal of Symbolic Logic. 2 (4): 153—163. JSTOR 2268280. S2CID 2317046. doi:10.2307/2268280.
^ Church, Alonzo (1940). „A formulation of the simple theory of types”. The Journal of Symbolic Logic. 5 (2): 56—68. JSTOR 2266170. S2CID 15889861. doi:10.2307/2266170.

Spoljašnje veze

SIGACT directory of additional theory links (archived 15 July 2017)
Theory Matters Wiki Архивирано на сајту Wayback Machine (19. јун 2017) Theoretical Computer Science (TCS) Advocacy Wiki
List of academic conferences in the area of theoretical computer science at confsearch
Theoretical Computer Science – StackExchange, a Question and Answer site for researchers in theoretical computer science
Computer Science Animated
Theory of computation at the Massachusetts Institute of Technology

[1] Minsky 1967:107 "In his 1936 paper, A. M. Turing defined the class of abstract machines that now bear his name. A Turing machine is a finite-state machine associated with a special kind of environment -- its tape -- in which it can store (and later recover) sequences of symbols," also Stone 1972:8 where the word "machine" is in quotation marks.

[2] Stone 1972:8 states "This "machine" is an abstract mathematical model", also cf. Sipser 2006:137ff that describes the "Turing machine model". Rogers 1987 (1967):13 refers to "Turing's characterization", Boolos Burgess and Jeffrey 2002:25 refers to a "specific kind of idealized machine".

[3] Sipser 2006:137 "A Turing machine can do everything that a real computer can do".

[4] Turing, Alan M. (децембар 1937). „Computability and λ-Definability”. The Journal of Symbolic Logic. 2 (4): 153—163. JSTOR 2268280. S2CID 2317046. doi:10.2307/2268280.

[church-5] Church, Alonzo (1940). „A formulation of the simple theory of types”. The Journal of Symbolic Logic. 5 (2): 56—68. JSTOR 2266170. S2CID 15889861. doi:10.2307/2266170.

[1]

[2]

[3]

[4]

[5]