Søgemaskineprojekt for

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

DECEMBER 2001


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.

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. 3 December 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

Eksamen bliver afholdt tirsdag d. 29 januar, 2002.

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.

Til projektet er lokalerne 0.10 og 0.15 reserveret mandag, onsdag og fredag i projektperioden.

Nedestående projektdage kan blive ændret efter behov.

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 : (T) Signe Kyster (GP), Kristian Nyeboe(GP,DB), Claus Harup (GP), Thor Dekov (GP,DB,NP) (F)
Gruppe 2 : (S) Jacob Borella (IAD, OOP, samt andre tekniske fag)
Gruppe 3 : (S) Nasim Odeh (OOP, IADS, NP), Salman Khan (OOP,NP) Kim An Phan (OOP, IADS, DBS), Eydun Jensen (OOP, IADS, NP)
Gruppe 4 : (S) Anders Hasle Nielsen (GP), Lene Hjort Grøndal (GP), Henrik Andersen (GP,IMS), Nicolai Johannesen (GP,PS,BA)
Gruppe 5 : (T) Elizabeth Madsen (OOP, first semester student from EBUSS which prefer english), Hang Zhou (WP)
Gruppe 6 : (S) Michael Frederiksen (WP,DB,NP), Henrik Sørensen (WP,PS,NP)
Gruppe 7 : (S) Maria Sander(GP,DBD,ITPO), Ulf Brandt(GP,DBD,ITPO), Susie Kristensen(GP,DBD,ITPO), Katrine K. Andersen(GP,DBD,ITPO) (F)
Gruppe 8 : (T) Nikolas Dragsdorff, Christina Haustrup (OOP, IADS, ITOP, DBS, DBD), Morten Flintrup (NP,IADS,DB,OOP)
Gruppe 9 : (S) Mohamed Azzouzi (GP, DBS, NP), Rasmus Andersen(GP,DBS,NP), Mark Baumgarten(GP,DBS,NP)
Gruppe 10 : (T) Jakob Karlsen (GP), Jakob Wrang (GP), Tue Rossel (GP)
Gruppe 11 (T) Mads-Jørn Nørgaard (GP,DB))
Gruppe 12 : (T) Jan Højer (IADS) og Henrik Willumsen (IADS)
Gruppe :
Gruppe :
Gruppe :
Gruppe :

Alle lærere og studerende

Lærere

Stephen Alstrup (adjunkt), email:stephen@it-c.dk
Theis Rauhe (adjunkt), email:theis@it-c.dk
Philip Bille (instruktor), email:beetle@diku.dk
Christian Worm Mortensen (instruktor), email:cworm@it-c.dk
Susanne Olsen (instruktor), email:sanne@it-c.dk

Instruktorvagtplan

Instruktorerne sidder i lokale 1.80. Vi har masser af tid så kig forbi.

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
Man 26/11
Tir 27/11 9.00-12.30 PB
Ons 28/11 9.00-16.00
9.00-16.00
PB
CWM
Tor 29/11 9.00-16.00 CWM
Fre 30/11 9.00-16.00PB
Man 3/12 9:00-16:00 SO
Tir 4/12 12.00-16.00 SO
Ons 5/12 9.00-16.00 PB
Tor 6/12 12.00-16.00 CWM
Fre 7/12 9.00-16.00 PB
Man 10/12 13:00-16:15 CWM
Tir 11/12 12:00-16:00 CWM
Ons 12/12 9.00-13.00 PB
Tor 13/12 12.00-16.00 SO
Fre 14/12 9.00-13.00 PB
Man 17/12 13:00-16:15 CWM
Tir 18/12 9.00-12.30 PB
Ons 19/12 9.00-13.00 PB
Tor 20/12 12.00-16.00 SO
Fre 21/12