5024.23 - Algoritmur og dátustrukturar

5024.23

Algoritmur og dátustrukturar

7,5

Diskret støddfrøði; Linear algebra fyri KT-verkfrøðingar; Innleiðandi forritan við Python, Java, ella líknandi forritanarmáli.

At geva teimum lesandi innleiðslu í teknskipan, frøðimál og arbeiðshættir í sambandi við algoritmur umframt innleiðslu í standard algoritmu-sniðgávu-paradigmir, ið verða brúkt, tá virknar algoritmuloysnir skulu mennast. Harumframt at geva teimum lesandi innleiðslu í tey støddfrøðiligu amboðini, sum tørvast fyri at greina algoritmur, tá ið tað snýr seg um formligar myndlar av tíð og rúmi.

• Innleiðsla o Allýsa eina algoritmu, telja støðisatgerðir við inning, greina hægstu (worst case) koyritíð og goymslukrøv hjá fleiri einføldum algoritmum. o Sniðgeva pseudokoto algoritmur. • Kompleksitetur o Asymptotulæra og raðfylgju-teknskipan fyri kompleksitet. o Samanbera polynomiala tíð og eksponentiala tíð og dømi um algoritmur við slíkum kompleksiteti. o Stutt innleiðsla í fatanina av rokniligum (computable) og órokniligum (non-computable) funktiónum. • Yvirlit yvir grafstrukturar og hvussu teir myndast. o Stýrdir og óstýrdir grafar, trø, umboðan av grannamatrisum og insidenslistum, ferðing ígjøgnum grafar og trø. • Algoritmu sniðgávu-teknikkir o Yvirlit yvir standard algoritmu sniðgávuparadigmir, sum vanliga verða nýtt í teldufrøði, saman við eyðkendum dømum, ið verða loyst við hesum sniðgávuparadigmum. o Yvirlit: hví tørvur er á fleiri sniðgávuháttum. o Být-og-vinn (Divide-and-Conquer) algoritmur: heildaryvirlit yvir atløgu (approach); greina koyritíð hjá einføldum být-og-vinn háttum umvegis loysnir við endurtøkusambondum. o Dynamisk forritan: í mun til být-og-vinn, heildaryvirlit og tørv á endurtøkuverkseting. o Gramshátturin (Greedy Method): optimeringshugtakið og munurin millum ‘neyvar’ og ‘umleið’ algoritmuloysnir.

Fyrilestrar og venjingar við støði í ástøði og teldufrøði.

Tá skeiðið er lokið, skal tann lesandi vera før/ur fyri at: - lýsa standard algoritmur so sum skipanaralgoritmur (sorting algorithms), leitialgoritmur, strongmakaalgoritmur, grafferðingaralgoritmur (graph traversal algorithms) - brúka hesar algoritmur ella eina givna pseudokotualgoritmu til at loysa eina ávísa uppgávu - gera einfaldar asymptotiskar greiningar av algoritmum, ið fevna um raðskipan, úrval og endurtøku, og eyðmerkja og samanbera einfaldar eginleikar hjá hesum algoritmum - lýsa algoritmusniðgávumeginreglurnar fyri být-og-vinn, gramshátt og dynamiska forritan og skilja munin millum hesar meginreglur - brúka tær lærdu algoritmurnar, ið lýsa hesar sniðgávumeginreglurnar - brúka tær lærdu sniðgávumeginreglurnar til at gera algoritmuloysnir til eina ávísa uppgávu - greiða frá og lýsa munin millum ymisk sløg av uppgávum, serliga tær, ið kunnu loysast við polynomialari tíð og eksponentialari tíð

 ein ella tvær innlatingar verða á skeiðinum o tær telja 0% av endaliga próvtalinum, men vit heita staðiliga á tey lesandi at standa hesar innlatingarnar, hóast tað ikki er ein treyt fyri at fáa loyvi at fara upp til endaligu próvtøkuna  4 tímar skrivlig próvtøka (við pappíri og blýanti/penni) o tað er IKKI loyvt at hava bøkur og tilfar frá skeiðinum við o próvtøkan telur 100% av endaliga karakterinum

Uttanhýsis

7-talsstigin

Viðmæltar lærubøkur: • Introduction to the Design and Analysis of Algorithms: International Edition, Anany V. Levitin, Pearson, 3rd Edition, 2014 Víðari lesnaður: • Introduction to ALGORITHMS, TH Cormen, CE Leiserson and RL Rivest, MIT Press, 4th Edition Hardcover, 2022

Qin Xin