Programmering FK Sammanfattning

Sammanfattning Programmering Java Fortsättningskurs

Interface, exceptions, Java Colections

Förklara begreppen: abstraktion, abstrakt datatyp, speciﬁkation, implementation, interface, pre- och post-conditions

ADT: En abstrakt modell tillsammans med de operationer man kan utföra på den.

Interface betyder gränssnitt och innehåller ingen implementering utan endast ”regler” som man måste implementera. Alla metoder är publika. En klass kan omplementera flera interface men bara ärva en klass. Fungerar som ett kontrakt.

Pre conditions: Villkor som måste vara uppfyllda för att en metod ska kunna utföra sin uppgift.
Post conditions: Beskriver hur metoden ändrar tillståndet på objektet

Deklarera interface i Java

public class MyComplexNumber implements ComplexNumber {

Skriva programkod för att fånga exception

Normalt fångar man det i en try-catch-sats. Kan själv välja vad som ska hända efter en felsituation har uppstått.
Scanner scan = null;
try {

// försöker öppna en fil med namnet fileName

scan = new Scanner(new File(fileName));

} catch (FileNotFoundException e) {

System.err.println("Couldn’t open file " + fileName);

System.exit(1);

{
... använd scan

Skriva metoder som genererar exception

public void deposit(int n) {

if (n < 0) {

throw new IllegalArgumentException("amount to deposit < 0");

}

balance = balance + n;

}

Förklara begreppen: generik, typparameter, autoboxing och unboxing

Autoboxing :automatisk konvertering från primitiv typ till objekt av motsvarande wrapper-klass

T.ex Integer k = 3;

Unboxing: automatisk konvertering av objekt av wrapperklass till motsvarande primitiva typ

T.ex int j = k;

Generik: public class ArrayList<E> {...} ger oss möjlighet att skapa generella klasser som klarar av att lägga in alla möjliga olika object i klassen men även göra det mer restriktivt med t.ex <Integer>

Använda en iterator för att traversera en samling element

Alla klasser som implementerar collection måste även implementera även metoden iterator()
Man skaffar sig en iterator genom att anropa metoden iterator. Iterator<Person> itr = pList.iterator();

Implementera iteratorer för enkla datastrukturer som listor och vektorer

Förklara interfacet Comparable och kunna implementera detta interface

Objekt av klasser som implementerar Comparable går att jämföra med varandra returnerar en Integer -1 0 +1 om mindre än, lika eller större än det jämförda objektet.
CompareTo vs .equals:

equals finns i superklassen Object och returnerar true om de jämförda objekten är identiska.

Säg att p1,p2 och p3 är en referens till typ Pelle 19år. P1 och p2 refererar till samma objekt medan p3 refererar till ett annat men som heter samma sak.Javas operator == tillämpad på referenser testar just referenslikhet, alltså om två referenser
pekar på samma objekt. Vid ovanstående situation skulle alltså p1 == p2 ge true medan
p1 == p3 skulle ge false. Boolean equal fungerar på samma sätt som operatorn ==.

Ibland vill vi kanske veta om objekten är samma men i ett annat fall vill vi kanske testa ifall objekt p1 och p3 har samma namn. I detta fallet kommer p1.equals(p3) att ge true eftersom man har överskuggat equals i klassen String och därmed kollar värdet på attributen istället.

Metoden compareTo används t.ex vid sorteringar när det är nödvändigt att veta om objektet även är större, mindre eller lika med det andra objektet.

Formulera testfall och använda JUnit för att testa klasser.

Förklara begreppen: skuggning, överlagring, polymorﬁsm

Mer om generik

Generik och arv

Wildcards

? är wildcard. Collection<?> är en ”collection of unknown”.
public static void printCollection(Collection<?> c) {

for (Object e: c) {

System.out.println(e);

}

}
Nu kan metoden anropas med objekt av godtycklig collection-klass t ex
Collection<Object> eller LinkedList<String>.

Ibland behöver man ange begränsning på typparmetern till en generisk
klass:
public class ASortedCollection<E extends Comparable<E>>
Typparametern <E extends T> betyder att E måste vara subklass till T om T är en klass. Det är också tillåtet att E = T.
E måste implementera interfacet T om T är ett interface. I exemplet ovan anger vi alltså att E måste vara en typ som implementerar interfacet Comparable<E>. Vi kan därmed använda metoden compareTo på objekt av typen E i implementationen av ASortedCollection.
<? extends E> är exempel på ”wildcard med begränsning”.
<? extends E> kan utläsas: ”okänd subklass till E. Typ vi vet inte vilken typparameter som kommer in, men den måste ärva från E.
E extends Comparable<? super E> kan utläsas ”E implementerar interfacet Comparable<T> där T är en okänd superklass till E (vilket inkluderar E)”

Vektorer och generik

Generiska metoder

Även metoder kan ha typparametrar

Listor, köer, stackar

Förklara vad en lista, kö och stack är för någonting och vilkaoperationer man förväntas kunna utföra på dem.

En lista innefattar positionsbegrepp. T.ex första/ sista elementet i en lista samt efterföljande element av ett annat element. Dock ej sorterade.

En enkellänkad list ser ut såhär:

Förklara vad nästlade och inre klasser är för något samt kunna implementera sådana

En klass som är deklarerad inuti en annan klass kallas för en nästlad klass. Detta används oftast då klassen endast är meningsfull för den omslutande klassen och användaren behöver inte veta om klassen. I den omgivande klassen har man tillgång till allt som finns i den nästlade klassen även om den är deklarerad private.
I den nästlade klassen kan man komma åt allt som finns i den omgivande klassen såvida inte den nästlade klassen är deklarerad som static, då kommer den bara åt de attribut som är static i den omgivande klassen.

Använda klasser och interface från Java Collections Framework såsom List, Queue, ArrayList, LinkedList, Iterator, ListIterator och Iterable

ArrayList – implementeras med vektor. Använd om alla insättningar görs sist i listan. Annars blir det omflyttningar.

LinkedList – implementeras med en dubbellänkad cirkulär struktur.

ListIterator – är som en iterator fast med lite fler tillagda metoder för att röra sig bakåt i listor och för att sätta in element.

Algoritmers effektivitet

Förklara begreppet tidskomplexitet.

Tidskomplexitet är ett begrepp på en dataalgoritms storlek. Ibland säger man bara komplexitet om tidskomplexitet
hög tidskomplexitet ⇐⇒ dålig eﬀektivitet ⇐⇒ dyr, hög kostnad
låg tidskomplexitet ⇐⇒ eﬀektiv ⇐⇒ billig, låg kostnad
Tidskomplexiteten ska uttryckas som en funktion av problemets storlek.

Tidskomplexiteten ska uttryckas så att vi är oberoende av vilken dator.
Man räknar därför på hur många basala (som tar konstant tid) operationer som utförs av varje algoritm. Om man utför n operationer är tidskomplexiteten T(n) = n. Den verkliga tidsåtgången blir då c *T(n) där c är en konstant för hur fort en viss dator räknar den basala operationen.

Beräkna tidskomplexiteten T(n) för enkla algoritmer (av den svårighetsgrad som behandlats på föreläsningar och övningar).

Uttrycka tidskomplexitet med O (ordo) och förklara vad det innebär att tidskomplexiteten är O(f (n)).

Ordo kommer från matematiken och är ett sätt att begränsa uppåt. Funktionen kan alltså inte bli större än ordo av funktionen.
Om man vill ange tidskomplexiteten med ordo är det bara att stryka de termer som är minst dominanta. En eventuell konstant på den dominerande termen kan också strykas.

Förstå vad olika storleksordningar på tidskomplexiteten innebär för algoritmers användbarhet (konstant, logaritmisk, linjär, kvadratisk,exponentiell,...).

Förstå och kunna använda sambandet mellan verklig tidsåtgång och teoretiskt beräknad tidskomplexitet, t(n) ≈ c ∗ T(n).

Avgöra när en algoritms tidskomplexitet beror på indata och i sådana fall kunna beräkna tidskomplexitet för värsta fall, W (n). Kunna förklara vad som menas med tidskomplexitet i medelfall, A(n), för algoritmer vars tidskomplexitet beror på indata.

Tidskomplexitet kan bero på indata. Då kan vi inte säga exakt hur många gånger som den utförs. Man frågar sid då två saker:

Vad är tidskomplexiteten i medelfall? A(n)

Vad är tidskomplexiteten i värsta fall? W(n)

Medelfall beräknas genom ∑ Pi*Ti(n) och är alltså sannolikheten att just en viss tidskomplexitet ska inträffa vilket blir ett medelvärde. Är sannolikheten stor att det man skickar in ger en hög tidskomplexitet kommer också viktningen att dras åt det hållet.
Worst case är lite lättare att räkna ut eftersom man slipper alla sannolikheterna. Det är egentligen bara att klura ut vad det värsta kan vara och räkna därefter. W(n) = max Ti(n)

Rekursion

Förklara begreppet rekursion.

Betyder att anropa sin egna metod från metoden

Förklara hur rekursion fungerar.

Man delar upp problemet i mindre delar för att till slut komma till något som är lätt att lösa. Som en pyramid. För att det ska fungera krävs ett basfall som redan är klart. (utrycks explicit)

Så här fungerar metodanrop i allmänhet, vilket kan vara bra att komma ihåg vid rekursiva algoritmer.
En rekursiv metod måste ha:

En eller ﬂera parametrar som bestämmer problemets storlek

Ett eller ﬂera basfall som löses direkt.

Ett eller ﬂera rekursiva anrop. De rekursiva anropen måste leda till att ett basfall så småningom nås.

Induktion?

Förklara begreppet söndra-och-härska i samband med rekursion.

Söndra-och-härska begreppet är en teknika för att konstruera rekursiva algoritmer. Man gör minst två anrop som delar upp problemet i mindre delar. Sedan löser man problemet och sätter ihop. Detta kan man göra på t.ex sorteringsalgoritmer som då blir snabba.

Använda dynamisk programmering för att eliminera onödiga rekursiva anrop.

Dynamisk programmering betyder att man håller reda på de rekursiva anrop som redan har räknats ut. Man håller reda på det som räknats ut i en tabell och vid anrop av just ett redan uträknat anrop skickas värdet från tabellen tillbaka. Annars görs det rekursiva anropet.

Man bör använda rekursion när det är svårt att lösa det på annat sätt. Med andra ord då det blir lättare med rekursion. Det är lätt att det går långsamt, men kan lösas effektivt.

Kraftfull teknik för att konstruera algoritmer:

Vissa problem löses enklast med rekursiv teknik.

Gäller t ex algoritmer som manipulerar datastrukturer som träd och grafer.

Enkelt att översätta rekursiv algoritm till program.
Enkelt att visa att en rekursiv algoritm är korrekt.
Rekursiv teknik leder ibland till eﬀektivare lösning av problem där det ﬁnns alternativa icke-rekursiva algoritmer.

T ex sortering

Ibland leder dock rekursion till väldigt ineﬀektiva algoritmer.

Kan t ex inträﬀa i algoritmer som gör mer än ett rekursivt anrop när detta leder till att samma instans anropas ﬂera gånger.

Träd, Binära träd, Set, Comparable, Map

Förklara begreppen träd och binära träd och därmed sammanhörande begrepp såsom rot, löv, subträd, förälder, barn. Förklara begreppen nivå/djup för en nod. Förklara begreppet höjd för ett träd.

Träd – Ett träd består av en rot och noll ett eller flera subträd

Binära träd – Är ett träd där varje nod har enbart 2 barn

Rot – Den enda nod som saknar förälder

Löv –nod som saknar barn

Gren – Sammankoppling av två noder

Nivå = Djup - Rotens nivå = 1 och nivån för en nod ges av förälderns nivå + 1

Höjd – max(nivå)

Förklara hur träd kan implementeras med länkad datastruktur.

Man skapar en klass Node som innehåller tre attribut. En som håller reda på själva datan i noden. En som håller reda på dess vänstra barn och ett som håller reda på dess högra barn. Left och right länkar alltså vidare till en nod.

Beskriva olika sätt att traversera träd: preorder, inorder, postorder.

Traversera betyder att man går igenom alla noder i träder.
Preorder: Rot, vänster i preorder, höger i preorder

Inorder: Skriver ut ”iordning” från vänster till höger. Mao vänster inorder, rot, höger inroder.

Postorder: Som Preorder fast tvärtom. Vänster i postorder nedifrån, höger i postorder nedifrån sist orten.

Implementera operationer på träd, speciellt rekursiva operationer.

Förklara begreppet binära sökträd.

Lagrar elementen med hjälp av en söknyckel. T.ex att 1 är lägre än 4. Eller Anna hamnar för Bertil. Nycklarna i vänster subträd är mindre än roten som är mindre än höger subträd. Man vill alltså ha roten i mitten. Dubletter tillåts ej i binära sökträd
Fördelarna är att man enkelt och snabbt kan sätta in, ta bort, söka upp element.
Traverserar man ett binärt sökträd i inorder får man alltså ut trädet växande enligt söknyckeln (bokstavsordning, nummerordning, osv).

Förklara hur insättning, sökning och borttagning i ett binärt sökträd går till och kunna implementera sökning och insättning.

Sökning – När man söker i ett binärt sökträd börjar man från roten och jämför sedan om värdet är större eller mindre än nodens element. Är det sökta värdet mindre går vi till nodens vänstra barn och upprepar proceduren. På samma sätt går man till höger om värdet är större. Returnerar null om värdet inte överensstämmer med noden man är på och noden saknar barn (misslyckad sökning)
Insättning - När man sätter in ett nytt element i trädet är det viktigt att ordningen bevaras. Inga dubletter får förekomma. Man kan därför göra insättningen som en misslyckad sökning. Om noden som man söker inte finns med i trädet sätter man in den på den plats där man är när sökningen misslyckas.
När man jämför använder man compareTo eftersom man är intresserad av ordningen i detta fallet.

Borttagning :

Sök upp elementet

koppla ihop föräldern med något av barnen

Sammankoppling sker på olika sätt om noden har 0,1 eller 2 barn
- 0: Sök upp, sätt elementet till null
- 1: Sök upp, sätt parents referens till noden till nodens barn
- 2: Sök upp, konstatera att det är två, hitta minsta noden i nodens högra subträd flytta datan från denna till noden som ska tas bort. Tag bort den minsta.

Förklara begreppet balanserat binärt sökträd (AVL-träd) och varför man vill ha balanserade träd.

Höjden av ett sökträd är mellan gränserna som ni ser nedan. Eftersom operationerna som visats innan går längs med en gren som max kan vara höjden lång ger därför längden på grenen ett mått på tidskomplexiteten. Tidskomplexiteten är alltså O(h) vilket är som längst när trädet är en enda lång gren. Som minst är det när trädet är balanserat (när varje nivå har så många noder som är möjligt) Därför vill man ha balanserade sökträd.
Balanserat binärt träd: Ett binärt träd är balanserat om det för varje nod i trädet gäller att höjdskillnaden mellan dess båda subträd är högst ett

Ange tidskomplexitet för operationer på binära sökträd, såväl obalanserade som balanserade.

2log(n + 1) ≤ hö jden ≤ n
Tidskomplexiteten är O(höjden)
Om ett binärt sökträd hålls balanserat kommer sökning, insättning ochborttagning därmed att kosta O(2log n) i värsta fall

Använda interfacen Map och Set och deras implementerande klasser i Java Collections Framework.

Set: Är en mängd element som inte innehåller några dubletter. Typ samma som Collection fast med restriktionen att inte ha några dubletter.
Sorted set: Förutsätter att elementen som sätts in går att jämföra med varandra. iterator() returnerar en iterator som går igenom mängden i växande ordning.
Map: I map är varje element tvådelat. En nyckel och ett tillhårande värde Det kan finnas flera värden, men bara en nyckel.

Känna till och kunna implementera interfacet Comparator.

Comparator kan man använda när man vill jämföra objekt i en klass på olika sätt. T.ex både med Comparator och CompareTo.

Förklara begreppen hashtabell och hashfunktion.

En hashfunktion avbildar en nyckel på ett heltal så att man lätt kanläga in och hitta nycklar i t.ex lista vektor. En bra hashfunktion förväntas ge lågt antal kollisioner samt bör påverkas av alla delar av nyckeln.

Deﬁniera vad som menas med sluten och öppen hashtabell och hur kollisioner hanteras i sådana tabeller.

Man kan implementera en hashtabell på olika sätt.
Sluten Hashtabell – En vektor används för att lagra objekten. Man måste hantera kollisioner på något sätt.

Linjär teknik; första lediga plats efter

Kvadratisk teknik; undviker primär klustring att alla värden samlas på samma ställen. Funkar inte nästa hoppar den till 22 steg bort, funkar inte det går den 32

Öppen hastabell – En vektor med listor används för att lagra. Listan tar på så sätt hand om kollsionerna. Alla element vars nyckel avbildar på platsen k i vektorn hamnar i dess lista.
Om en klass omdeﬁnierar equals, så måste den också omdeﬁniera hashCode() – Objekt som är lika enligt equals ska ha samma hashkod.

Förklara vad som menas med fyllnadsgraden (eng: load factor) för en hashtabell.

Fyllnadsgraden är element/tabellplatser

Förklara hur sökning, insättning och borttagning går till i slutna och öppna hashtabeller.

HashSet<Person> set = new HashSet<Person>();

Person p = new Person("Kalle");

set.add(p);

Ange tidskomplexiteten för operationer på hashtabell i värsta fall och medelfall.

Tidskomplexiteten är i värstafall O(n) (om alla element har hamnat i samma lista) vilket är osannolikt om man har en bra hashfunktion. I medeltal ger det O(1) om man inte sätter in fler element än 2*tabellstorleken.

Prioritetsköer, heapar, heapsort

Redogöra för vilka operationer som skall ﬁnnas i den abstrakta datatypen prioritetskö.

Sätta in element

Ta reda på det högst prioriterade elementet

Ta bort det högst prioriterade elementet

Redogöra för olika sätt att implementera en prioritetskö och kunna jämföra dem med avseende på tidskomplexitet.

Det finns inget givet interface i java för prioritetsköer det man gör är att man använder interfacet Queue<E> och skapar en klass PriorityQueue<E> som implementerar Queue<E>

I klassen skapar man:

Offer

Peek returnerar minsta elementet i kön

Poll – tar bort minsta elementet (lågt värde)

Använda klassen java.util.PriorityQueue

Lågt värde anger hög prioritet.
Finns två konstruktorer i java.util.PriorityQueue en som förutsätter att du implementerar comparable och den andra använder sig av comparator.

Förklara begreppet heap

En heap är ett komplett binärt träd är varje nod innehåller ett element som är mindre än barnens element.

Och minsta värdet är högst upp.

Förklara hur en heap kan implementeras med hjälp av en vektor

Man lägger till element i vektorn på första lediga plats vilket gör att heapen kommer att få rätt form. Sätt in vektorn i heapen och addleaf eller percolate up beroende på om elementet är på rätt plats i heapen.

Förklara hur insättning, borttagning och sökning efter högst prioriterat element går till i en heap och ange dessa metoders tidskomplexitet.

Offer: O(2log n) i värsta fall men o(1) i medeltal

Peek: Minsta värdet är ju alltid på plats 0 i vektorn  O(1)

poll:

Tag bort noden på plats 0 i vektorn.

Ersätt med den som ﬁnns på sista plats.

Ger rätt form, men roten har nu troligtvis fel storleksförhållande till sina barn.

Byt med minsta av barnen tills ordningen ok. Kallas percolate down eller addroot.

I värsta fall måste vi byta med alla O(log n) även medelfallet.

Förklara hur man bygger en heap på linjär tid från en osorterad samling

Redogöra för algoritmen Heapsort och dess värstafallstid.

Sorterar n element i en vektor på plats.

Eﬀektiv – O(n log n) i värsta fall.

Efter k steg i algoritmen är de k största elementen sorterade.

Metoden kan alltså avbrytas om vi endast vill ta reda på de k största elementen.

Sortering

Redogöra för och jämföra olika sorteringsalgoritmer:

Insättningssortering i vektor
- Ta nästa element och sätt det på rätt plats bland de sorterad elementen
- O(n2)
- Dock bra om nästan sorterad  O(n)

Urvalssortering i vektor
- Sök upp det minsta byt plats med första elementet i den osorterade delen
- O(n2)
- Bra att använda för små n

Mergesort
- Söndra härska
- Sorter vänster, höger, samsortera
- n log n
- I praktiken långsammare än quicksort
- Kräver extra minnesutrymme

Quicksort
- Sämre än mergesort och heapsort i värsta fall
- Bättre i medelfall
- Pivot
- Inget extra minnesutrymme krävs
- O(n log n) bästa
- O(n2)

Heapssort
- O(n log n) Kan utformas så att inget extra minnesutrymme krävs.
- I praktiken långsammare än Quicksort.
- Efter k pass är de k största elementen sorterade. Kan därför vara lämplig om man bara vill få fram de k största

Samsortera två sorterade följder

Det minsta elementet i varje vektor jämförs med varandra och det minsta läggs in i den nya vektorn.

Förklara begreppen pivot-element och partitionering (Quicksort).

Använda idéerna från sorteringsalgoritmerna för att lösa andra problem (t.ex. partionering från quicksort eller sammanslagning av sorterade följder från mergesort ( se t.ex. övning 5).

Similar

Sök Wikisida

Senast ändrad

...more

Sammanfattningar

File Galleries

Data

Ekonomi

Filosofi

Juridik

Matematik

Medicin

Psykologi

Språk

Statsvetenskap