Algoritmer og matematikk

[mushin]

Heisann, hvordan er forholdet mellom algoritmer og matematikk? Holder på med et programmerings emne som heter algoritmer og datastrukturer, samtidig som jeg holder på å ta opp R1. Er alle matte-problemer algoritmiske? Dvs, kan de løses ved å presist definere stegene for løsningen? Eller er det å tenke "algoritmisk", steg-for-steg, mere vanlig innen diskret matematikk?

Jeg syntes det er gøy å definere en algoritme som forhåpentligvis skal løse problemet, og deretter følge planen og se om det funker. Hvordan jobber dere med matte, er det veldig "free-flow-jamming" eller legger dere opp en strategi?

Mvh Daniel, som beveger seg fra matte-hat til matte-elsk.

[Markonan]

Omtrent alt man lærer av matte opp til vgs-nivå er algoritmisk matematikk. Man regner gjennom oppgaver som enten har en formel (f.eks pythagoras eller abc-formelen) eller en veldig bestemt fremgangsmåte (f.eks finn maks/min-punktet til funksjonen), som begge kan sammenlignes med en algoritme.

I høyere matematikk er det ikke så mye algoritmisk matematikk, men mer bevisføring. Det går ikke an å skrive en algoritme/et dataprogram som beviser resultater (bortsett fra på veldig enkle bevis). Veldig ofte kreves det litt fantasi eller en lur observasjon for å fullføre et bevis, og det er ikke datamaskiner så flinke til.

Kort sagt, så er ikke all matematikk algoritmisk.

På en annen side så brukes det mye i anvendt matematikk. F.eks finnes det integraler og partielle differensialligninger og andre ting som ikke kan løses analytisk, men som rimelig enkelt kan beregnes numerisk. På en måte kan de ikke løses med en algoritme, men de kan løses numerisk - som allikevel er en algorimte.

[Charlatan]

Jeg vil si at mye av høyere (og såkalt "ren") matematikk faktisk er veldig algoritmisk. Mange bevis går rett og slett ut på å danne en algoritme for å finne det man ønsker å finne. F.eks er de aller fleste eksistensbevis (som ikke avhenger av utvalgsaksiomet) rent algoritmiske. Man bør ikke sette et skille mellom algoritme og bevis, skjønt et bevis muligens krever en høyere standard på begrunnelse for at algoritmen faktisk fungerer.

Opp til vgs-nivå handler det imidlertid mest om å utføre gitte algoritmer, men dette er jo ikke hva man driver på med når man programmerer algoritmer likevel. Så man kan kanskje si at høyere matematikk ligger nærmere emnet ditt enn vgs-nivå-matematikk.

[espen180]

Jeg vil tro at alle oppgaver, uansett nivå, der målet er å bestemme en egenskap eller finne verdien til denne, er rent algoritmiske.

Algoritmene hviler derimot på at visse teoremer er sanne. Bevisene for disse teoremene er derimot sjelden algoritmiske. I mange tilfeller kreves det, som Markonan påpekte, kreativitet i minst ett steg i beviset.

I denne sammenhengen er det interessant at en datamaskin var i stand til å reprodusere gamle teoremer i geometri, samt produsere mange nye teoremer.

Kanskje disse linkene er interessante. Du kan finne flere på Google ved å søke etter "Computer generated theorems" eller lignende.
http://www.macalester.edu/~bressoud/pub/cgp.pdf
http://people.unt.edu/ctm0055/Paper2.pdf
http://www.math.bas.bg/omi/DidMod/Artic ... _Point.pdf

[FredrikM]

F.eks er de aller fleste eksistensbevis (som ikke avhenger av utvalgsaksiomet) rent algoritmiske.

Et par mot-eksempler: Bevisene til Borsuk-Ulam, Brouwers fikspunkt-teorem, at det finnes irrasjonelle tall. Alle disse er eksistensbevis, men bruker motsigelse som "teknikk".

Er alle matte-problemer algoritmiske? Dvs, kan de løses ved å presist definere stegene for løsningen?

Svaret er nei. Hilbert's tiende problem stilte nettopp det spørsmålet om Diofantiske ligninger (ligninger med heltallsløsninger). (http://en.wikipedia.org/wiki/Hilbert's_problems) Det er bevist at det ikke finnes noen generell algoritme for å løse en generell Diofantisk ligning (sånn omtrent).

I tillegg har vi Gödels kjente teoremer, som sier at det finnes sanne matematiske påstander som ikke lar seg bevise.

[Charlatan]

F.eks er de aller fleste eksistensbevis (som ikke avhenger av utvalgsaksiomet) rent algoritmiske.

Et par mot-eksempler: Bevisene til Borsuk-Ulam, Brouwers fikspunkt-teorem, at det finnes irrasjonelle tall. Alle disse er eksistensbevis, men bruker motsigelse som "teknikk".

Vel, strengt tatt vil jeg ikke si at beviset for at det finnes irrasjonelle tall ikke er algoritmisk. La oss ta f.eks kvadratroten av 2. Man viser først at x^2-2 = 0 har en løsning. Hvis man tar utgangspunkt i definisjonen av reelle tall som ekvivalensklasser av konvergerende rasjonale følger vil et eksistensbevis være å nettopp finne en slik følge. Det vil jeg kalle algoritmisk. Når man deretter viser at tallet er irrasjonalt så er man ikke lenger inne på et eksistensbevis, men et bevis angående egenskapene til et tall man allerede har funnet. At man bruker motsigelse som teknikk angående dette er i og for seg naturlig ettersom irrasjonalitet er en negativ egenskap, i den forstand at et reellt tall er definert som irrasjonalt dersom det ikke er rasjonalt.

Aksiomatisk geometri er et eksempel på hvor bevis er konstruktive og algoritmiske.

[Markonan]

Før vi begynner og slåss her inne, så er det greit å slenge ut denne:

There is no generally accepted definition of algorithm.

Fra
http://en.wikipedia.org/wiki/Algorithm_ ... erizations

På neste linje står det:

But most agree that algorithm has something to do with defining generalized processes

Det var dette jeg tenkte på. Når så mange bevis bruker resultater fra tidligere bevis mener jeg at det ikke helt kvalifiserer til denne typen algoritme. Tenkte spesielt på situasjoner der man bruker et resultat fra et helt annet felt, som hender av og til.

På en annen side så definerte vel Al-Kwarizmi algoritmer som:
en prosess som etter et endelig antall steg produserer et resultat.
Med denne definisjonen så er omtrent all matematikk algoritmisk, men da blir det så generelt at det mister mening.