5024.17 - Algoritmur og datastrukturar
Skeiðsnummar
5024.17
Heiti
Algoritmur og datastrukturar
ECTS
7,5
Fortreytir
Diskret støddfrøði; Linear algebra fyri KT-verkfrøðingar; Innleiðandi forritan við Java, C ella C++.
Endamál
- Innleiðing í teknskipan, frøðimál, og arbeiðshættir ið verða brúkt í samband við algoritmur.
- Innleiðing í standard algoritmu-design-mynstrini, ið verða brúkt í menningini av góðum algoritmu-loysnum.
- Innleiðing í tey støddfrøðiligu amboðini, sum krevjast til at greina algoritmur við atliti til brúk av formligum myndlum í Tíð og Rúmi.
Innihald
Innleiðing
o Skilmarking av algoritmu, at telja grundleggjandi operatiónir við inning, worst-case greining av koyritíð og lagurkrøvum – fyri fleiri dømir av einføldum algoritmum.
o Design av pseudo-kodu-algoritmum.
Torgreindis-evnir
o Asymptotulæra og "raðfylgja av" teknskipan fyri torgreind.
o Samanbering av polynomiu-tíð og eksponential-tíðar torgreindum og dømir um algoritmur við slíkum torgreindum.
o Stutt innleiðing um funktiónir sum kunnu roknast út (computable) og sum ikki kunnu roknast út (non-computable).
Yvirlit yvir graf-strukturar og teirra ímynding.
o Stýrdir og óstýrdir grafar; trø; ímynding við granna-matricum og hendinga-listum, graf og træa-tvørturumferðing.
Algoritmu-Design-Teknikkir
o Yvirlit yvir standard algoritmu-design-mynstrini sum vanliga verða brúkt í Computer Science saman við eyðkendum dømis-uppgávum ið verða loystar á hendan hátt.
o Yvirlit: hví tørvur er á nógvum design hættum.
o Divide-and-Conquer-algoritmur: yvirskipað yvirlit av of hátti; koyritíðar-greining av einføldum Divide-and-Conquer hættum umvegis loysnum til endurtøku relatiónir.
o Dynamisk Forritan: Divide-and-Conquer munir; generelt yvirlit; tørvur á endurtøkuverkseting.
o Greedy Hátturin: optimeringstrupulleikahugtakið og skilnaðurin ímillum ‘neyvar’ og ‘umleið’
algoritmuloysnir.
Læru- og undirvísingarhættir
Fyrilestrar, teoretiskar og teldu-grundaðar uppgávur og tímar við uppgávuvegleiðing.
Læruúrtøka
Tá skeiðið er liðugt, skal tú sum lesandi kunna:
- lýsa standard algoritmur, so sum sorteringsalgoritmur, leitialgoritmur, string-makaalgoritmur, graph traversal algoritmur;
- brúka hesar algoritmurnar, ella eina givna pseudo-kodu algoritmu, til at loysa eina setta uppgávu;
- gera einfaldar asymptotiskar greiningar av algoritmum við at inndraga sekvensir, úrval og endurtøku, og eyðmerkja og samanbera einfaldar eginleikar fyri hesar algoritmur;
- lýsa algoritmudesign-meginreglurnar fyri ‘divide-and-conquer’, greedy háttin, og dynamiska forritan og skilja munin millum hesar meginreglur;
- brúka tær kannaðu algoritmurnar, sum lýsa hesar design-meginreglurnar;
- brúka hesar kannaðu design-meginreglurnar at gera algoritmuloysnir til settar uppgávur;
- greiða frá og lýsa munin millum ymsar uppgávuklassar, serliga polynomiska tíð og eksponentialar tíðarloysiligar uppgávur.
Próvtøkuháttur
ein ella tvær metingar verða givnar gjøgnum fyrilestrarnar
o telur 0% av endaliga karakterinum, men vit heita staðiliga á teg um at standa hesar uppgávurnar, hóast tað ikki er ein treyt fyri at fáa loyvi til at fara upp til endaligu próvtøkuna
4 tímar skrivlig próvtøka (við pappíri og blýanti/penni)
o bøkur og tilfar frá skeiðnum eru IKKI loyvd at hava við
o telur 100% av endaliga karakterinum
Próvdøming
Uttanhýsis
Próvtalsstigi
7-talsstigin
Lestrarlisti
Viðmældar bókmentir:
Introduction to the Design and Analysis of Algorithms, Anany V. Levitin, Villanova University, 2011 (Third Edition), Addison-Wesley
Víðari lesnaður:
Introduction to ALGORITHMS, TH Cormen, CE Leiserson and RL Rivest, MIT Press/McGraw-Hill, 3rd Edition, 2009
Ábyrgd
Qin Xin