Søgemaskineprojekt for

Grundlæggende Programmering,
Objekt orienteret programmering,
Databasesystemer,
Parallelle systemer og
Introduktion til algoritmik og datastrukturer

MAJ 2002

Denne hjemmeside :
http://www.it-c.dk/research/algorithms/Kurser/SoegeProjekt/2002MAJ/


Indhold

Denne side: Andet:

Overordnet

Velkommen til hjemmesiden for søgemaskineprojektet. Søgemaskineprojektet er for studerende med forskellige forudsætninger og projektmål. Alle grupper skal løse de opgaver der er beskrevet under fællesdelen nedenfor. Dog kan der træffes specielle aftaler for hver gruppe med en lærer. Når en gruppe har løst opgaverne under fællesdelen har gruppen sin første primitive udgave af en søgemaskine for IT-C.

Efter fællesdelen kan gruppen arbejde videre i forskellige retninger. F.eks. kan gruppen arbejde videre med en eller flere af de foreslåede udvidelser. Hvad den enkelte gruppe vælger at arbejde videre med vil afhænge af interesser og forudsætninger. Såfremt gruppen ikke har andre forudsætninger end grundlæggende programmering forventes det ikke at gruppen i projektperioden når meget længere end at besvare fællesdelen. Grupper med flere forudsætninger forventes at nå mere end at besvare fællesdelen.

Hver gruppe skal ved projektetperiodens start udfylde en projektformular. Hver gruppe skal beskrive sit projektarbejde i en rapport, og denne rapport skal senere forsvares ved en projekteksamen.

Under projektperioden afholdes der projektdage hvor der vil blive givet generel information om projektet og hvor der vil være mulighed for at stille spørgsmål. Hvis du eller din gruppe herudover har problemer under projektet, er I velkomne til at henvende jer til en af de lærere, der er tilknyttet projektet.

På den første projektdag præsenteres projektet og der vil være mulighed for at danne grupper. Desuden præsenteres de programmeringsteknikker som er nødvendige for at kunne løse fællesdelen. I nedenstående beskrivelse af opgaven vil der således sikkert være ord som du ikke kender før den første projektdag har været afholdt. Specielt vil dele af teksten nok i en eller anden udstrækning være uforståelig, hvis man ikke før har hørt om hægtede lister. Hægtede lister er en af de programmeringsteknikker som bliver præsenteret på den første projektdag.


Opgaven

Datafiler

Til brug for projektet stilles forskellige datafiler der indeholder hele eller dele af IT-Cs hjemmesidestruktur til rådighed. Datafilernes format kan illustreres ved følgende eksempel:

*PAGE:http://www.it-c.dk
Her
står
et
ord
og
et
ord
mere
*PAGE:http://www.it-c.dk/enandenside.html
Her
står
mere
og
endnu
mere

Ideen er altså, at en datafil indeholder informationer om en række hjemmesider. Informationerne for en given hjemmeside starter med en *PAGE linje der angiver hvilken adresse siden findes på. Sådan en adresse kaldes også en URL. Dernæst kommer en liste over de ord siden indeholder. Ordne er blot opremset med et ord pr linje i den rækkefølge de står i på siden. Det fremgår at det samme ord godt kan optræde flere gange under den samme side.

Man kan hente følgende datafiler hvor de første indeholder nogle af IT-Cs hjemmesider og den sidste indeholder allesammen:

Disse filer findes også i kataloget:

  s:\sysadm\soegemaskine

og det anbefales at man bruger dem direkte herfra når man er på IT-C.

Hvis man arbejder under linux finder man filerne på /import/share/stud/sysadm/soegemaskine/

Programmet SearchCmd

Som en del af denne opgave udleveres programmet SearchCmd.java som implementerer en lille søgemaskine. Programmet skal, når det udføres, gives navnet på den datafil som det skal bassere sin søgning på, som parameter. Se afsnittet om brug af Java nedenfor for informationer om hvordan man angiver parametre til Java programmer.

Den parameter man angiver til programmet bliver lagt i args[0] hvor args er parameteren til programmets main metode. Det første programmet gør er at konstruere en hægtet liste datastruktur med alle linjerne fra datafilen hvis navn står i args[0]. Objekterne i den hægtede liste indeholder felterne str og next. Feltet str indeholder en linje fra datafilen og next peger på det næste objekt i listen. Efter indlæsning startes en simpel brugergrænseflade hvor brugeren kan få svar på om et givet ord findes på en af hjemmesiderne i den indlæste datafil.

Fællesdelen

Fællesdelen består i at løse følgende 4 opgaver hvor opgave 3 er den mest omfattende. Disse opgaver bliver præsenteret på den første projektdag.
  1. Kør programmet SearchCmd.
  2. Modificer SearchCmd således at hvis der f.eks. søges på "Hans", så udskrives alle de URL'er, hvorpå "Hans" forekommer. Dette skal gøres ved at ændre på søgemetoden i SearchCmd. Man skal altså ikke ændre på opbygningen af datastrukturen.
  3. Modificer opbygningen af datastrukturen således at der dannes en hægtet liste af objekter som indeholder tre felter, nemlig str, next og urls. Felterne str og next skal være som i SearchCmd, blot skal der kun stå ord i listen og hvert ord skal kun forekomme en gang. Såfremt et objekt indeholder ordet "Hans" i feltet str skal objektets urls felt være en peger til en liste af de URL'er som indeholder ordet "Hans". En liste af URL'er skal bestå af objekter med to felter, nemlig next og url. Feltet next skal være en peger til det næste objekt i listen og feltet url skal være en peger til en URL. Efter konstruktionen af denne datastruktur skal der laves tilhørende søgerutiner. Datastrukturen opbygget her fylder mindre end strukturen fra SearchCmd og er hurtigere at søge i.
  4. Modificer løsningen fra opgave 3 således at man i stedet for at have en hægtet liste med de forskellige ord der forekommer har disse i en hashtabel datastruktur. I skal opbygge hashtabellen med chained hashing, d.v.s. hver indgang skal indeholde en objekt reference til en haegtet liste. Brug af sådan en struktur vil give en drastisk reducering af den tid det tager at opbygge og søge i datastrukturen.

I løsningen af ovenstående fællesopgaver er det ikke tilladt at bruge andre pakker end java.io og java.lang. Specielt er det altså ikke tilladt at bruge nogen af klasserne fra java.util pakken. Baggrunden for dette krav er, at et af formålene med dette projekt er at lære hvordan man programmerer forskellige datastrukturer og ikke blot at lære hvordan man bruger datastrukturer programmeret af andre.

Som det fremgår er det tilladt at bruge forskellige metoder på String objekter. Herunder er det tilladt at bruge metoden hashCode. Desuden er det tilladt at oprette tabeller (arrays). Hvis du er i tvivl om du må bruge en given Java funktionalitet så kontakt en af lærerne.

Til de opgaver der kommer efter fællesdelen er der ikke nogen begrænsninger på hvilke java faciliteter man må bruge.

Rapporten

Der stilles følgende helt generelle krav til rapporten:

Desuden er der følgende krav til rapporten som alle er relateret til de 3 søgemaskiner implementeret i fællesdelen:

Hvad rapporten skal indeholde i forbindelse med det der ligger udover fællesdelen vil afhænge af hvad gruppen har arbejdet med og hvor gruppen har valgt at lægge fokus i dette arbejde.

På grundlæggende programmering er der udarbejdet en note om hvorledes en projektrapport kan se ud. Denne note anbefales det at man læser før rapportskrivning. I noten skønnes det at en projektrapport ca. fylder 25 side. For dette konkrete projekt skønner vi at en rapport kan fylde meget mindre, og rapporten må maksimalt fylde 20 sider med almindelig font. I de 20 sider skal ikke indregnes bilag og figur.

Datastrukturer

Til at løse opgaverne hørende til fællesdelen skal man bruge hægtede lister og hashing.

Hægtede lister bliver gennemgået på den første projektdag. Hvis man ikke kender til hægtede lister kan man læse om disse i "JAVA: software solutions" af John Lewis og William Loftus, anden udgave, kapitel 12.1. Alternativt kan man kigge på denne hjemmeside. Man kan også hente ListProgram.java som indeholder et lille eksempel på brug af hægtede lister. En rigitg god måde at blive fortrolig med hægtedede lister på er ved at eksperimentere med og ændre i dette program.

Som baggrundsliteratur om hashing anbefaler vi materialet man kan finde på denne hjemmeside.

Udvidelser

Her forslag til hvad man kan gå i gang med efter fællesdelen. Rækkefølgen af disse forslag er vilkårlig.

Om brug af Java

I dette afsnit kan man læse nogle udvalgte informationer om brug af Java. Man kan finde yderligere og mere grundlæggende informationer på hjemmesiden for grundlæggende programmering. Desuden er her et link til Java API specifikationen.

I forbindelse med kørsel af SearchCmd har man brug for at angive parametre til main metoden. Desuden er det i forbindelse med flere af de foreslåede udvidelse nødvendigt at bruge såkaldte jar filer. I de følgende afsnit er det beskrevet hvordan man gør disse to ting i forskellige Java udviklingsmiljøer.

Generelt kan det nævnes at en jar fil indeholder funktionalitet udover den der findes i selve Java. En jar fil er nødvendig både når man oversætter og når man udfører et program der benytter sig af den ekstra funktionalitet. Alle de jar filer der er henvist til på hjemmesiden for søgemaskineprojektet findes også i kataloget:

  s:\sysadm

BlueJ

I BlueJ kører man et program ved at udføre main metoden. Der kommer så en dialogboks frem hvor man skal angive programparametrene. Her kan man eksempelvis angive:

  {"s:\\sysadm\\soegemaskine\\itcwww-small.txt"}

Bemærk de dobbbelte backslasher.

I BlueJ kan man anvende .jar filer ved at gå ind i Options og dernæst Preferences. Man skal så vælge fanen Libraries. Man skal så trykke Add og så finde den jar fil man skal bruge.

JCreator

Hvis man bruger JCreator til at oversætte og udføre Java programmer og hvis man har problemer med at få oversat og kørt de rette programmer, så kan det anbefales at gå ind i File menuen og vælge Close workspace hver gang JCreator startes op.

Man kan angive hvilke parametre man vil give til et programs main metode på følgende måde: Vælg Configure menuen. Vælg dernæst Options og så JDK Tools. Vælg så i feltet Select tools type værdien Run application og tryk på <default>. Tryk så Edit og vælg fanen Parameters. Parametrene kan så skrives i feltet Main (...).

Man kan benytte en jar fil ved i menuen at vælge Configure, dernæst vælge Options og så vælge JDK Profiles. Man skal så vælge JDK version 1.3 og vælge Edit. Man skal så trykke på Add og vælge Add package og man skal angive den jar fil man ønsker at bruge.

Kommandolinjeprogrammernre

Den helt klassiske måde at køre og oversætter java programmer på er via de såkaldte kommandolinje programmer. Man kan oversætte programmet i SearchCmd.java på følgende måde:

  javac SearchCmd.java

Man kan så køre dette program med den lille datafil på følgende måde:

  java SearchCmd s:\sysadm\soegemaskine\itcwww-small.txt

Hvis man vil benytte en jar fil gør man det ved at tilføje den til den såkaldte CLASSPATH. Dette er allerede gjort for de jar filer der henvises til fra hjemmesiden for søgemaskine projektet.


Administrativt

Vigtige datoer

Projektformular

Hver gruppe skal udarbejde en projektformular. Denne skal afleveres underskrevet af en lærer senest d. 13 Maj i studieadministrationen. I projektformularen indgår der en projektbeskrivelse og her er det tilstrækkeligt at angive en reference til denne hjemmeside. I projektformularen skal hvert gruppemedlem endvidere angive hvilke forudsætninger medlemmet har for projektet. Dette omfatter relevante kurser, uddannelser, erfaringer m.m. fra IT-C og fra andre steder.

Projekteksamen

Tidspunktet for eksamen vil blive offentliggjort senere.

Der vil udarbejdet en eksamensplan snarest muligt efter at projekterne er afleveret.
Eksamensplan er ikke klar endnu

Hver gruppe skal forsvare sin rapport ved en mundtlig eksamen. På basis af rapporten og forsvaret gives der en individuel karakter på 13-skalaen for hver deltager i gruppen.

Projektdage

Under projektperioden vil der være dage hvor projektgrupperne har mulighed for at få hjælp til projektet m.m.

Nedestående projektdage kan blive ændret efter behov. Projektdagene bliver afholdt i lokale 0.15 og 0.19.

Projektgrupper

Hvis du er interesseret i projektet i søgemaskiner skal du straks skrive til stephen, hvor du samtidig oplyser om hvilke tekniske kurser du har haft.
Nedenstående projektgrupper skal betragtes som foreløbige projektgrupper. Indtil videre er blot listet de studerende som på dette tidlige tidspunkt har ytret interesse for projektet.

Bemærk, der skal være mindst to deltagere i en gruppe, med mindre andet er aftalt med projektvejleder. Vi anbefaler dog mindst 3 personer i hver gruppe.
Hvis du er medlem af en gruppe med få medlemmer skal du forsøge at kontakte andre grupper via nedestående mail, for at flette grupperne sammen. Hvis der til den første projektdag stadig er grupper med kun et medlem, vil vi denne dag forsøge at flette disse grupper sammen.

Gruppe 1 (SA) : Marianne Skafte Ritschel, Dorina Neuman, Morten Skaarup Jensen(OOP)
Gruppe 2 (SA) : Nabila Hejazi, Sara Pors Jepsen, Melihat Zengin (GP, DBD, ITPO, DB, NP)
Gruppe 3 (TR) : Susanne Munkebo Christiansen, Jakob Tholle (GP, Webprog.)
Gruppe 4 (TR) : Jonas E. Andersen, Bjørn E. Petersen, Lars E. Sonne, Susanne Bisggard (OOP,DB,IAD,SP)
Gruppe 5 (SA) : Bjarke Meier, Lisbeth Hove Høgsbro (IAD, VOOP,NP,OMP,INP,DS,PS,EAP,DSK,VOP)
Gruppe 6 (TR) : Kira Høegh, Karen Binderup Jørgensen (IAD,OOP)
Gruppe 7 (SA) : Henrik Jensen, Lisbeth Nielsen, Peter Pilgaard Rasmussen, Thomas Demant (IAD)
Gruppe 8 (SA) :Jan Mogensen, Allan Rosentjørn (GP, DBD, ITPO)
Gruppe 9 (TR) : Jens Lind, Solvejg Vibeke Reeh, Mads-Jørn Nørgaard (webprogrammering)
Gruppe 10 (TR) : Lotte Dybbro, Asger Knudsen (GP,IS, IM,MMT)
Gruppe 11 (TR) : Louise Sofie Kehler, Susanne Gheorghe (DKM,GP)
Gruppe 12 (TR) : Jakob Karlsen, Jakob Andreas Wrang, Bjørn Wahlberg, Jens Bo Bjørholm
Gruppe 13 (SA) : Abdellatif Karoub, Hamdy Hassan, Lone Gram Larsen (GP, NP, ITPO)
Gruppe 14 (TR) : Pernille Kruse og Kinnie Pedersen (GP, OOP, DBS)
Gruppe 15 (SA) : Frederik Weeth, Karl Sæberg (DBD, ITPO,GP)
Gruppe 16 (SA) : Lars Erik Udsen, Jonas Ask Homaa, Andreas Mikkelsen (GP, DBD, ITPO, DKM)
Gruppe 17 (TR) : Michael Christoffersen, Peter Ulrik Rindal (GP, NP, DBS)
Gruppe 18 (TR) : Mette Berger (GP, ITPO, DBD)

Alle lærere og studerende

Lærere

Stephen Alstrup (Lærer), email:stephen@it-c.dk
Theis Rauhe (Lærer), email:theis@it-c.dk
Philip Bille (Instruktor), email:beetle@diku.dk
Jacob Borella (Instruktor), email:jborella.it-c.dk

Instruktorvagtplan

Instruktorerne sidder i lokale 1.80 (eller går rundt i terminalrummet) fra og med onsdag d. 8/5. Følgende vagtplan bliver opdateret og udvidet løbende. Hvis efterspørgslen efter instruktorerne er lille en dag kan det være vi går hjem tidligt.

Dato Tid Instruktor
Ons 8/5 10.00-16.00PB
Tor 9/5
Fre 10/5 13.00-16.00PB/JB
Man 13/5 12:00-16:00 JB
Tir 14/5 12.00-16.00 JB
Ons 15/5 10.00-16.00 PB
Tor 16/5 13.00-16.00 PB
Fre 17/5 13.00-16.00 PB
Man 20/5
Tir 21/5 12:00-16:00 JB
Ons 22/5 12.00-16.00 PB
Tor 23/5 12.00-16.00 PB
Fre 24/5 13.00-16.00 PB
Man 27/5 12:00-16:00 JB
Tir 28/5 12.00-16.00 JB/PB
Ons 29/5 10.00-16.00 JB/PB