Teoria obliczeń
Z Wikipedii, wolnej encyklopedii
Z Wikipedii, wolnej encyklopedii
Teoria obliczeń – dział informatyki i matematyki, który dzieli się na: teorię automatów i języków formalnych, teorię obliczalności oraz teorię złożoności. Teoria automatów zajmuje się definicjami i własnościami modeli obliczeń (modelami maszyn liczących). W uproszczeniu zajmuje się ona odpowiedzią na pytanie czym jest komputer, teoria obliczalności odpowiedzią na pytanie, które problemy dają się rozwiązać przy pomocy komputera, a teoria złożoności – odpowiedzą na pytanie jakim kosztem (czasowym i pamięciowym) da się to zrobić[1].
Modele obliczeń stosuje się w praktyce, na przykład model zwany automatem skończonym jest wykorzystywany w architekturze komputerów, budowie kompilatorów i w przetwarzaniu tekstu (przetwarzanie języka naturalnego, synteza mowy). Inny model, nazywany gramatyką bezkontekstową, jest używany przy projektowaniu języków programowania i sztucznej inteligencji[1].
Najogólniejszym modelem obliczeń jest maszyna Turinga. Można ją rozumieć jako komputer o nieograniczonych zasobach pamięci. Inne używane modele, takie jak: rachunek lambda, rachunek kombinatorów, algorytmy Markowa, funkcje rekurencyjne są sobie równoważne w tym sensie, że wszystko co jest obliczalne na jednym z nich, da się też obliczyć na maszynie Turinga. Rozważa się również węższe modele tzn. takie, które nie pozwalają na wyrażenie dowolnej funkcji obliczalnej, np. funkcje pierwotnie rekurencyjne. O niektórych problemach związanych z modelami obliczeń wiadomo, że są nierozstrzygalne. Na przykład nie istnieje algorytm, który rozstrzyga czy dwa λ-wyrażenia są równoważne lub czy maszyna Turinga dla danego wejścia zatrzyma się (zob. problem stopu). Podstawowym obiektem badań teorii obliczalności są funkcje obliczalne. Problem P vs NP jest określany jako najważniejszy nierozwiązany problem matematyczny w informatyce.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
