Mål:

Kunna använda hashning och anpassa den till ett givet problem (hashfunktion, tabellstorlek, krockhantering)
Kunna beskriva en graf som grannmatris och grannlista samt rita upp den.

PERFEKT HASHFUNKTION

Hitta på en perfekt hashfunktion för atomer. Hur stor blir hashtabellen?

lösning

HÅLL REDA PÅ MEDIA (Tildatenta 030308)

Under gulfkriget var det väldigt svårt för armestaben att hålla reda på alla TV-bolag som for omkring och rapporterade i öknen. För att hålla reda på dem användes en hashvektor. Koden fungerade inte som avsett och man har nu gett i uppdrag åt en f.d. tildastudent att titta på en misstänkt del av koden:

from string import findhashningKunna tillämpa algoritmer för sortering,

p = 100;
hashvektor = [0]*p
alfabet = "abcdefghijklmnopqrstuvxyz"

def put(tvbolagsnamn, tvbolag):
    hashcode = 0
    for i in range(len(tvbolagsnamn)):
        alfanum = find(alfabet, tvbolagsnamn[i])+1
        hashcode += alfanum
    hashcode = hashcode % p
    hashvektor[hashcode] = tvbolag

Vad är det för fel på koden? Beskriv hur man kan förbättra den. Namnen på TV-bolagen kan antas bestå av högst tre bokstäver. Det kommer inte att förekomma mer än 75 TV-bolag.

lösning

NIX TILL TELEFONFÖRSÄLJNING (Tilda-tenta 000603)

Föreningen för konsumentskydd vid marknadsföring per telefon har startat ett register dit den som inte vill bli uppringd av telefonförsäljare kan anmäla sig.

Till att börja kommer kontrollen att ske genom att företaget sänder sin telefonlista till nix och får tillbaka en lista där de nixade numren markerats.

Vilka av följande metoder kan föreningen använda sig av? Vilken är bäst? Binärträd, bloomfilter, hashtabell.

Ett framtida mål är att kontroll också skall kunna ske över internet. Då måste kontrollen ske snabbt men man vill också försäkra sig om att ingen ska kunna få ut en lista över alla nixade telefonnummer.

Vilken metod passar bäst för internet-kontrollen?

lösning

Grafer

En allmän graf består av en samling hörn (vertices) med kanter (edges) emellan.
Grafen är riktad om kanterna är riktade (pilar).
Antalet kanter från ett hörn är hörnets grad (degree).
En stig (path) är en väg från ett hörn till ett annat, dvs en följd av intilliggande kanter.
En cykel är en stig där man startar och slutar i ett och samma hörn.
Om grafen inte har några cykler är den acyklisk.
I en viktad graf har kanterna vikter.

Abstrakt datatyp för grafer

Följande metoder skulle en graf kunna ha:

addVertex(node) Lägger till hörnet node till grafen.
addEdge(node1, node2) Drar en kant mellan hörnen node1 och node2.
v = getVertex(key) Hittar det hörn som har nyckeln key
vlist = getVertices() Returnerar en lista med alla hörn.

En graf kan implementeras med en grannmatris (adjacency matrix) eller grannlista (adjacency list).

En grannmatris har ett element för varje möjlig kant mellan två hörn. Elementet kan vara True/False (för en oviktad graf) eller ha ett värde som anger kantens vikt (för en viktad graf).

	A	B	C	D
A		5		1
B	5
C				2
D	1		2

En gles grannmatris ger ineffektiv lagring, så för grafer med relativt få kanter är det bättre att använda en grannlista. Grannlistan har ett element för varje hörn, och i det lagras en lista (eller vektor) med kanterna.

A	[B, 5], [D, 1]
B	[A, 5]
C	[D, 2]
D	[A, 1], [C, 2]

GRANNMATRIS OCH GRANNLISTOR

	A	B	C	D	E	F
A		8	5	6
B			2
C				3
D					1
E	4
F

Rita upp den graf som grannmatrisen ovan representerar. Skriv också upp motsvarande grannlistor. Vilken representation är mest sparsam?

ARKITEKTUR BYGGER SLOTT (C-uppgift från Tildatenta 2018-06-07)

Ett magiskt sagoslott har många rum som är förbundna med varandra. En del rum angränsar till väldigt många rum och andra rum gränsar bara till ett enda. Ibland så ändras planlösningen magiskt. Det som händer då är att antingen så försvinner en förbindelse mellan två rum eller så tillkommer en ny förbindelse mellan två rum.

addVertex(node) Lägger till hörnet node till grafen.
addEdge(node1, node2) Drar en kant mellan hörnen node1 och node2.
v = getVertex(key) Hittar det hörn som har nyckeln key
vlist = getVertices() Returnerar en lista med alla hörn.

En tildastudent får uppdraget att lagra hur rummen är förbundna med varandra i en graf. Man ska kunna

se om två rum är förbundna med varandra,
se vilka rum som är förbundna med ett givet rum,
uppdatera grafen när magi inträffar (rumsförbindelse försvinner/tillkommer).

a) Rita och beskriv kortfattat hur grafen kan representeras som en grannlista.

b) Rita och beskriv kortfattat hur grafen kan representeras som en grannmatris.

c) Jämför grannlista och grannmatris med avseende på prestanda och minnesåtgång för de tre punkterna ovan.

lösningsskiss (se uppg 8 C)