5024.17 - Algoritmur og datastrukturar

5024.17

Algoritmur og datastrukturar

7,5

Diskret støddfrøði; Linear algebra fyri KT-verkfrøðingar; Innleiðandi forritan við Java, C ella C++.

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

 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.

Fyrilestrar, teoretiskar og teldu-grundaðar uppgávur og tímar við uppgávuvegleiðing.

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.

 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

Uttanhýsis

7-talsstigin

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

Qin Xin