Från Rilpedia

Du har inte behörighet att redigera denna sida, av följande anledning:

Du kan se och kopiera denna sidas källtext:

<noinclude>{{rpsv.from.wpsv}}</noinclude>'''''Beräkning''''' (eng ''Computation'') kan definieras som sökandet efter en lösning på ett [[problem]] från ett givet indata med hjälp av en [[algoritm]]. '''''Beräkningsteori''''', som är en underdisciplin till [[matematik]] och [[datavetenskap]], behandlar analys av problem, indata och algoritmer. ==Historik== I tusentals år gjordes beräkningar med papper och penna eller i huvudet. Beräkningsteorin uppstod i början av 1900-talet, innan moderna [[dator]]er gjorde sitt intåg. Vid den tiden arbetade matematiker med att försöka avgöra vilka problem som var lösbara med enkla metoder och vilka som inte var det. Det första steget i detta arbete var att definiera vad som var en ”enkel metod” för att lösa ett problem, vilket ledde till behovet av en formell modell för vad en beräkning egentligen är. === Tidiga modeller === I dessa tidiga år föreslogs många olika modeller för beräkningar. En känd modell, [[Turingmaskin]]en, lagrar [[symbol]]er på ett oändligt långt band, där en ruta i taget behandlas av maskinen genom att innehållet läses, en beräkning äger rum och resultatet skrivs tillbaka i samma ruta. En annan modell, rekursiva funktioner, använder matematiska funktioner och funktionskomposition för att utföra sifferoperationer. [[Lambdakalkyl]] fungerar på ungefär samma sätt. Ytterligare modeller, såsom [[Markov-algoritm]]er och Post-system, använder [[grammatik]]liknande regelsystem för att utföra operationer på strängar. Alla dessa formaliseringar visade sig med tiden besitta samma beräkningskraft – dvs, en beräkning som kan utföras enligt en modell kan också utföras med vilken som helst av de andra. Detta gäller teoretiskt såväl som applicerat i samband med moderna datorer om man antar att en dator har [[oändlig]]t minne. Det är en mycket spridd uppfattning att alla väldefinierade formaliseringar av begreppet algoritm har samma beräkningskraft som en Turing-maskin, vilket är formulerat i Church-Turings sats. == Beräkningsteori== Beräkningsteori behandlar modeller för generella beräkningar tillsammans med de begränsningar som dessa har när de implementeras med datorer: * Vilka problem är – säkert eller förmodat – olösliga för en dator? * Vilka problem kan lösas av en dator, men som kräver så långa beräkningstider att lösningen inte är användbar? * Kan det vara svårare att lösa problemet med en dator än att kontrollera en given lösning till problemet? Frågor som dessa behandlas av komplexitetsanalys. === Andra användningsområden === Utöver modeller för generella beräkningar studeras även några enklare beräkningsmodeller som är användbara för vissa speciella avgränsade användningsområden, såsom * [[reguljära uttryck]], som används till att uttrycka [[mönstermatchning]]svillkor * [[ändlig]]a [[tillståndsmaskin]]er som används vid kretsdesign och inom vissa domäner av problemlösning * [[kontextfri]]a [[grammatik]]or som används för att specificera [[programspråk]] === Beräkningsteori och formella språk === Olika beräkningsmodeller är lämpade för olika typer av problem. Ett sätt att mäta beräkningskraften i en viss modell är att studera den klass av formella språk (se [[formell grammatik]]) som modellen kan generera. Dessa klasser finns beskrivna i den så kallade [[Chomsky]]-hierarkin. [[Kategori:Beräkningsteori]] [[ar:تحسيب]] [[en:Computation]] [[he:חישוביות]] [[pt:Computação]] [[su:Komputasi]] [[th:การคำนวณ]] <!-- could be theory of computation? -->

Tillbaka till Beräkningsteori.