Mängdlära och mängdoperationer

Skriv lösningarna till uppgifterna i en och samma fil och testa koden själv innan du använder rättningsskriptet. Att kunna testa sin kod är en viktig del av att programmera!

Att lära dig från uppgifterna

• Förstå det matematiska konceptet mängd.
• Förstå hur mängder kan bearbetas i Python.

Man kan få max 105 poäng och för att få godkänt krävs 60 poäng (90 för väl godkänt). Försök dock att lösa alla uppgifter då inte alla fel upptäcks av rättningsskriptet. Om ni har lite marginal kan ni kanske bli godkända även om assistenten som rättar hittar något sådant fel.

Uppgift 9.1

Ni ska nu översätta ett antal mängduttryck till Python. Använd mängderna nedan för att testa er lösning. Mängderna representerar kvinnor ($M_{F}$), programmerare ($M_{P}$), levande personer ($M_{L}$) och personer födda i USA ($M_{A}$). Detta var sant så sent som

• $M_{F} = {Churchland, Conway, Easley, Wilson}$
• $M_{P} = {Conway, Easley, Knuth, Wilson}$
• $M_{L} = {Chomsky, Churchland, Knuth, Wilson}$
• $M_{A} = {Chomsky, Conway, Easley, Knuth, Fodor}$

Börja med att översätta dessa mängder till Python-notation. Skicka sedan motsvarande mängder som argument till funktionerna ni implementerar. (För den som är nyfiken: Noam Chomsky, Patricia Churchland, Lynn Conway, Annie Easley, Jerry Fodor, Donald Knuth, Sophie Wilson)

9.1.1 (5p)

Skriv en funktion set_expr1(A, B, C) som tar tre mängder som argument. Funktionen skall returnera värdet av mängduttrycket $(A \cap B) \cap C$.

Exempel

>>> set_expr1(M_L, M_A, M_P)
{'Knuth'}

9.1.2 (5p)

Skriv en funktion set_expr2(A, B, C) som tar tre mängder som argument. Funktionen skall returnera värdet av mängduttrycket $A \cup (B \setminus C)$.

Exempel

>>> set_expr2(M_L, M_F, M_P)
{'Knuth', 'Chomsky', 'Wilson', 'Churchland'}

9.1.3 (5p)

Skriv en funktion set_expr3(A, B, C, D) som tar fyra mängder som argument. Funktionen skall returnera värdet av mängduttrycket $B \setminus (C \setminus (A \setminus D))$.

Exempel

>>> set_expr3(M_P, M_L, M_F, M_A)
{'Chomsky', 'Knuth', 'Wilson'}

9.1.4 (5p)

Skriv en funktion set_expr4(A, B, C, D) som tar fyra mängder som argument. Funktionen skall returnera värdet av mängduttrycket $((B^\complement) \cap (A \cap D)) \cup C^\complement$.

Exempel

>>> set_expr4(M_F, M_P, M_L, M_A)
{'Conway', 'Fodor', 'Easley'}

Uppgift 9.2 (10p)

Skriv en funktion subsets som inte tar några argument och returnerar en mängd med strängar. Strängarna i mängden ska motsvara namnen på de delmängder nedan som är delmängder till $S = \{3, 7, \{5, 6\}\}$. Om mängderna $A$, $B$ och $C$ är delmängder till $S$ ska den returnerade mängden alltså vara {'A', 'B', 'C'}. Det är tillåtet att hårdkoda svaret*.

* Hårdkoda betyder att ni manuellt skriver in de rätta svaren i en mängd i retursatsen. Ni behöver inte skriva någon mer kod än så och det är alltså inte ett krav att ni ska programmera en funktion som själv kan besvara frågorna genom att testa påståendena på något vis. Att ni redovisar på det här sättet är främst ett “hack” för att ni själva ska kunna kontrollera om era svar är korrekta med hjälp av rättningsskriptet ;) (Med det sagt så är det inte förbjudet att översätta mängderna till Python och testa vilka som är delmängder, men försäkra er om att ni själva förstår svaret också.)

$$ \begin{align*} A&=\{3, 6\} \\ B&=\{\{5, 6\}, 7\} \\ C&=\{7, 3\} \\ D&=\{7, 5\} \\ E&=\emptyset \\ F&=\{\{5, 6\}\} \\ G&=\{\{3, 7\}, 5, 6\} \\ H&=\{5, 6\} \\ I&=\{3, 7, \{5, 6\}\} \\ \end{align*} $$

Uppgift 9.3 (10p)

Skriv en funktion statements som inte tar några argument och returnerar en mängd av strängar. Strängarna i mängden ska motsvara namnen på de påståenden nedan som är sanna givet $S = \{x, y, \{x, z\}\}$. Om påstående $A$, $B$ och $C$ är sanna ska den returnerade mängden alltså vara {'A', 'B', 'C'}.

Även här ska ni själva besvara frågan manuellt, funktionen är bara ett trick för att kunna använda rättningsskriptet.

$$ \begin{align*} A&: x \subseteq S \\ B&: \{x\} \subseteq S \\ C&: \{x, y, \{x, z\}\} \subset S \\ D&: \{x, y\} \in S \\ E&: \{x, z\} \in S \\ F&: z \in S \\ \end{align*} $$

Uppgift 9.4

Venn-diagram

Ett vanligt sätt att illustrera mängder är med så kallade Venn-diagram. Nu ska vi försöka härleda några mängduttryck utifrån sådana Venn-diagram.

Ett mängduttryck består av några mängder, här kallar vi dem $A$, $B$ och $C$ som vi kombinerar ihop med hjälp av mängdoperationerna union $\cup$, snitt $\cap$, differens $\setminus$ och komplement $S^\complement$.

OBS! Det är inte säkert att ett uttryck kommer använda sig av alla argument. Det kan också finnas mer än ett uttryck som motsvarar varje Venn-diagram, ni behöver bara hitta något av dem.

Det är inte fel att lösa uppgiften på papper först och sedan översätta till Python.

9.4.1 (5p)

Skapa en funktion venn_1(A, B, C, U) som tar tre mängder och ett universum som argument. Funktionen skall returnera mängden som indikeras av Venn-diagrammet till höger.

Exempel

OBS! Kom ihåg att mängder är oordnade och att ni inte nödvändigtvis får elementen i samma ordning.

>>> A = {'a', 'ab', 'ac', 'abc'}
>>> B = {'b', 'ab', 'bc', 'abc'}
>>> C = {'c', 'bc', 'ac', 'abc'}
>>> U = A | B | C
>>> venn_1(A, B, C, U)
{'abc', 'bc'}

9.4.2 (5p)

Skapa en funktion venn_2(A, B, C, U) som tar tre mängder och ett universum som argument. Funktionen skall returnera mängden som indikeras av Venn-diagrammet till höger.

Exempel

>>> A = {'a', 'ab', 'ac', 'abc'}
>>> B = {'b', 'ab', 'bc', 'abc'}
>>> C = {'c', 'bc', 'ac', 'abc'}
>>> U = A | B | C
>>> venn_2(A, B, C, U)
{'bc', 'ac', 'abc', 'c', 'a'}

9.4.3 (5p)

Skapa en funktion venn_3(A, B, C, U) som tar tre mängder och ett universum som argument. Funktionen skall returnera mängden som indikeras av Venn-diagrammet till höger.

Exempel

>>> A = {'a', 'ab', 'ac', 'abc'}
>>> B = {'b', 'ab', 'bc', 'abc'}
>>> C = {'c', 'bc', 'ac', 'abc'}
>>> U = A | B | C
>>> venn_3(A, B, C, U)
{'ac', 'c', 'ab', 'abc'}

9.4.4 (5p)

Skapa en funktion venn_4(A, B, C, U) som tar tre mängder och ett universum som argument. Funktionen skall, utan att använda union, returnera mängden som indikeras av Venn-diagrammet till höger.

Exempel

>>> A = {'a', 'ab', 'ac', 'abc'}
>>> B = {'b', 'ab', 'bc', 'abc'}
>>> C = {'c', 'bc', 'ac', 'abc'}
>>> U = A | B | C
>>> venn_4(A, B, C, U)
{'ac', 'b', 'bc', 'abc', 'ab', 'c'}

Uppgift 9.5

Givet mängderna $A = \{2, 4, 6, 8, 10\}$, $B = \{b, c\}$ och $C = \{1, 2, 3, a, b, c\}$. I uppgifterna nedan ska du skriva funktioner som kan användas för att beräkna följande kardinaliteter:

• $|C \setminus B|$
• $|(C \cup A) \setminus B|$
• $|(B \cap C)^\complement|$

Notera dock att funktionerna ska kunna hantera alla variationer av formlerna ovan, t.ex. $|B \setminus A|$ eller $|(A \cup B) \setminus C|$

9.5.1 (5p)

Skriv en funktion diff_card(X, Y) som tar två mängder och beräknar $|X \setminus Y|$.

Exempel

>>> diff_card(C, B)
4

9.5.2 (5p)

Skriv en funktion union_diff_card(X, Y, Z) som tar två mängder och beräknar $|(X \cup Y) \setminus Z|$.

Exempel

>>> union_diff_card(C, A, B)
8

9.5.3 (5p)

Skriv en funktion intersec_comp_card(X, Y, U) som tar tre mängder, varav det sista är ett universum, och beräknar $|(X \cap Y)^\complement|$.

Exempel

>>> intersec_comp_card(B, C, (A | B | C))
8

Uppgift 9.6

Vi ska nu återskapa de grundläggande mängdoperationerna med hjälp av listor och funktioner. Detta blir vår första riktiga övning i abstraktion. Dvs. där vi gömmer undan den underliggande komplexiteten och det faktum att vi arbetar med listor genom att bygga en uppsättning funktioner som ger oss ny funktionalitet. Även om vi i det här fallet bara återskapar funktionalitet som redan finns. Jämför det med att spela skalor när man lär sig ett instrument.

Begränsningar:

• Det är inte tillåtet att använda datatypen set i lösningen till någon av deluppgifterna. Däremot kan man använda set för att testa sina lösningar.
• Det är inte tillåtet att modifiera argumenten till någon av funktionerna.
• Frivilligt: Se till de funktioner som returnerar en lista returnerar en lista utan dubbletter.

Disclaimer: Sättet vi kommer implementera mängder här speglar inte hur datatypen set fungerar under ytan. Vi skapar “bara” något som beter sig på samma sätt. Detta är i sig en viktig insikt, två olika stycken kod kan utvändigt bete sig på samma sätt och användas på samma sätt men under ytan fungera på fundamentalt olika sätt. Detta är just vad abstraktion handlar om inom programmering, att kunna bortse från de där interna detaljerna som skiljer sig.

9.6.1 (5p)

Skriv en funktion list_set_subset(lst1, lst2) som returnerar True om alla unika element i lst1 också existerar i lst2.

Tips: En for-loop och operatorn in är lämpliga byggstenar att använda.

Exempel

>>> list_set_subset([], [])
True
>>> list_set_subset([], [1, 2])
True
>>> list_set_subset([1], [1, 2])
True
>>> list_set_subset([1, 2], [1, 2])
True
>>> list_set_subset([3], [1, 2])
False

9.6.2 (5p)

Skriv en funktion list_set_eq(lst1, lst2) som returnerar True om lst1 och lst2 är lika med varandra ur mängdperspektiv. Dvs. om lst1 och lst2 är lika när vi bortser från ordning och eventuella dubbletter.

Tips: Använd list_set_subset och notera att den inte kräver att lst1 är en strikt delmängd av lst2…

Exempel

>>> list_set_eq([], [])
True
>>> list_set_eq([1, 2], [2, 1])
True
>>> list_set_eq([1, 2], [1, 2, 1])
True
>>> list_set_eq([1, 2], [1, 1, 1])
False

9.6.3 (5p)

Skriv en funktion list_set_card(lst) som returnerar storleken av lst ur mängdperspektiv. Dvs. antalet unika element i lst.

Tips: En for-loop och en räknare som bara räknas upp när ett visst värde dyker upp för första gången.

Exempel

>>> list_set_card([])
0
>>> list_set_card([1,2])
2
>>> list_set_card([1,2,1])
2
>>> list_set_card([1,1,1])
1

9.6.4 (5p)

Skriv en funktion list_set_intersec(lst1, lst2) som returnerar en ny lista med de element som finns i både lst1 och lst2.

Tips: En for-loop och operatorn in är lämpliga byggstenar även här.

Exempel

OBS! Ordningen på elementen i resultaten spelar ingen roll.

>>> list_set_intersec([], [])
[]
>>> list_set_intersec([1, 2], [1, 1, 1])
[1]
>>> list_set_intersec([1, 2], [1, 2, 1])
[1, 2]
>>> list_set_intersec([1, 2], [2, 3])
[2]
>>> list_set_intersec([1, 2], [3, 4])
[]

9.6.5 (5p)

Skriv en funktion list_set_union(lst1, lst2) som returnerar en ny lista med alla element som finns i minst en av lst1 och lst2.

Tips1: En for-loop, eller två, och operatorn in är lämpliga byggstenar även här.

Tips2: Om man bara vill ha en for-loop kan man börja med att kopiera den ena listan. Vi kan kopiera en lista genom att ta ut ett slice av hela listan. Dvs. my_list_copy = my_list[:].

Exempel

OBS! Ordningen på elementen i resultaten spelar ingen roll.

>>> list_set_union([], [])
[]
>>> list_set_union([], [1, 1, 1])
[1]
>>> list_set_union([1, 2], [1, 1, 1])
[1, 2]
>>> list_set_union([1, 2], [1, 2, 1])
[1, 2]
>>> list_set_union([1, 2], [2, 3])
[1, 2, 3]

9.6.6 (5p)

Skriv en funktion list_set_diff(lst1, lst2) som returnerar en ny lista med de element som finns i lst1 men inte i lst2.

Tips: En for-loop och operatorn in är lämpliga byggstenar igen.

Exempel

OBS! Ordningen på elementen i resultaten spelar ingen roll.

>>> list_set_diff([], [])
[]
>>> list_set_diff([1, 2], [1, 1, 1])
[2]
>>> list_set_diff([1, 2], [1, 2, 1])
[]
>>> list_set_diff([1, 2], [2, 3])
[1]
>>> list_set_diff([1, 2], [3, 4])
[1, 2]