Algoritme - Wikipedia

# Algoritme

### Frå Wikipedia – det frie oppslagsverket

Ein algoritme i matematikk og informatikk er ein oppskrift på korleis ein kan løse ein bestemt type problem. Ordet kjem opphaveleg frå matematikaren og astronomen al-Khowarizmi (ca. 780-850)). I ei av bøkene sine beskriv han ein algoritme for korleis ein kan løyse ein klase av andregradslikningar.

## [endre] I informatikk og matematikk

Algoritmar er først og fremst eit tema i matematikk og informatikk, og vert studert i nokre spesialområde i teoretisk informatikk, som algoritmeteori, kompleksitetsteori og bereknbarheitsteori. I form av dataprogram vert algoritmer nytta til å styre datamaskinar.

## [endre] Definisjon

Mange matematikarar og logikarar i det 19. og 20. århundret likte ikkje den manglande nøyaktigheita i omgrepet algoritme, og ønskte eit meir teoretisk tilfredsstillande fundament. I den første halvdelen av det 20. århundret vart det gjort fleire forsøk på å finne ein god definisjon. Turingmaskina til Alan Turing, Lambda-kalkulusen til Alonzo Church, rekursive funksjonar, Chomsky-grammatikken og Markov-algoritmer er alle formaliseringar av bereknbarheitsomgrepet. Det var prova at alle desse metodane er like kraftige. Alle kan emulere ein turingmaskin, og alle kan verte emulert av ei turingmaskin. Ved hjelp av turingmaskina vert følgjande formelle definisjon mogleg:

Ei berekningsoppskrift kallast ein algoritme om det finst ei Turing-maskin som er ekvivalent til oppskrifta og som stoppar for alle inndata som har ei løysing.

Frå denne definisjonen kan ein utlede følgjande eigenskapar:

1. Ein må kunne skrive oppskrifta med ein endeleg lang tekst.
2. Eit kvart steg i oppskrifta må kunne utførast.
3. På kvart tidspunkt kan berre ein endeleg stor lagringsplass nyttast.
4. Oppskrifta kan berre nytte eit endeleg antall steg.

I praktiske problem krev ein vanlegvis òg at ein algoritme skal oppfylle følgjande vilkår:

1. Algoritmen må alltid gi same svar dersom inndataene er dei same.
2. Kva det neste steget i oppskrifta er må alltid vere eintydig definert.

## [endre] Analyse av algoritmar

Analyse av algoritmar er eit hovedtema i informatikk, og vert vanlegvis gjort teoretisk utan å lage konkrete implementeringar i programmeringsspråk. Den liknar difor andre matematiske område, der ein heller studerer dei grunnleggjande konseptene, enn å se på konkrete anvendingar. Ein studerer difor algoritmar i ein sterkt formalisert form.

Ein deler analysen i ulike delområde. I kompleksitetsteori studerer ein ressursbruken til algoritmane, det vil seie tiden det tek å kjøre algoritmen og lagringsplassen som krevst. I bereknbarheitsteori studerer ein spørsmålet om ein gitt algoritme i det heile vil terminere.

Henta frå «http://nn.wikipedia.org../../../a/l/g/Algoritme.html»

Kategoriar: Informatikk

##### Views

- Innhaldsside
- Diskusjon
- Noverande versjon

##### Søk

##### På andre språk

- ‪Norsk (bokmål)‬
- Svenska
- Dansk
- Afrikaans
- العربية
- Aragonés
- Asturianu
- বাংলা
- Беларуская
- Bosanski
- Български
- Català
- Česky
- Deutsch
- Eesti
- Ελληνικά
- English
- Español
- Esperanto
- فارسی
- Français
- Galego
- 한국어
- Hrvatski
- Bahasa Indonesia
- Interlingua
- Íslenska
- Italiano
- עברית
- ქართული
- Latviešu
- Lëtzebuergesch
- Lietuvių
- Magyar
- Македонски
- Bahasa Melayu
- Nederlands
- 日本語
- Polski
- Português
- Română
- Русский
- Shqip
- Simple English
- Slovenčina
- Slovenščina
- Српски / Srpski
- Srpskohrvatski / Српскохрватски
- Basa Sunda
- Suomi
- Tagalog
- ไทย
- Tiếng Việt
- Тоҷикӣ
- Türkçe
- Українська
- 中文