Az elméleti számítógép-tudomány a tanulmány alapjainak logika és a matematika , a számítógép . A számítástechnika egyik ága . Általánosabban, a kifejezést a számítástechnikához kapcsolódó egyetemes igazságokra ( axiómákra ) összpontosító kutatási területek vagy részterületek jelölésére használják . Az elméleti informatikát matematikai és kevésbé empirikus megközelítés jellemzi a számítástechnikában, és célkitűzései nem mindig kapcsolódnak közvetlenül a technológiai kérdésekhez .
Sok tudományterület csoportosítható ezen diffúz név alatt, beleértve:
Ebben a részben az elméleti számítástechnika történetét adjuk meg, különböző források alapján:
Bertrand Russel , David Hilbert és George Boole logikusok voltak az elméleti számítástechnika úttörői. De a számítástechnika ezen ága főleg Alan Turing és Alonzo Church 1936-os munkájából merült fel , akik hivatalos számítási modelleket ( Turing-gépek és lambda-számítások ) vezettek be . Megmutatták, hogy léteznek univerzális gépek, amelyek képesek azonos típusú gépek szimulálására, például az univerzális Turing-gépek . 1938-ban Claude Shannon kimutatta, hogy a Boolean algebra megmagyarázza az áramkörök viselkedését elektromechanikus relékkel . 1948-ban Claude Shannon kiadta a kommunikáció matematikai elméletét , az információelmélet megalapozóját . 1949-ben bejelentette a Boole-áramkörök komplexitásának elméletének alapjait .
A programozás a számítógépek az idő nehéz volt. Például egy egyszerű művelet végrehajtása érdekében száz kábelt kellett csatlakoztatni vagy leválasztani az ENIAC számítógépéről .
Az 1950-es évek fontos hozzájárulása olyan programozási nyelvek létrehozása, mint a FORTRAN , a COBOL és a LISP , amelyek magas szintű konstrukciókat kínálnak az íráshoz:
A nyelvek és az automaták elmélete fontos téma az 1950-es években, mert lehetővé teszi a számítógépes nyelvek kifejező képességének és megvalósításának megértését. A véges állapotú gépeket és a halmozott automatákat formálisan definiálják. Ezután Michael Oser Rabin és Dana Stewart Scott matematikailag tanulmányozzák e modellek kifejezőerejét és határait.
1964-ben Noam Chomsky meghatározta Chomsky hierarchiáját . A nyelvek több osztálya ( normál nyelvek , algebrai nyelvek , összefüggésekkel rendelkező nyelvek, rekurzívan felsorolható nyelvek ) megfelelnek az elméleti gépek különféle típusainak ( állapotgépek , sejtautomaták , Turing-gép lineáris memóriája Turing-gép). A nyelvek és gépek ezen osztályainak különféle változatait tanulmányozzák.
Hartmanis , Lewis és Stearns és mások a nyelveket a számításukhoz szükséges idő és / vagy memória szerint osztályozzák. Ezek a komplexitáselmélet kezdetei .
Az 1970-es évek során a komplexitás elmélete kialakult. A komplexitás osztályok P és NP meghatározása; az NP-teljességet Stephen Cook és Leonid Levin függetlenül határozza meg . Richard Karp bemutatta az NP-teljes nyelvek fontosságát. A kérdés P = NP kérik, és a kutatók azt sejtette, hogy megoldható lenne keresztül közötti levelezés a Turing-gép és áramkörök.
Fejlesszen ki formális módszereket a programok ellenőrzésére is. Meghatározzuk a programozási nyelvek formális szemantikáját.
A kapcsolatok fejlesztése a relációs adatbázis modell és a relációk kiszámítása között is az adatbázisokban történő lekérdezések hatékony végrehajtása érdekében.
Ezek az évek az algoritmikában is virágzottak . Donald Knuth, mint Aho, Hopcroft és Ullman, nagyban befolyásolta az algoritmusok fejlődését.
Az 1980-as és 1990-es évek elősegítették a párhuzamos számítástechnika és az elosztott rendszerek fejlesztését .
Nem könnyű pontosan meghatározni, hogy mit kell érteni az "elméleti számítástechnika" alatt. A kifejezés inkább a számítógépes kérdések matematikai és formai szempontból történő megközelítésére utal, gyakran figyelmen kívül hagyva a számítás gyakorlati szempontjait. Ebben az értelemben az elméleti informatikát néha a diszkrét matematika egyik ágának tekintik . Céljait általában az a vágy jellemzi, hogy elvileg azonosítsák a számítógépek lehetőségeit és korlátait .
Az Algoritmusok és Számításelmélet Különleges Érdekcsoportja (SIGACT) , amely a Számítógépes Gépek Szövetségéhez (ACM) csatlakozik, és az elméleti számítógép kutatásának támogatására törekszik, széles körű meghatározást ad, amely olyan sokféle területet tartalmaz, mint az algoritmika és adatstruktúrák , a komplexitáselmélet , párhuzamosság , VLSI , gépi tanulás , a bioinformatika , algoritmikus geometria , információelmélet , kriptográfia , kvantum számítástechnika , elmélet Algorithmics számok és az algebra , a szemantika a programozási nyelvek , formális módszerek , automaták elmélete és a tanulmány a véletlenszerűség a számítástechnikában.
A kutatók francia elméleti számítógép-tudomány szerint vannak csoportosítva a GDR Informatique Matematika és tartsa be a francia Association alapjogi Informatikai , tagja a Société informatique de France a francia szint és tagja a EATCS európai szinten.
Az ACM SIGACT definíciója túlságosan korlátozott, mivel a felsorolás nem teljes és túl széles, mivel az említett területek többsége nem pusztán elméleti kérdésekre összpontosít.
Ez a tudományág megpróbálja új algoritmusokat felfedezni, fejleszteni és tanulmányozni a problémák nagyobb hatékonysággal történő megoldása érdekében.
Bizonyos érzékeny programok tökéletes megbízhatóságot igényelnek, és ennek eredményeként matematikai eszközöket fejlesztenek ki az algoritmika, a modellezés és az algebra között félúton annak érdekében, hogy lehetővé tegyék a programok és algoritmusok formális ellenőrzését.
Az információelmélet kezdetben Ronald A. Fisher munkájából ered . Ez a statisztikus teoretizálja az információkat a valószínűségelméletben és a mintákban. Technikailag az „információ” megegyezik a vizsgált valószínűségi törvény logaritmusának deriváltjának négyzetének átlagértékével. Cramer egyenlőtlenségéből kiindulva az ilyen "információ" értéke arányos a kapott következtetések alacsony változékonyságával. Más szavakkal, Fisher az információt a bizonyosság fokához kapcsolja. Más matematikai modellek hivatalosan kiegészítették és kibővítették az információk meghatározását.
Claude Shannon és Warren Weaver megerősítik a paradigmát. A telekommunikációs mérnökök, műszaki aggályaik arra késztették őket, hogy információkat mérjenek fel a kommunikáció alapjainak (és nem információelmélet) levezetése érdekében. A Mathematical Theory of Communication in 1948 , akkor modellezni információt, hogy tanulmányozza a megfelelő törvények: zaj, az entrópia és a káosz, az általános analógia törvényei energetika és a termodinamika.
Munkájuk, kiegészítve Alan Turing , Norbert Wiener és Von Neuman munkáját (hogy csak a főbbeket említsem ), alkotják az "információtudomány" kezdeti alapját. Az információelmélet főként két jellegzetes elképzelésen alapul, amelyek a bizonytalanság és az entrópia variációi („rendellenesség” a rend hiánya, tehát az információ hiánya szempontjából a figyelembe vett halmazban, ahol meghatározhatatlanság). Ezeknek az elveknek és más kemény tudományok elvének elvetésével a technológiák azzal foglalkoznak, hogy miként lehet megvalósítani, elrendezni és megvalósítani az emberi társadalom igényeinek megfelelő megoldásokat.
Egyes kutatók azt igyekeztek párhuzamot vonni fogalmai közötti entrópia a fizikában és az entrópia a számítástechnika a megszerzése érdekében a számítási készítmény a kozmológia és a fizikai valóság világunk, amely egyesek szerint nem talált kulcsok matematikai eszközöket, amelyek sejtautomaták .
Egyesek a számítástechnikában csak az információfeldolgozás automatizálásának technológiai változatát látják (ideértve az átvitelt és a szállítást is), és a "számítástechnika" kifejezések használatát tévesnek tartják, ezért ugyanazok az emberek inkább az "információs és kommunikációs technológiák" elnevezést használják, mert mondjuk, hogy jobban lefedi a tág értelemben vett számítástechnika különféle összetevőit (feldolgozó rendszerek, hálózatok stb.). Az "informatika" kifejezésnek ezt a nagyon korlátozó elképzelését nem mindenki osztja, ráadásul sok angolszász irigyli az "informatika" szó gazdagságát, és kölcsönbe kezdi.
A gráfelmélet számos diszkrét probléma modellezését teszi lehetővé: útvonalszámítások, erőforrás-allokációk, SAT-problémák ... A négy színű tételt a számítástechnika ezen ágának klasszikus eredményeként idézhetjük .
A komplexitás elmélete lehetővé teszi az algoritmusok aszimptotikus végrehajtási idejük szerinti osztályozását. Vagyis viselkedésüknek megfelelően, ha nagyon nagy adatokon használják őket. A számítástechnika ezen ágában található például a híres P = NP probléma .
A kiszámíthatóság elmélet célja, hogy jellemezze azokat a függvényeket, amelyeket egy algoritmus kiszámíthat. Valójában meg lehet mutatni, hogy vannak olyan funkciók, amelyeket a számítógép nem tud kiszámítani, ezért érdekes tudni, hogy melyek azok. Az elfoglalt hódprobléma vagy Ackermann funkciója klasszikus példa az ezen a területen vizsgált tárgyakra.
A nyelvek elmélete, amely gyakran az automaták elméletéhez kapcsolódik, az adott szókincsben található szavak halmazának felismerésével foglalkozik. Természetes nyelvű feldolgozó algoritmusokban használják, például: automatikus fordítás , automatikus dokumentumindexálás stb. valamint a mesterséges nyelvek, például a programozási nyelvek esetében: összeállítás, értelmezés.
A formális logika a számítógép alapvető eszköze, léteznek bizonyos típusú elméletek , a lambda számítás és az újraírás, mint a funkcionális programozás alapvető eszközei és az igazoló asszisztensek .