Teoretyczny informatyka jest badanie fundamentów logiki i matematyki na komputerze . To dziedzina informatyki . Mówiąc bardziej ogólnie, termin ten jest używany do określania dziedzin lub poddziedzin badań skoncentrowanych na uniwersalnych prawdach ( aksjomatach ) związanych z informatyką. Informatyka teoretyczna charakteryzuje się bardziej matematycznym, a mniej empirycznym podejściem do informatyki, a jej cele nie zawsze są bezpośrednio związane z zagadnieniami technologicznymi .
Wiele dyscyplin można zgrupować pod tą rozproszoną nazwą, w tym:
W tej sekcji podajemy historię informatyki teoretycznej na podstawie różnych źródeł:
Logicy Bertrand Russel , David Hilbert i George Boole byli pionierami informatyki teoretycznej. Ale ta gałąź informatyki wyrosła głównie z prac Alana Turinga i Alonzo Churcha w 1936 roku, którzy wprowadzili formalne modele obliczeń ( maszyny Turinga i rachunek lambda ). Wykazali istnienie uniwersalnych maszyn zdolnych do symulowania wszystkich maszyn tego samego typu, na przykład uniwersalnych maszyn Turinga . W 1938 roku Claude Shannon wykazał, że algebra Boole'a wyjaśnia zachowanie obwodów z przekaźnikami elektromechanicznymi . W 1948 roku Claude Shannon opublikował Matematyczną teorię komunikacji , twórcę teorii informacji . W 1949 roku ogłosił podstawy teorii złożoności obwodów Boole'a .
Programowanie z komputerami czas był trudny. Np. Konieczne było podłączenie lub odłączenie stu kabli w komputerze ENIAC w celu wykonania prostej operacji.
Ważnym wkładem lat pięćdziesiątych XX wieku jest stworzenie języków programowania, takich jak FORTRAN , COBOL i LISP , które oferują konstrukcje wysokiego poziomu do pisania:
Teoria języków i automatów jest ważnym tematem w 1950 roku, ponieważ pozwala zrozumieć wyrazistość języków komputerowych i ich realizacji. Maszyny skończone i automaty piętrowe są formalnie zdefiniowane. Następnie Michael Oser Rabin i Dana Stewart Scott matematycznie badają siłę ekspresji i ograniczenia tych modeli.
W 1964 roku Noam Chomsky zdefiniował hierarchię Chomsky'ego . Kilka klas języków ( języki regularne , języki algebraiczne , języki z kontekstów, języków rekurencyjnie przeliczalny ) odpowiadają różnych typów maszyn teoretycznej ( maszyn stanowych , automatów komórka , maszyna Turinga liniowy pamięci maszyny Turinga). Badane są różne warianty tych klas języków i maszyn.
Hartmanis , Lewis i Stearns i inni klasyfikują języki według czasu i / lub pamięci potrzebnej do ich obliczenia. To są początki teorii złożoności .
XX wieku rozwinęła się teoria złożoności . Do klasy złożoności P i NP zostały określone; NP-zupełności jest definiowany niezależnie przez Stephen Cook i Leonid Levin . Richard Karp zademonstrował znaczenie języków NP-pełnych. Zadano pytanie P = NP, a naukowcy przypuszczali, że można je rozwiązać za pomocą korespondencji między maszynami Turinga i obwodami.
Opracuj także formalne metody sprawdzania programów. Definiujemy semantykę formalną dla języków programowania.
Rozwija się również powiązania między relacyjnym modelem bazy danych a obliczaniem relacji , w celu sprawnego wykonywania zapytań w bazach danych.
Te lata kwitły również w algorytmice . Donald Knuth znacząco wpłynął na rozwój algorytmów, podobnie jak Aho, Hopcroft i Ullman.
Lata 80-te i 90-te sprzyjały rozwojowi obliczeń równoległych i systemów rozproszonych .
Nie jest łatwo zdefiniować dokładnie, co rozumie się pod pojęciem „informatyka teoretyczna”. Termin ten odnosi się raczej do sposobu podejścia do zagadnień komputerowych z bardziej matematycznego i formalnego punktu widzenia, często pomijając bardziej praktyczne aspekty informatyki. W tym sensie informatyka teoretyczna jest czasami postrzegana jako gałąź matematyki dyskretnej . Jego cele charakteryzują się generalnie chęcią zidentyfikowania w zasadzie możliwości i ograniczeń komputerów .
Grupa Specjalnych Interesów ds.Algorytmów i Teorii Obliczeń (SIGACT) , zrzeszająca stowarzyszenie Association for Computing Machinery (ACM) i zajmująca się wspieraniem badań w dziedzinie komputera teoretycznego, podaje szeroką definicję obejmującą obszary tak różnorodne, jak algorytmika i struktury danych , teoria złożoności , równoległość , VLSI , uczenie maszynowe , bioinformatyka , geometria algorytmiczna , teoria informacji , kryptografia , obliczenia kwantowe , teoria algorytmiki liczb i algebry , semantyka języków programowania , metody formalne , teoria automatów i badanie losowości w informatyce.
Naukowcy francuskiej informatyki teoretycznej są zgrupowani w GdR Informatique Mathematics i należą do Francuskiego Stowarzyszenia Informatyki Podstawowej , członka Société informatique de France na poziomie francuskim i członka EATCS na poziomie europejskim.
Definicja podana przez ACM SIGACT jest zarówno zbyt ograniczona, że lista nie jest wyczerpująca, jak i zbyt szeroka, ponieważ kilka z wymienionych dziedzin koncentruje się nie tylko na kwestiach czysto teoretycznych.
Ta dyscyplina stara się odkrywać, ulepszać i badać nowe algorytmy, aby rozwiązywać problemy z większą wydajnością.
Niektóre wrażliwe programy wymagają doskonałej niezawodności, dlatego narzędzia matematyczne w połowie drogi między algorytmami, modelowaniem i algebrą są opracowywane, aby umożliwić formalną weryfikację programów i algorytmów.
Teoria informacji początkowo wynika z prac Ronalda A. Fishera . Ten statystyk teoretyzuje informacje w swojej teorii prawdopodobieństw i prób. Z technicznego punktu widzenia „informacja” jest równa średniej wartości kwadratu pochodnej logarytmu badanego prawa prawdopodobieństwa. Z nierówności Cramera wartość takiej „informacji” jest proporcjonalna do małej zmienności wynikających z niej wniosków. Innymi słowy, Fisher odnosi informacje do stopnia pewności. Inne modele matematyczne formalnie uzupełniły i rozszerzyły definicję informacji.
Claude Shannon i Warren Weaver potwierdzają ten paradygmat. Inżynierowie telekomunikacyjni, ich problemy techniczne skłoniły ich do zmierzenia informacji, aby wydedukować podstawy komunikacji (a nie teorię informacji). W Mathematical Theory of Communication w 1948 r. Modelowali informacje w celu badania odpowiednich praw: szumu, entropii i chaosu, przez ogólną analogię do praw energetyki i termodynamiki.
Ich praca, uzupełniająca prace Alana Turinga , Norberta Wienera i Von Neumana (żeby wymienić tylko te najważniejsze), stanowi początkowy fundament "nauk informacyjnych". Teoria informacji opiera się głównie na dwóch charakterystycznych pojęciach, którymi są zmienność niepewności i entropii („nieporządek” w sensie braku porządku, a zatem informacji w rozważanym zbiorze, gdzie nieokreśloność). Odchodząc od tych zasad i innych nauk ścisłych, technologie zajmują się wdrażaniem, aranżacją i realizacją rozwiązań, które zaspokoją potrzeby społeczeństw ludzkich.
Niektórzy badacze próbują paralele między pojęciami entropii w fizyce i entropia w informatyce w celu uzyskania obliczeniowej preparat o kosmologii i fizycznej rzeczywistości naszego świata, które niektórzy twierdzą mógł znaleźć klucze w narzędzi matematycznych, które są automaty komórkowe .
Niektórzy widzą w informatyce tylko technologiczną odmianę automatyzacji przetwarzania informacji (w tym transmisji i transportu) i uważają użycie terminu „informatyka” za niepoprawne, dlatego ci sami ludzie wolą nazwę „technologie informacyjne i komunikacyjne”, ponieważ powiedzieć, że lepiej obejmuje różne komponenty (systemy przetwarzania, sieci itp.) szeroko rozumianej informatyki. Ta bardzo restrykcyjna wizja terminu „informatyka” nie jest podzielana przez wszystkich, a ponadto wielu Anglosasów zazdrości bogactwa słowa „informatyka” i zaczyna je pożyczać.
Teoria grafów umożliwia modelowanie wielu dyskretnych problemów: obliczenia ścieżek, alokacje zasobów, problemy SAT ... Możemy przytoczyć twierdzenie o czterech kolorach jako klasyczny wynik tej gałęzi informatyki.
Teoria złożoności umożliwia klasyfikację algorytmów ze względu na ich asymptotyczny czas wykonania. To znaczy zgodnie z ich zachowaniem, gdy są używane do bardzo dużych danych. To właśnie w tej gałęzi informatyki znajduje się na przykład słynny problem P = NP .
Celem teorii obliczalności jest scharakteryzowanie funkcji, które może obliczyć algorytm. Rzeczywiście można wykazać, że istnieją funkcje, których komputer nie może obliczyć, dlatego warto wiedzieć, które z nich są. Problem ruchliwego bobra czy funkcja Ackermanna to klasyczne przykłady obiektów badanych w tej dziedzinie.
Teoria języków, często powiązana z teorią automatów, zajmuje się rozpoznawaniem zbiorów słów w danym słownictwie. Znajduje zastosowanie w algorytmach przetwarzania języka naturalnego, na przykład: automatyczne tłumaczenie , automatyczne indeksowanie dokumentów itp. a także w językach sztucznych, takich jak języki programowania: kompilacja, interpretacja.
Logika formalna jest podstawowym narzędziem komputera, istnieje szczególności teoria typu The rachunek lambda i przepisywanie jako podstawowych narzędzi programowania funkcjonalnego i dowód asystentów .