Introduktion
Dette projekt handler først og fremmest om datalogisk modellering og samspillet mellem datastrukturer og de algoritmer, der virker på dem. Vi har valgt at undersøge dette eksemplarisk i forhold til en konkret matematisk problemstilling. Dvs. idéen er, via udviklingen af funktionelt program, at lade dette understøtte en undersøgelse og analyse af en række datalogiske problemstillinger.
Anvendelsen af datalogiske metoder til løsning af en problemstilling kræver i første omgang en datalogisk repræsentation af problemstillingen. Dvs. valg af en datastruktur, der kan repræsentere de kritiske data. Dernæst følger udviklingen og implementeringen af algoritmer, der løser problemerne på den valgte datastruktur. Sidst kræves en oversættelse og en fortolkning af de løsninger, algoritmerne udformer, så en løsning på den oprindelige ("virkelige") problemstilling opnås. Dvs. den løsning, der ligger i datastrukturen(e) efter programkørsel, skal præsenteres for brugeren - selvfølgelig på en form, der er umiddelbart forståelig i forhold til den referenceramme, problemstillingen udstikker.
Vi har valgt et velkendt og umiddelbart enkelt matematisk problem; beregning af resultater af aritmetiske operationer med polynomier. Dette stemmer overens med vores ønsker om at fokusere på problemerne i det datalogiske domæne.
For at en computer skal kunne arbejde med et polynomium, skal det oversættes til en repræsentation, som er nem for computeren at arbejde med. En tekststreng er i princippet den enkleste entydige repræsentation af et polynomium. Det er den repræsentation, vi mennesker normalt sætter lig med et polynomium (selv om man ikke kan sige, at en notation er lig det matematiske udtryk, den beskriver).
Vi har set meget enkle løsninger baseret direkte på tekststrengs-formen. I første omgang mener vi simpelthen ikke, at denne repræsentation er datalogisk "pæn", og den er dermed heller ikke hensigtsmæssig i forhold til vores overordnede formål - at lære noget om datalogisk modellering og samspillet mellem datastrukturer og algoritmer!
For os mennesker er det let at overskue og finde f.eks. to ens led, hvis koefficienter skal adderes i en polynomieaddition, hvilket ikke er tilfældet for en computer. En fornuftig repræsentation vil derfor forsøge, at skabe det "overblik" over polynomiet, der gør det muligt for den hurtigere at finde og fortolke de rette elementer. I en tekststreng vil det være nødvendigt at gennemløbe hele strukturen før man med sikkerhed kan sige noget om forekomsten af ensartede led.
En repræsentation, som ofte er hensigtsmæssig for en computer, er et træ eller en hægtet liste. Begge disse repræsentationer har den fordel, at de er dynamiske. De har den fordel, fremfor f.eks. et statisk array, at hvis man har brug for at indsætte et element midt i datastrukturen under programkørsel, behøver man blot at ændre i et par referencer i stedet for at skulle flytte alle de resterende elementer et felt frem.
Vi har også set et eksempel på anvendelsen af en cirkulær enkelt-hægtet liste som datastruktur. Denne datastruktur havde det problem, at nok var den dynamisk mht. tilføjelsen af flere led, men den var ikke dynamisk i forhold til tilføjelsen af nye variable. Den krævede en eksplicit angivelse af de benyttede variable.
Vi har i dette projekt valgt en datastruktur skitseret af Donald E. Knuth fra Stanford University. Denne datastruktur er beskrevet i hans bog "The Art of Computer Programming" (knuth 1973), og tilføjer denne fleksibilitet mht. antallet af variable. Denne datastruktur er, som vi vil komme nærmere ind på i afsnittet Datastruktur, på en måde en sammenbygning af de to ovennævnte repræsentationsformer - træer og hægtede lister.
Den datastruktur, vi har valgt til repræsentation af et polynomium er rig i den forstand, at den er specialiseret til problemet, og vi mener, at den fanger de essentielle træk i forhold til problemstillingen. Vi har med andre ord valgt denne fremfor en række mere simple, der for det første kunne være for simple i forhold til vores overordnede mål om, at løse problemstillingen datalogisk "smukt", og for det andet kunne lægge begrænsninger på datastrukturens dynamik.
For at indpakke den datalogiske problemløsning i forhold til en programmør, der ønsker at bruge pakken (og i tråd med god objektorienteret tankegang), har vi desuden valgt, at lade den interne repræsentation være skjult inde i en pakke, der tilbyder et letforståeligt interface at arbejde med. Helt enkelt har vi valgt, at input og output skal være i form af tekststrenge.
Vi vil løbende forsøge at dokumentere og begrunde de valg, vi tager i design og implementering, og vi har valgt i et separat analyse-afsnit, med udgangspunkt i ønsket om at udvide problemstillingen til også at medtage negative eksponenter, at diskutere Knuths datastruktur og de begrænsninger selv denne rige datastruktur medfører.
Abstrakt
Formålet med dette projekt er at udvikle en Javapakke, der udfører aritmetiske funktioner på polynomier og undersøger forholdet mellem datastruktur og problemløsning.
Javapakken baserer sin interne repræsentation på en datastruktur foreslået af Donald E. Knuth. Denne træstruktur er blevet anvendt, selvom vi fandt visse begrænsninger under programudviklingen. Disse begrænsninger har vi analyseret, og i perspektiveringen har vi foreslået en forbedret datastruktur til repræsentation af polynomier.
De aritmetiske funktioner, der er implementeret i pakken er addition, subtraktion, multiplikation, division, integration, differentiation, eksponentialisering og negering.
Desuden er der lavet en parser for at tilbyde en bruger af pakken et enkelt brugerinterface, hvori der anvendes tekststrenge til repræsentation af polynomier. Derudover har vi inkluderet en grafisk udskrift af datastrukturen via HTML.
Konklusionen er, at det er muligt at lave en korrekt fungerende Javapakke, som kan anvendes til polynomieregning. Ydermere konkluderes det, at udformningen af datastrukturen har en stor effekt på problemløsningen, da det i høj grad er datastrukturen, som sætter rammerne for disse løsninger.
English Title: Java-package for polynomial handling.
Datastrukturen
Som nævnt ovenfor kommer datastrukturen fra Donald E. Knuth, der har nævnt den i forbindelse med "The Art of Computer Programming". Knuth mener selv at datastruturen er eksemplarisk mht. indlæring af træer og hægtede lister.
(Klik for at se hele datastrukturen og ikke kun dette udsnit).
Som det kan ses af ovenstående billede er datastrukturen nærmest en 4-hægtet liste, der i sin opbyning minder om et træ. Dvs. at alle polynomier har en rod, men da der er cikulære hægter i stukturen kan den per definiton ikke være et træ (nok nærmere en busk).
Download
Projekt:
Selve projektet (i
pdf-format) 1184 KB
Kodebilag zippet (i pdf-format zippet) 229 KB
PolySim-pakken (jar fil) 16 KB
PolySim-pakken zippet (java filer zippet) 20 KB