Kursusbasen

Kursusoversigt

Kursusbeskrivelse

Kursusnavn (dansk):	Effektive algoritmer og programmer
Kursusnavn (engelsk):	Efficient algorithms and programs
Semester:	Efterår 2000
Udbydes under:	cand.it., internet- og softwareteknologi (int)
Omfang i ECTS:	0,00
Kursussprog:	Dansk
Kursushjemmeside:	https://learnit.itu.dk
Min. antal deltagere:	10
Forventet antal deltagere:	0
Maks. antal deltagere:	30
Formelle forudsætninger:	Grundlæggende programmering og et kursus i indledende algoritmer og datastrukturer.
Læringsmål:	Mange anvendelser af informationsteknologi kræver effektiv software. For eksempel, har HT en internet-baseret rejseplanlægger (rejseplanen) som skal finde den bedste rute blandt astronomisk mange muligheder i et system med mere end 10000 stoppesteder, 400 bus- og toglinier, 400000 daglige afgange og 1000000 adresser. Selv med nutidens (og fremtidens) computere er det altafgørende, at der her benyttes effektiv software for at rejseplanen hurtigt kan svare på en forespørgsel (inden bussen er kørt...). Kernen i denne og al anden effektiv software er effektive datastrukturer og algoritmer. Målet med kurset er, at du skal kende, kunne anvende og implementere en række grundlæggende, nyttige og effektive algoritmer.
Fagligt indhold:	Du skal forstå algoritmernes opbygning og deres effektivitet samt være i stand til at implementere algoritmerne som effektive programmer. Du skal desuden kunne anvende og tilpasse algoritmerne til løsning af konkrete problemer indenfor bl.a. områderne ruteplanlægning, computer-støttet design, netværk og programmers korrekthed. Endelig skal du være bekendt med og kunne identificere en række hyppigt forekommende svære problemer som kun har delvist effektive løsninger. Kurset er baseret på Cormen, Leiserson, Rivest, "Introduction to Algorithms" MIT Press og udleverede noter. Emner der dækkes: dybde-først og bredde-først søgning i grafer, korteste vej-algoritmer, letteste udspændende træer, hashing, dynamisk programmering, binære beslutningsdiagrammer (BDDer), NP-fuldstændighed og, approksimative algoritmer for svære problemer. Kurset har normalt to parallelle forløb. Den ene forløb består af forelæsninger og opgaveregninger til indøvning af teorien. Det andet forløb består af obligatoriske ugentlige programmeringsopgaver til indøvning af de praktiske færdigheder med effektivt at implementere algoritmerne. På grund af lavt deltagerantal afholdes kurset i semesteret E2000 som seminarkursus med ugentlig vejledning. men uden forelæsninger. Programmeringsopgaverne bliver rettet detaljeret og du får tilbagemeldinger på programmeringsstil og -kvalitet. Kursushjemmeside med bla. lektionsplan.
Læringsaktiviteter:	Vejledning, Opgaveregning, obligatoriske afleveringsopgaver.
Eksamensform og -beskrivelse:	X. experimental examination form (7-scale; external exam), 13-skala, Intern censur Afløsning ved aflevering og godkendelse af 8 ud af 10 stillede obligatoriske opgaver, med bedømmelsen bestået/ikke-bestået.
Litteratur udover forskningsartikler:	NULL