Algoritmer

Lärandemål

• Kunskap och förståelse
• beskriva dina algoritmer och deras egenskaper: förklara algoritmer skriftligen, så att andra kan förstå hur de fungerar, varför de är korrekta och snabba, och var de är användbara.
• inse att icke-triviala beräkningsproblem, som måste lösas med hjälp av algoritmer, dyker upp i olika verkliga datortillämpningar och att formalisera dem.
• intractability: känna igen "intractable problems" och andra klasser av problem som P, NP, NPC.
• bevisa korrektheten av algoritmer.
• Färdighet och förmåga
• design: tillämpa de viktigaste designteknikerna för effektiva algoritmer (t.ex. giriga, dynamisk programmering, söndra och härska, backtracking, heuristiska) på problem som liknar läroboksexemplen men är nya.
• utföra hela utvecklingscykeln av algoritmer: problemanalys, välja, modifiera och kombinera lämpliga tekniker och datastrukturer, analys av korrekthet och komplexitet, fylla i implementationsdetaljer, hitta möjliga förbättringar, etc.
• utföra enkla reduktioner mellan problem, förklara NP fullständighet, känna igen olika beräkningssvåra problem som tenderar att dyka upp om och om igen i olika applikationer, klara, åtminstonei princip, beräkningsmässigt svåra problem med hjälp av heuristik förfiningar av uttömmande sökning, approximativa lösningar, etc.
• Värderingsförmåga och förhållningssätt
• kritiskt bedöma algoritmiska idéer och visa förmåga att motstå frestelsen att skapa uppenbara och till synes rimliga algoritmer (som ofta visar sig vara felaktiga) .
• analysera: förklara varför tidseffektivitet hos algoritmer är avgörande, uttrycka tidskomplexitet på ett rigoröst och vetenskapligt korrekt sätt, analysera tids komplexiteten hos algoritmer (summera operationer i nästlade loopar, lösa vanliga rekursionsekvationer, etc.) det vill säga göra en objektiv bedömning av prestanda för att kunna jämföra med andra algoritmer.
• Var dock medveten om att detta inte är en kurs i programmering! Fokus ligger på design av algoritmer från en given problemformulering och analys av effektiviteten i dessa algoritmer. Det är, så att säga, det analytiska arbete som måste göras innan du skriver någon kod, om man vill lösa ett nytt problem med hjälp av datorer.