7. Algoritmer

Färdig för 2023!

Denna laboration är färdig för 2023. Det går bra att börja. Den gamla labben från 2019 finns också kvar för tidigare studenter.

Studiematerial

Innan denna labb påbörjas bör följande studiematerial ha lästs:

Algoritmer

Använd kursmodulen!

Använd kursmodulen (module add courses/TDDE24) för att få rätt version av Python samt tillgång till moduler som används under labben!

7.1 Inledning

Syftet med denna laboration är att öva på att formulera och implementera algoritmer. Kapitel 13 i läroboken behandlar algoritmer, ger exempel på hur man kan tänka och visar hur ett flertal välkända algoritmer ser ut och fungerar.

Checka in och pusha kod ofta, gärna flera gånger om dagen, även om ni inte är klara med labben. Dels är versionshantering bra för att få "kontrollpunkter" som man kan backa till vid behov, dels ger regelbundna incheckningar en tydlig logg över hur arbetet har gått till. Den loggen är inte minst bra för att demonstrera att ni har skrivit programkoden själva!

Kapitlet Algoritmer förbereder för denna laboration.

7.2 Mönstermatchning

Algoritmer för mönstermatchning är användbara vid flera olika tillfällen. Ett av de enklaste fallen är när man vid kommandoraden listar alla filer som börjar med py genom att skriva ls py* där * är ett mönster som matchar i princip vad som helst. I datorintroduktionen i kursen TDDE23 Funktionell och imperativ programmering, del 1 tittade vi också på reguljära uttryck som är en kraftfull och generell form av mönstermatchning.

För den här laborationsomgången ska vi formulera och implementera en algoritm för mönstermatchning i listor. Vi söker igenom listan och mönstret parallellt och försöker se om de matchar varandra. I det här fallet kommer vi inte att matcha tecken för tecken, utan vi matchar element i listan mot varandra i sin helhet. Mönstret ['apa', 'banan'] matchar listan ['apa', 'banan'] men inte listan ['apa', 'konservburk'].

I vår mönstermatchning kommer vi att ha två typer av specialmönster: '&' som matchar exakt ett element, vilket som helst, och '--' som matchar noll, ett eller flera element, vilka som helst. Detta innebär t.ex. att mönstret ['a', '&', 'c'] matchar listorna ['a', 'b', 'c'] och ['a', 'd', 'c'], men inte ['a', 'c'] eller ['a', 'b', 'd', 'c']. På samma sätt kommer mönstret ['a', '--', 'c'] matcha listorna ['a', 'b', 'c'], ['a', 'b', 'd', 'c'] och ['a', 'c'], men inte ['a', 'b', 'c', 'd'].

Vi vill ha en huvudfunktion match som tar en lista och ett mönster som indata, och som returnerar True om listan matchar mönstret och False om listan inte matchar mönstret.

Hur går vi då tillväga för att komma fram till en lämplig algoritm? Ett sätt är att börja med att skriva pseudokod och försöka täcka alla tänkbara fall. På så sätt kan man få en idé om hur ens program kommer fungera och samtidigt är det lätt att få en överskådlig blick vilket gör det lätt att identifiera eventuella missade fall. Låt oss göra detta för vår mönstermatchare.

`Pseudokod`	Kommentar
`1. Om mönstret är tomt, returnera True om listan är tom, annars False`	Vi måste börja med ett basfall. Ett tomt mönster matchar en tom lista, men inte en lista som innehåller något.
`2. Om '--' är först i mönstret`
`2.1. Om resten av mönstret matchar listan, returnera True`	Mönstret '--' kan matcha noll tecken, så om resten av mönstret matchar resten av listan har vi en matchning.
`2.2. Om listan är tom, returnera False`	Om resten av mönstret inte matchar i punkten ovan, men listan är tom, så innebär det att mönstret innehåller fler tecken än listan och vi har ingen matchning.
`2.3. Sök igenom resten av listan med samma mönster`	Annars låter vi '--' äta upp första elementet i listan och söker vidare.
`3. Om listan är tom, returnera False`	Eftersom '--' är det enda som kan matcha noll tecken, samt att vi i första fallet kontrollerade om både mönstret och listan är tomma samtidigt, så räcker det att här kontrollera om listan är om. I så fall innehåller mönstret för många element och vi har ingen matchning.
`4. Om '&' är först i mönstret, jämför resten av listan med resten av mönstret`	Vi låter '&' äta upp första elementet och försöker matcha resten.
`5. Om första elementet i listan matchar första elementet i mönstret, fortsätt matcha resten av listan mot resten av mönstret`	Vi har nu passerat specialtecknen och kan matcha vanliga element mot varandra. Dessa tar vi ett i taget och anropar oss själva rekursivt.
`6. I alla andra fall, returnera False`	Hit kommer vi om inget annat matchar, t.ex. om första elementen inte matchar eller om mönstret har tagit slut innan listan.

Omskrivet till Python ser mönstermatcharen ut så här (se match.py, som ska finnas i ditt Git-arkiv):

def match(seq, pattern): """ Returns whether given sequence matches the given pattern """ if not pattern: return not seq elif pattern[0] == '--': if match(seq, pattern[1:]): return True elif not seq: return False else: return match(seq[1:], pattern) elif not seq: return False elif pattern[0] == '&': return match(seq[1:], pattern[1:]) elif seq[0] == pattern[0]: return match(seq[1:], pattern[1:]) else: return False

Uppgift 7A - Utökad mönstermatchning

I denna uppgift ska du göra två saker: utöka mönstermatchningsrutinen som vi visade ovan och skapa en ny funktion som använder mönstermatcharen för att göra en sökning i en enkel databas.

Förtydligande 2020-12-14: Som vi har skrivit ovan ska man göra två saker. Att utöka mönstermatchningsrutinen är alltså en egen deluppgift som är oberoende av själva databassökningen. Detta innebär bland annat att mönstermatcharen fortfarande ska vara helt generell och kunna användas på godtyckliga strukturer. Nu ska den dock kunna användas för att hitta element som i sig är nästlade listor.

Databasen innehåller uppgifter om ett antal böcker och är lagrad som listor i listor. Strukturen framgår av följande exempel (se books.py, som också ska finnas i ditt Git-arkiv):

db = [[['författare', ['john', 'zelle']], ['titel', ['python', 'programming', 'an', 'introduction', 'to', 'computer', 'science']], ['år', 2010]], [['författare', ['armen', 'asratian']], ['titel', ['diskret', 'matematik']], ['år', 2012]], [['författare', ['j', 'glenn', 'brookshear']], ['titel', ['computer', 'science', 'an', 'overview']], ['år', 2011]], [['författare', ['john', 'zelle']], ['titel', ['data', 'structures', 'and', 'algorithms', 'using', 'python', 'and', 'c++']], ['år', 2009]], [['författare', ['anders', 'haraldsson']], ['titel', ['programmering', 'i', 'lisp']], ['år', 1993]]]

Er uppgift är att skriva en funktion search som tar ett mönster och en enkel databas enligt ovanstående format. Funktionen ska söka igenom databasen (listan) och matcha mönstret mot varje huvudelement i listan. Returvärdet ska vara en lista med de element som matchar, alternativt en tom lista om inga böcker matchar.

För att kunna använda vår tidigare mönstermatchare måste ni dock först utöka denna så att den klarar av att matcha listor i listor. Som den fungerar nu kan den enbart matcha raka listor.

Förtydligande 2020-12-14: Att "först utöka" mönstermatcharen är alltså en egen deluppgift som resulterar i en generell mönstermatchare, som vi även förtydligade längre upp. Precis som den ursprungliga mönstermatcharen får den inte bara klara av bokdatabaser och får inte hårdkoda specifika nycklar. Sedan, när mönstermatcharen är utökad, används denna generella funktion för att skriva den enkla funktionen search, som är tänkt att användas för sökning i bokdatabaser på ovanstående mer specifika format.

Tips 2020-12-14: Exemplet ovan använder har element där listor bara förekommer i två nivåer, men som vanligt kan man inte lösa de här problemen genom att t.ex. testa om ett element är en lista och i så fall lägga in ytterligare mönstermatchningskod för den nästlade listan. Det skulle ju leda till onödigt duplicerad kod, vilket vi aldrig vill ha. Istället blir den rimligaste lösningen att rekursera ner i den nästlade listan... vilket också gör att man automatiskt kan hantera ett godtyckligt antal nivåer.

Tips 2020-12-14: Tänk på att hantera fallen där mönstret anger att man ska matcha en nästlad lista medan elementet inte alls är en lista, eller vice versa. I det fallet ska "&" kunna matcha vilket element som helst, även en nästlad lista. Motsvarande gäller "--".

Målet är att sökfunktionen, som anropar matchningsfunktionen, ska fungera så här:

>>> search([['författare', ['&', 'zelle']], ['titel', ['--', 'python', '--']], ['år', '&']], db) [[['författare', ['john', 'zelle']], ['titel', ['python', 'programming', 'an', 'introduction', 'to', 'computer', 'science']], ['år', 2010]], [['författare', ['john', 'zelle']], ['titel', ['data', 'structures', 'and', 'algorithms', 'using', 'python', 'and', 'c++']], ['år', 2009]]] >>> search(['--', ['år', 2042], '--'], db) [] >>> search(['--', ['titel', ['&', '&']], '--'], db) [[['författare', ['armen', 'asratian']], ['titel', ['diskret', 'matematik']], ['år', 2012]]]

Testning I den här labben ingår det inga givna tester. Istället är det er uppgift att skriva egna tester för de funktioner som ni har implementerat. Vilken metod ni väljer för att göra testerna (Pythons inbyggda unittest eller assert) är upp till er.

Ni behöver inte demonstrera eller lämna in detta förrän ni är färdiga med hela labb 7, men ni får gärna be handledaren att ta en titt på det ni har gjort för att få informell återkoppling.

7.3 Rekursiva strukturer och högre ordningens funktioner

När vi behandlar rekursivt definierade strukturer är ett bra angreppssättet ofta "gör X i basfallet, gör Y annars". När vi i övning 416 i laboration 4 skrev ut nycklarna i ett (av en händelse sorterat) träd handlade det om två olika uppsättningar instruktioner:

Basfall
1. Om vi kommit till ett tomt träd: gör ingenting
2. Om vi kommit till ett löv: skriv ut nyckeln
Om vi kommit till en inre nod: gå vidare med vänster träd, skriv sedan ut inre nodens nyckel, gå sedan vidare med höger träd

Nu vill vi generalisera hanteringen av binära träd och definiera en funktion traversera som tar ett binärt sökträd (definierat som i laboration 4) och inte mindre än tre funktioner:

empty_tree_fn som inte tar några argument
leaf_fn som tar ett argument - nyckeln för lövet
inner_node_fn som tar tre argument - nyckeln för den inre noden, samt värdet av vänster respektive höger subträd.

Funktionen traverse ska systematiskt gå igenom hela trädet och agera på följande sätt:

Om den stöter på ett tomt träd körs empty_tree_fn.
Om den stöter på ett löv körs leaf_fn på det lövet.
Om den stöter på en inre nod körs inner_node_fn på den aktuella nyckeln och resultatet av att traversera vänster respektive höger subträd.

Det är kanske lättare att se hur detta fungerar genom ett exempel. Kom ihåg att trädet [6, 7, 8] är en representation av ett träd som rent strukturellt ser ut så här:

7 / \ 6 8

Vi definierar tre funktioner som vi tänker oss att köra på olika delar av av trädet. Varje tomt träd får resultatet 0, varje nyckel kommer att kvadreras och för varje inre nod summerar vi nyckelvärdet med värdet från vänster gren. Den högra grenen ignoreras.

def empty_tree_fn(): return 0 def leaf_fn(key): return key**2 def inner_node_fn(key, left_value, right_value): return key + left_value

Om vi nu traverserar vårt exempelträd med dessa funktioner får vi följande resultat:

>>> traverse([6, 7, 8], inner_node_fn, leaf_fn, empty_tree_fn) 43

I den inre noden beräknar vi alltså värdet av de två subträden. Vänster subträd visar sig vara ett löv (6), och lövfunktionen ger tillbaka värdet 36 (nyckel 6, 6^2=36). På samma sätt visar sig höger subträd vara ett löv, med följden att vi skickar tillbaka värdet 8^2 = 64. Beräkningen från den inre noden kan nu genomföras. Summan nyckel + vänster_värde blir 7 + 36 = 43.

Uppgift 7B - Att traversera träd

Här följer 4 deluppgifter. Om du kör fast på en: Prova att gå vidare med en annan, så kanske det lossnar!

Deluppgift (i) Definiera funktionen traverse enligt ovan. Du kan anta att användaren alltid ger dig giltiga binära sökträd, som följer beskrivningen i laboration 3. Använd dig av de primitiva hjälpfunktionerna som t.ex. left_subtree istället för att leta i listorna med hjälp av index. Saknas någon sådan funktion, definiera den.

Du får givetvis skapa extra hjälpfunktioner till traverse om det underlättar implementationen.

Deluppgift (ii) Använd nu traverse för att definiera en sökfunktion contains_key som söker efter en nyckel i ett binärt träd (inte nödvändigtvis ett väl sorterat sådant).

Uppgiften är alltså i praktiken att definiera de tre funktionerna som ska skickas in till traverse - inre-nod, löv och tomt-träd - för att åstadkomma en sökning. Ledtråd: Om man definierar en funktion inuti en annan, kan den inre funktionen komma åt den yttre funktionens parametrar. Därmed behövs inga globala variabler eller liknande trick.

>>> contains_key(6, [6, 7, 8]) True >>> contains_key(2, [6, 7, [[2, 3, 4], 0, []]]) True >>> contains_key(2, [[], 1, 5]) False

Deluppgift (iii) Använd traverse för att definiera en funktion tree_size som beräknar storleken av ett binärt sökträd, d.v.s. det totala antalet löv och inre noder.

>>> tree_size([2, 7, []]) 2 >>> tree_size([]) 0 >>> tree_size([[1, 2, []], 4, [[], 5, 6]]) 5

Deluppgift (iv) Använd traverse för att definiera en funktion tree_depth som beräknar djupet av ett binärt sökträd, d.v.s. antalet noder i den längsta vägen från roten till ett löv.

>>> tree_depth(9) 1 >>> tree_depth([1, 5, [10, 7, 14]]) 3

Redovisa labben så snart som möjligt!

Demonstrera samtliga uppgifter för handledaren för att få återkoppling på era lösningar. Åtgärda eventuella problem som upptäcks vid demonstrationen.
Se till att all er programkod och alla körexempel enligt ovan finns i ert lokala Git-repo (git add, git commit), och att det även finns tillgängligt i Gitlab (git push).
Meddela labbassistenten att er inlämning är redo för kontroll, genom att skapa ett ärende i vår centrala ärendehanterare (som också råkar finnas i Gitlab).

Sidansvarig: Peter Dalenius
Senast uppdaterad: 2023-11-13