Tietojenkäsittelyteoria on tutkimuksen perustan logiikka ja matematiikka on tietokone . Se on tietotekniikan haara . Yleisemmin termiä käytetään osoittamaan tieteenalaan liittyviä tutkimusaloja tai -aloja, jotka keskittyvät universaaleihin totuuksiin ( aksioomiin ). Teoreettiselle tietojenkäsittelytieteelle on ominaista matemaattisempi ja vähemmän empiirinen lähestymistapa tietojenkäsittelytieteeseen, ja sen tavoitteet eivät aina liity suoraan teknologisiin kysymyksiin .
Monet tieteenalat voidaan ryhmitellä tämän hajautetun nimen alle, mukaan lukien:
Tässä osassa esitämme teoreettisen tietojenkäsittelytieteen historiaa, joka perustuu eri lähteisiin:
Logistiikat Bertrand Russel , David Hilbert ja George Boole olivat teoreettisen tietojenkäsittelytieteen edelläkävijöitä. Mutta tämä tietojenkäsittelytieteen ala syntyi pääasiassa Alan Turingin ja Alonzo Churchin työstä vuonna 1936, jotka esittivät muodolliset laskentamallit ( Turingin koneet ja lambda-laskelmat ). He ovat osoittaneet universaalikoneiden olemassaolon, jotka pystyvät simuloimaan kaikkia samantyyppisiä koneita, esimerkiksi universaalit Turingin koneet . Vuonna 1938 Claude Shannon osoitti, että Boolen algebra selittää piirien käyttäytymisen sähkömekaanisilla releillä . Vuonna 1948 Claude Shannon julkaisi viestinnän matemaattisen teorian, tietoteorian perustajan . Vuonna 1949 hän ilmoitti Boolen piirien monimutkaisuuden teorian perustan .
Ohjelmointi on tietokoneiden aika oli vaikeaa. Esimerkiksi yksinkertaisen toimenpiteen suorittamiseksi oli tarpeen liittää tai irrottaa sata kaapelia ENIAC- tietokoneesta .
Tärkeä merkitys 1950-luvulta on ohjelmointikielien, kuten FORTRAN , COBOL ja LISP , luominen , jotka tarjoavat korkean tason rakenteita kirjoittamista varten:
Teoria kielten ja automaattien on tärkeä aihe vuonna 1950, koska sen avulla ymmärtää ekspressiivisyyden tietokonekielten ja niiden toteuttamisesta. Äärelliset tilakoneet ja pinotut automaatit on määritelty muodollisesti. Sitten Michael Oser Rabin ja Dana Stewart Scott tutkivat matemaattisesti näiden mallien ilmaisuvoimaa ja rajoja.
Vuonna 1964 Noam Chomsky määritteli Chomskyn hierarkian . Useita luokkia kielillä ( säännöllisten kielten , algebrallinen kielet , kieliä yhteyksissä, kielet rekursiivisesti numeroituva ) vastaavat erilaisia teoreettisia koneen ( -tilakonetta , solun automaatit , Turingin kone lineaarinen muisti Turing kone). Näiden kieli- ja koneluokkien erilaisia variantteja tutkitaan.
Hartmanis , Lewis ja Stearns ja muut luokittelevat kielet niiden laskemiseen tarvittavan ajan ja / tai muistin mukaan. Nämä ovat monimutkaisuuden teorian alku .
1970-luvulla monimutkaisuuden teoria kehittyi. Monimutkaisuus luokat P ja NP on määritelty; NP-täydellisyys on määritelty itsenäisesti Stephen Cook ja Leonid Levin . Richard Karp osoitti NP-täydellisten kielten tärkeyden. Kysymys P = NP kysytään ja tutkijat arvelevat, että se voitaisiin ratkaista Turingin koneiden ja piirien vastaavuuden avulla.
Kehitä myös muodollisia menetelmiä ohjelmien tarkistamiseksi. Määritämme virallisen semantiikan ohjelmointikielille.
Myös relaatiotietokantamallin ja suhteiden laskennan välisiä yhteyksiä kehitetään , jotta tietokannoissa tehtävät kyselyt voidaan suorittaa tehokkaasti.
Nämä vuodet ovat olleet kukoistavia myös algoritmeissa . Donald Knuth on vaikuttanut suuresti algoritmien kehitykseen, kuten Aho, Hopcroft ja Ullman.
1980- ja 1990-luvut edistivät rinnakkaisten laskenta- ja hajautettujen järjestelmien kehittämistä .
Ei ole helppoa määritellä tarkasti, mitä "teoreettisella tietojenkäsittelyllä" tarkoitetaan. Pikemminkin termi viittaa tapaan lähestyä tietokoneongelmia matemaattisemmalla ja muodollisemmalla näkökulmalla, jättämällä usein huomiotta laskennan käytännön näkökohdat. Tässä mielessä teoreettista tietojenkäsittelyä pidetään joskus erillisen matematiikan haarana . Sen tavoitteet ovat yleensä ominaista halu tunnistaa periaatteessa mahdollisuudet ja rajoitukset tietokoneita .
Special Interest Group algoritmeihin ja laskenta Theory (SIGACT) , joka kokoaa sidoksissa Association for Computing Machinery (ACM) ja jolla tuetaan tutkimusta Tietojenkäsittelyteoria määritellään laajasti, joka sisältää erilaisia aloja, kuten Algoritmiikan ja tietorakenteita , vaativuus , rinnakkaisuus , VLSI , koneoppiminen , bioinformatiikka , algoritmisen geometria , informaatioteorian , kryptografia , kvanttilaskennalla , teoria Algoritmiikan numeroita ja algebran , semantiikka ohjelmointikielet , muodollinen menetelmiä , automaattien teoria ja tutkimus satunnaisuuden tietotekniikassa.
Ranskan teoreettisen tietojenkäsittelytieteen tutkijat on ryhmitelty GdR Informatique Mathematics -sovellukseen, ja he ovat liittyneet Ranskan perustietotekniikan liittoon , joka on Ranskan Société informatique de France -yrityksen jäsen ja Euroopan tason EATCS- jäsen .
ACM SIGACTin antama määritelmä on sekä liian rajallinen, koska luettelo ei ole tyhjentävä että liian laaja, koska useat mainituista aloista eivät keskity pelkästään puhtaasti teoreettisiin kysymyksiin.
Tämä tieteenala yrittää löytää, parantaa ja tutkia uusia algoritmeja ongelmien ratkaisemiseksi tehokkaammin.
Tietyt arkaluonteiset ohjelmat vaativat täydellisen luotettavuuden, ja siksi matemaattiset työkalut algoritmien, mallinnuksen ja algebran puoliväliin kehitetään, jotta ohjelmat ja algoritmit voidaan muodollisesti todentaa.
Tietoteoria on alun perin tullut Ronald A.Fisherin työstä . Tämä tilastotieteilijä teorioi tietoja todennäköisyyksien ja näytteiden teoriassa. Teknisesti "informaatio" on yhtä suuri kuin tutkitun todennäköisyyslain logaritmin johdannaisen neliön keskiarvo. Cramerin eriarvoisuuden perusteella tällaisen "tiedon" arvo on verrannollinen tuloksena olevien johtopäätösten vähäiseen vaihtelevuuteen. Toisin sanoen Fisher vertaa tietoja varmuuden tasoon. Muut matemaattiset mallit ovat virallisesti täydentäneet ja laajentaneet tiedon määritelmää.
Claude Shannon ja Warren Weaver vahvistavat paradigmaa. Televiestintäinsinöörien tekniset huolenaiheet ovat johtaneet siihen, että he haluavat mitata tietoa johtaakseen viestinnän perusteet (eikä tietoteoriaan). Vuonna Theory Mathematical of Communication vuonna 1948 he mallintavat tietoja tutkiakseen vastaavia lakeja: melua, entropiaa ja kaaosta, analogisesti energian ja termodynamiikan laeille.
Heidän työnsä, täydentäen Alan Turingin , Norbert Wienerin ja Von Neumanin työtä (vain tärkeimmät), muodostaa "tietojenkäsittelytieteen" perustan. Informaatioteoria perustuu pääasiassa kahteen luonteenomaiseen käsitteeseen, jotka ovat epävarmuuden ja entropian vaihtelu ("häiriö" järjestyksen ja siten tiedon puuttumisen merkityksessä tarkasteltavassa joukossa, missä määrittelemättömyys). Hylkäämällä nämä periaatteet ja muiden kovien tieteiden periaatteet tekniikat käsittelevät kuinka toteuttaa, järjestää ja toteuttaa ratkaisuja vastaamaan ihmisyhteiskunnan tarpeita.
Jotkut tutkijat yrittävät rinnastaa käsitteet entropia on fysiikan ja entropia on tietojenkäsittelytieteen vuonna saamiseksi laskennallisen muotoilu ja kosmologian ja fyysisen todellisuuden maailmamme joista jotkut väittävät löytäisivät avaimet matemaattisia työkaluja, jotka ovat soluautomaatit .
Jotkut tietotekniikassa näkevät vain teknisen muunnelman tietojenkäsittelyn automatisoinnista (mukaan lukien siirto ja kuljetus) ja pitävät termien "tietojenkäsittely" käyttöä virheellisenä, joten samat ihmiset pitävät parempana nimitystä "tieto- ja viestintätekniikka", koska he sanotaan, että se kattaa paremmin tietojenkäsittelyn eri osat (käsittelyjärjestelmät, verkot jne.) laajassa merkityksessä. Tätä hyvin rajoittavaa näkemystä termistä "informatiikka" eivät ole kaikki samaa mieltä, ja lisäksi monet anglosaksit kadehtivat sanan "informatiikka" rikkautta ja alkavat lainata sitä.
Graafiteoria antaa mahdollisuuden mallintaa monia erillisiä ongelmia: polkulaskelmat, resurssien allokoinnit, SAT-ongelmat ... Voimme mainita nelivärisen lauseen tämän tietojenkäsittelytieteen klassisen tuloksen.
Kompleksiteoria mahdollistaa algoritmien luokittelun niiden asymptoottisen suoritusajan mukaan. Toisin sanoen heidän käyttäytymisensä mukaan käytettäessä erittäin suuria tietoja. Esimerkiksi tässä tietojenkäsittelytieteen haarassa sijaitsee kuuluisa ongelma P = NP .
Laskennateorian tarkoituksena on karakterisoida funktiot, jotka algoritmi voi laskea. On todellakin mahdollista osoittaa, että on olemassa toimintoja, joita tietokone ei voi laskea, ja siksi on mielenkiintoista tietää, mitkä niistä ovat. Kiireinen majava- ongelma tai Ackermannin tehtävä ovat klassisia esimerkkejä tällä alalla tutkituista kohteista.
Kieliteoria, joka liittyy usein automaattien teoriaan, koskee sanaryhmien tunnistamista tietyssä sanastossa. Sitä käytetään luonnollisen kielen käsittelyalgoritmeissa, esimerkiksi: automaattinen käännös , automaattinen asiakirjojen indeksointi jne. samoin kuin tekokielillä, kuten ohjelmointikielillä: kokoaminen, tulkinta.
Muodollinen logiikka on keskeinen väline tietokoneen, on olemassa erityisiä tyyppisiä teoriaan , The lambdakalkyyli ja kirjoittamasta kuin perusvälineet funktionaalisen ohjelmoinnin ja todiste avustajia .