Matte i media og forskning.

x871kx6167ss7 · 1. desember 2011

Fortell mer om logikk! Hva gikk det ut på? Hva lærte dere? Jeg er over middels interessert i det, og banner over at jeg ikke har funnet noen slike emner på NTNU. Aksiomatisk mengdelære kan også være interessant. Lurer på hvor dypt de går? Da må du nok bli vant med å føre bevis.

Har hatt mest om førsteordens predikatlogikk, som jeg vil tro du er i hvertfall litt familiær med (fra diskret matte, kanskje?). Det er gjerne tre ting som går igjen: syntaks, semantikk, og kalkyler.

Syntaksen defineres rett fram ved strukturell induksjon.

For semantikken har vi modeller og modellteori. En modell gir et domene, og forteller hva konstant-, funksjon-, og relasjonssymbolene skal tolkes som, og vi også (implisitt) bestemme hvordan $chart?cht=tx&chl=\forall$ - og $chart?cht=tx&chl=\exists$ -formler skal tolkes.

Har vel vært borte i to kalkyler i forbindelse med førsteordens logikk: sekventkalkyle (LK) og en som jeg ikke kan navnet på . Sekventkalkyle fungerer i bunn å grunn slik at man begynner med treet som består av bare påstanden, og så kan man utvide treet fra løvnodene etter bestemte regler, og når alle løvnodene er aksiomer, så har man et bevis. (Dersom man leser beviset andre veien, så begynner man med aksiomene, også kommer man fram til påstanden ved å sette dem sammen.)

En viktig ting er å bevise om kalkylen er komplett og sunn. En kalkyle er sunn dersom alt du beviser er gyldig, og den er komplett dersom alt som er gyldig er bevisbart. (Gyldig=semantikk, bevis=syntaks).

Eller så har jeg hatt litt intuisjonistiks logikk hvor vi også brukte sekventkalkyle (LJ) og kripke-modeller.

I matematisk logikk så jobbet vi oss mot Gödels ufullstendinghetsbevis.

Angående aksiomatisk mengdelære, så har jeg inntrykk av at de går ganske dypt. Du kan se emnesiden her (er vel litt informasjon for emnesiden for 2011).

pululf · 1. desember 2011

Halla folkens.

Har såvidt begynt å lære meg Wolfram Mathematica siden jeg må gjøre noen ganske heavy analyser av noen funksjoner til en coilgun jeg skal bygge.

Men jeg har problemer. Jeg får recursion error av det her:

L := 0.15

alpha[x_, y_] := x/y

beta[y_] := L/2 y

field[a_, b_] := b {ArcSin[a/b] - ArcSin[1/b]}

Plot3D[field[alpha[x, y], beta[y]], {x, 1, 10}, {y, 1, 10}]

Noen som skjønner seg på hvorfor dette skjer?

luser32 · 4. desember 2011

Litt tungvint(?) spørsmål:

Jeg prøver å utvide de komplekse tallene til en tredimensjonal normert algebra over R (for så å vise at den ikke er en "division algebra").

Nå har jeg gjort dette ved å definere tallet j slik at j^2 = -1 og ji = -1. Har prøvd å gå gjennom alle egenskapene som kreves for å sjekke om dette blir en algebra - og det ser ut til å funke. Men det blir bra mye tall å holde styr på etter hvert, så det kan jo hende jeg har gjort en feil en eller annen plass.

Så er det noen som allerede vet hvorvidt overnevnte utvidelse funker, evt har et moteksempel til meg?

Forresten, definisjon av algebra over $chart?cht=tx&chl=\mathbb{R}$ :

For alle $chart?cht=tx&chl=\alpha \in \mathbb{R}$ og x,y,z i overnevnte vektorrom:

$chart?cht=tx&chl=\alpha(xy) = (\alpha x)y = x(\alpha y)$
$(xy)z = x(yz)$
$(x y)z = xz yz$
$x(y z) = xz yz$

Endret 5. desember 2011 av luser32

wingeer · 5. desember 2011

Hei! Jeg tror du tenker og har gjort rett! Det blir veldig mye å holde styr på, ja. Det du gjør er rett og slett å definere kvaternionene, dersom du har hørt om de. Kvaternionene er historisk sett det første eksempelet på en nonkommutativ divisjonsalgebra, og utvider de komplekse tallene til 3 dimensjoner.

luser32 · 5. desember 2011

Naa tror jeg du blander litt:p Kvaternionene er firedimensjonale, det finnes ingen tredimensjonale divisjonsalgebraer over $chart?cht=tx&chl=\mathbb{R}$ . Jeg prover aa finne et eksempel paa en normert algebra over $chart?cht=tx&chl=\mathbb{R}$ , og vise at divisjon feiler.

I eksempelet mitt over, har ikke tallet i-j noen invers.

EDIT: Men naar jeg tenker over det, saa gir eksempelet mitt ingen mening, da ji=-1 impliserer at j=i, og da blir alt bare tull. Jeg faar prove noe annet:p

Endret 5. desember 2011 av luser32

wingeer · 5. desember 2011

Ah, det er et godt poeng. Quaternions, ligger litt i navnet. Hva er det du skal bevise, da?

luser32 · 5. desember 2011

wingeer:

Jeg ser litt paa quaternions og Frobenius' teorem om real divisjon-algebras. Prover ikke aa bevise noe, men vil se om jeg kan komme opp med en tredimensjonal normert algebra(komplekse tall i tre dimensjoner) - og deretter vise at divisjon ikke fungerer. Burde vel ogsaa vaere mulig aa soeke opp noen av William Hamiltons forsoek, men det blir jo juks:p

Halla folkens.

Har såvidt begynt å lære meg Wolfram Mathematica siden jeg må gjøre noen ganske heavy analyser av noen funksjoner til en coilgun jeg skal bygge.

Men jeg har problemer. Jeg får recursion error av det her:

L := 0.15

alpha[x_, y_] := x/y

beta[y_] := L/2 y

field[a_, b_] := b {ArcSin[a/b] - ArcSin[1/b]}

Plot3D[field[alpha[x, y], beta[y]], {x, 1, 10}, {y, 1, 10}]

Noen som skjønner seg på hvorfor dette skjer?

Skal ikke field vaere en vector? ie sett inn et komma mellom asin(a/b) og -asin(1/b)

wingeer · 5. desember 2011

wingeer:

Jeg ser litt paa quaternions og Frobenius' teorem om real divisjon-algebras. Prover ikke aa bevise noe, men vil se om jeg kan komme opp med en tredimensjonal normert algebra(komplekse tall i tre dimensjoner) - og deretter vise at divisjon ikke fungerer. Burde vel ogsaa vaere mulig aa soeke opp noen av William Hamiltons forsoek, men det blir jo juks:p

Aha! Kan du ikke bare se på $C^3$ med en passelig norm?

luser32 · 5. desember 2011

Litt usikker på hva du mener med $C^3$ , men disse to linkene kan se ut som interessante utgansgspunkt(og kanskje det var det du mente?):

http://en.wikipedia.org/wiki/Multicomplex_number

http://en.wikipedia.org/wiki/Tricomplex_number

Det er jo ganske gøy å utforske litt på utenom pensum innimellom merker jeg:o)

oslo72 · 7. desember 2011

Etter oppfordring fra Kubjelle poster jeg mitt spørsmål her:

--------------------------------------------------------------

Ok, jeg går ikke på skole, men føler at dette er nærmeste riktige sted å poste mitt problem:

Et puslespill på 5000 brikker er X vanskelig.

Hvor mye vanskeligere er et puslespill på 18240 brikker?

Vi kan ta utgangspunkt i at alle brikkene er snudd riktig vei opp.

Kan noen hjelpe meg med utregningen?

Det er jo ikke slik at det er 3,648 ganger vanskeligere.

Vi kan ta et par utgangspunkt:

- Samme motiv/farger

- Samme sammensetning av de ulike brikketypene

- 5000-biters puslespillet er 100x50 brikker

- 18240-biters puslespillet er 192x95 brikker

Finnes det i det hele tatt en formel for å regne ut differansen? Det er jo mye vanskeligere å finne riktig brikke blant 18240 brikker enn 5000 brikker.

SirDrinkAlot · 7. desember 2011

Du sier ingenting om hvordan "vanskelig" er definert. Altså hvordan avhenger vanskelighetsgraden av antall brikker? Og du har bare et punkt så du kan ikke f.eks. anta en sammenheng for så å finne den som passer best...

Jeg skjønner ikke hva du vil fram til, for meg virker det som det er for lite informasjon til å løse oppgaven.

Simen1 · 7. desember 2011

En dum og blind robot ville kanskje testet brikke for brikke uavhengig av form, farge og mønster etter brute force metoden. Da kunne man regnet ut statistisk vanskelighetsgrad i form av antall tester før spillet er ferdig lagt.

Straks man skal ha menneskelig intelligens med mønster-, form- og fargegjenkjenning inn i regnestykket så blir plutselig forutsetningene umulig å definere matematisk.

x871kx6167ss7 · 8. desember 2011

Dette høres ut som et kompleksitets-teori-spørsmål.

Det å finne gjennomsnittlig tidskompleksitet for et menneske har jeg ikke lyst til å prøve meg på. Da kommer som Simen1 nevner inn flere aspekter som gjør det veldig vanskelig.

Derimot så har jeg en følelse av at i værste tilfelle, så vil man måtte lete gjennom alle brikkene hver gang. Her snakker jeg om værste tilfellet, når ingen av brikkene har felles egenskaper som man greier å gjenkjenne. I såfall så vil tidskompleksiteten være $chart?cht=tx&chl=\Theta(n!)$ , med andre ord så har vi da hhv $5000!$ "vanskelig" og $18240!$ "vanskelig". Problemet er i hvertfall i NP, og jeg vil tro at problemet er NP-hardt.

oslo72 · 8. desember 2011

Jeg skjønner at det er mange ukjente faktorer her. Jeg er absolutt ikke noe mattegeni, og slang ut spørsmålet fordi det er relevant for meg da jeg vurderer å pusle dette om et par år.

Min intelligens spiller såklart en rolle i regnestykket, men jeg er nok ca like smart på 18240- som på 5000-spillet.

Vi brukte ca 3 måneder (med til og fra-pusling) på 5000-spillet - og spørsmålet kom vel egentlig opp fordi jeg er bekymret for at det kommer til å ta MANGE år med samme intensitet som sist (ca 50-60 brikker om dagen). I samme tempo som sist vil det jo ta opp mot 10-12 måneder - men sjansen for å finne riktig brikke like raskt som på 5000-spillet er jo veldig mye mindre.

Simen1 · 8. desember 2011

Så fremt bildet er nogen lunde sorterbart så kan du sortere brikkene i haguer og konsentrere deg om en haug av gangen. F.eks i haugene lys himmel, mørk himmel, skyer, blomster, gress, vann, bygninger, mennesker, kjøretøy og tak. Det vil alltids bli noen huller pga feilsortering, men det fyller du igjen senere. Tidsforbruket vil nok likevel bli litt mer enn lineært skalert fra 5 til 18 tusen brikker, så fremt du brukte samme metode sist. Hvis ikke så kanskje du klarer å presse ned tidsforbruket til under lineær skalering. God sortering på forhånd er god tidsbruk.

Du kan jo også vurdere å øke dagsproduksjonen for å bli fortere ferdig.

Matsemann · 8. desember 2011

Hvis ikke så kanskje du klarer å presse ned tidsforbruket til under lineær skalering. God sortering på forhånd er god tidsbruk.

Skal du sortere i hauger må du igjennom alle brikkene, og allerede da har du lineær tid/skalering. Selv med lavt konstantledd og lav "kjøretid" i forhold til resten av puslespillet vil det vel i Big-O-notasjon bli begrenset der.

La oss si man har et 16x16 puslespill, og et 4x4 puslespill. Det 4x4 klarer man å løse lett.

Det 16x16 deler man brikkene i 4 stk hauger a 4 brikker, der man løser disse 4x4 puslespillene. Så har man 4 store "brikker", som man så løser som et 4x4 puslespill.

Slik ville nok jeg løst det, på en eller annen måte. Hadde man fått 32x32 ville man delt det opp i 4 stk 16x16 som man ville delt videre. Altså en form for rekursiv algoritme. Gitt man har en god måte å avgjøre hvilket hjørne en brikke skal være i.

Hvor kompleks kjøretid dette har er derimot vanskelig å si uten å vite hvordan man ville delt brikkene rundt.

Men antall operasjoner (uten konstantledd) vil jo kunne bli på formen (n = antall brikker):

T(n) = 4 * T(n/4) + f(n)

der f(n) sier noe om hvor mye arbeid det er å fordele brikkene en får i 4 hauger (som man så sender ned i en ny T(n)), og så hvor lang tid man bruker på å slå disse 4 "brikkene" man da får sammen til en ny, stor brikke.

Splitt og hersk, rekursivt til man når base-case. Har man f(n) kan man da finne hvordan problemstørrelsen vokser vha Master Theorem.

Endret 8. desember 2011 av Matsemann

Matsemann · 8. desember 2011

Slo opp i en artig bok jeg kjøpte i fjor, som omhandler kompleksiteten til forskjellige spill, Games, Puzzles & Computation. Der står det dessverre ikke mye om jigsaw-puzzles (det engelske navnet), annet enn:

Jigsaw puzzles can be formalized in a variety of ways, with different edge matching rules, different boundary conditions, and different constraints on numbers of available pieces. Many versions are NP-complete. Infinite generalizations are undecidable.

Det hjelper ikke særlig på å finne en faktor mellom to puslespill, da.

oslo72 · 8. desember 2011

Jaja, da gjelder det bare å teste ut selv

Jeg poster svaret om 4-5 år

nicho_meg · 8. desember 2011

Vi kan jo anta at begge puslespillene er like i motiv. Først vil du sortere alle brikkene som tar noe lengre tid med større antall brikker. Men da er det antagelig snakk om konstant forskjell. F.eks 1000 brikker tar 10 ganger så lang tid som 100.

Hjørne- og kantbrikker blir tilsvarende som eksempelet over.

Men det store problemet er motivet og dermed hvor godt du kan sortere brikkene. Elg i solnedgang er mye lettere å sortere, derfor får du flere enklere hauger, enn isbjørn i snøstorm. (vi antar logisk nok at det er lettere å pusle mange små sorterte hauger enn en stor).

Så for å svare på spørsmålet ditt så godt jeg kan: Det som avgjør tidsforskjellen er størrelsen på de små sorterte haugene og hvor lang tid det vil ta å lage/sortere de. Å pusle sammen to bilder lagd av to ferdigpuslede hauger tar liten tid(evt O(m) der m er antall hauger). Siden vi antar at sorteringen tar O(n) blir da tiden det tar; (sorteringstid per brikke)+(kompleksitet/pusletid per haug)*(antall hauger)+(sammenpusling av bildene).

Du får selv sette inn tall. Det lar seg ikke gjøre uten å vite den vanskelighetsgraden på motivet. Forskjellen i tid får du ved å dele totaltidene på hverandre.

oslo72 · 8. desember 2011

Tusen takk.

Jeg får leve med at ikke alt går å løses matematisk med så mange ukjente faktorer. :-)

Matte i media og forskning.

Anbefalte innlegg

Lenke til kommentar

Videoannonse

Lenke til kommentar

Lenke til kommentar

Lenke til kommentar

Lenke til kommentar

Lenke til kommentar

Lenke til kommentar

Lenke til kommentar

Lenke til kommentar

Lenke til kommentar

Lenke til kommentar

Lenke til kommentar

Lenke til kommentar

Lenke til kommentar

Lenke til kommentar

Lenke til kommentar

Lenke til kommentar

Lenke til kommentar

Lenke til kommentar

Lenke til kommentar

Opprett en konto eller logg inn for å kommentere

Opprett konto

Logg inn

Populær nå

Hvem er aktive 0 medlemmer