KTH
| Nada
| Utbildning
| Teknologer
|
Vi gick igenom betydelsen av abstrakta datatyper/datastrukturer. Detta exemplifierades genom att dels titta på generella abstrakta dataytyper så som stacken, inläsning och utskrift och listan samt dels studerade en egendefinerade abstrakta datatyper fraction. I pdfen finns två ytterligre exemple på egendefinerade abstrakta datayper temperatur och iso2utf.
Övningsanteckningar och MyUtil.py .
Vi gick igenom listor, pekare, binära träd , rekursion och komplexitet. Detta exemplifierades genom att vi skrev remove_second och gcd (greatest common divisor) och . Vi gick även igenom hur binära träd byggs, utag från binärträd med in, pre och postordning samt vi räknade på programtidsåtgång givet en viss programkomplexitet. Övningsanteckningarna innehåller även ett ytterligare ett par program, re- move_every_second, fib (fibonnaccis tal), summa (trädsumma) och height (trädhöjd) som det kan vara bra att kolla på.
Övningsanteckningar och ordlista
Vi gick igenom problemträd, sökning i problem träd med bredden först, och djupet först. Vi exemplifierade det genom att lösa två uppgifter strykord, med djupet först, och sjuor i rad, med bredden först. Titta gärna på den sista lösningen av sjuor i rad som vi inte han med. Där löser vi uppgiften att skriva ut kjedjan av räknesätt fram till lösningen.
Vi igenom problem som handlade om lagring och sortering. Vi löste uppgifter som handlade om hashning, binärträd, bloomfilter, trappor (heap), komplexitet och sortering. Vi gick igenom talen 1-5. Jag rekommenderar att kolla på de återstående talen 6-10. Återkomm gärna till mig med frågor.
OBS: Rättning från övningen för uppgift 1 och uppgift 2. Alfabetet har 26 bokstäver och inte 25 som an- togs på övningen. Uppmärksamma också att i uppgift 1 att bokstav 1 viktas med (nr_bokstav - 1) * 27 och inte nr_bokstav * 25 som ja sa på övningen. Det är bara detlajer och ändrar dock inga slutsater vi gjorde på övningen.
Vi igenom automater, reguljära uttryck och syntax. Vi exemplifierade detta genom att lösa 5 uppgifter. Vi tittade på hur next vecktorn i en KPM automat byggs up, hur reguljära uttryck kan skapas och tolkas samt vi felsökte 4 olika syntax grammatiker och skapade får egna grammatik för att kolla om en websida är rätt skriven.
Idag gick vi igenom komprimering, kryptering och testning. Specifikt löste vi komprimeringproblem med huffmankodning och Lempel-Ziv, funderade på testproblem till lab 5, samt krypteringsproblem rot13, transpo- sitionschiffer och RSA.
Idag räknade vi igenom en tentamen från 12 januari 2010. OBS i många uppgifter kan man svara på olika sätt. Det viktiga är att visa att man förstått.