8: Algoritmit

Question 1

Äärellinen, askeleista koostuva vaihesarja, joka ratkaisee tietyn laskennallisen ongelman

Answer 1

Algoritmi

nimi lähtöisin: Muhammad al-Khwarizmi (780-850)

Kehitetty alun perin laskennallisiin ongelmiin, mutta nykyään sovelletaan tiedonkäsittelyyn (datan järjestely, muokkaus) ja automaattiseen päättelyyn (esim. autopilotti, kontrollijärjestelmät)

Question 2

1900-luvun alussa tehty lista kysymyksiä, johon matematiikan tulisi pystyä vastaamaan tulevalla vuosisadalla

Answer 2

Hilbertin lista

David Hilbert (1862-1943)

Vastausten avulla tultaisiin saavuttamaan matematiikalle universaali luonne. Lista innoitti monia matemaatikkoja, ja sai aikaan kehitystä

Question 3

Hilbertin listan kysymys, jossa algoritmille annetaan väittämä, ja se ratkaisee onko tämä universaalisesti validi

palauttaa: tosi-epätosi

Answer 3

Päätösongelma

Tälläista algoritmia ei ollut mahdollista toteuttaa, sen todisti Kurt Gödel (1906-78)

Question 4

Laite, millä pystytään laskemaan kaikki samat ongelmat kuin algoritmeilla

Answer 4

Turingin kone

Alan Turing (1912-54)

Tätä väitettä kuvaa Churchin-Turingin teesi. Turingin kone määrittelee myös sen, mitä digitaalisilla tietokoneilla on mahdollista tehdä