729G46 Informationsteknologi och programmering¶

Tema 1, Föreläsning 1.3¶

Johan Falkenjack, johan.falkenjack@liu.se¶

Föreläsningsöversikt 1.3¶

  • Admin
  • Matematik och diskret matematik
    • Mängdlära
    • Venndiagram

Admin¶

Påminnelse, Python-material!¶

  • Kurslitteratur
    • Skansholm (2019) kap 1-2, 5.1-5.3.2, 5.3.5, 5.4, kap 6.1-6.2, 6.4, kap 8.1-8.2
  • Jodys videos
    • 1-5 & 7 är relevanta för Tema 1
    • Mindre än 25 minuter totalt, men väl värt att upprepa
    • https://web.microsoftstream.com/channel/5bf65e11-e261-45aa-ab27-0ec34e2b10e4
  • Alternativ kurslitteratur
    • Exempelvis Learning Python, 5ed av Mark Lutz
    • Python Tutor
    • https://pythontutor.com/python-debugger.html
    • Google

Påminnelse, Begreppsseminarium 1¶

  • Förberedelser
    • titta på videos
    • gör övning
    • lämna in Entry Ticket (deadline: kl. 12 dagen innan seminariet)
    • OBS! Entry Ticket inlämnad i tid krävs för deltagande på begreppsseminariet!
  • På seminariet
    • diskussion

Kort om GPT och generativ AI i kursen¶

  • Om ni använder det, använd det för att lära er programmera själva
  • Kod som ni redovisar och lämnar in ska ni skriva själva
  • Inlämningar som ni genererat via GPT och inte förstår in i minsta detalj betraktas som fusk
  • Lärare och assistenter är skyldiga att anmäla misstänkt fusk till LiUs disciplinnämnd

Vad gör viss matematik diskret?¶

Diskret matematik¶

  • Behandlar diskreta matematiska strukturer.
    • Diskreta i betydelsen åtskilda.
    • Inget att göra med att vara diskret i betydelsen lågmäld, förtegen, finkänslig, etc.
    • På engelska discrete, inte discreet.
  • T.ex.
    • Heltal
      • Det finns inget heltal mellan talet 1 och 2, de är åtskilda.
    • Studenter som läser kursen 729G46 i år.
      • Alla studenter är separata entiteter, de är åtskilda.
    • Husnummer
      • Vi har Storvägen 1, Storvägen 2 - Storvägen 1,5 finns normalt sett inte, adresserna är åtskilda.

Icke-diskret matematik?¶

  • Behandlar kontinuerliga matematiska strukturer
    • Kontinuerlig i betydelsen "steglös"
  • T.ex.
    • Reella tal
      • Det finns oändligt många reella tal mellan 1 och 2, vi kan steglöst flytta mellan dem.
    • Geometri
      • Vi kan alltid minska eller öka ett avstånd, oavsett hur litet eller stort det är, vi kan steglöst förändra storlekar.
    • Derivator och integraler
      • Per definition kontinuerliga till den grad att icke-kontinuiteter orsakar huvudverk.
  • Enklare att förstå vad som inte är diskret matematik?
  • Ni som får en klump i magen av derivator och integraler kan vara lugna.

Tillämpningar av diskret matematik¶

  • Modellering av diskreta domäner ("ämnesområden")
    • Formell beskrivning av t.ex. en Turingmaskin
    • Beskrivning av ett socialt nätverk
  • Logistik
  • Datalogi
    • Relationella databaser
    • Kryptering
    • Algoritmer, t.ex. kortaste vägen mellan två städer (karta = graf)
  • Annika pratade om Turingmaskinen.

Ämnen inom diskret matematik¶

  • Mängdlära
  • Matematisk logik
  • Abstrakt algebra
  • Tal- och informationsteori
  • Grafteori
  • Kombinatorik
  • Ordningsteori
  • Abstrakta algebror: t.ex. Boolesk algebra eller relationsalgebra

Får egna föreläsningar¶

  • Mängdlära
  • Matematisk logik
  • Abstrakt algebra
  • Tal- och informationsteori
  • Grafteori
  • Kombinatorik
  • Ordningsteori

Dyker upp här och där¶

  • Mängdlära
  • Matematisk logik
    • I AI-kursen
  • Abstrakt algebra
    • Boolesk algebra
    • I databaskursen
  • Tal- och informationsteori
    • Talsystem
    • Textrepresentation
  • Grafteori
  • Kombinatorik
    • I statistikkurser
  • Ordningsteori
    • Sortering

Idag¶

  • Mängdbegreppet
  • Venn-diagram
  • Kardinalitet
  • Delmängd
  • Mängdalgebra
    • Union
    • Snitt
    • Differens
  • Mängder och funktioner?

Mängdbegreppet¶

Mängd (eng. set)¶

  • "Samling av unika ting"
  • Exempel:
    • Kogvetettan
    • Böcker du har läst
    • Heltal
    • Rektanglar
    • Fester jag minns ( $\subset$ fester jag har varit på, men vi kommer till det)

Diskreta och kontinuerliga mängder¶

  • Diskreta (uppräkneliga):
    • Heltalen
    • Försöksdeltagare
    • Böcker
  • Kontinuerliga (ouppräkneliga):
    • Reella talen
    • Trianglar
    • Mätvärden i ett experiment (ibland)
  • Båda kan vara oändliga

Venn-diagram, att visualisera mängder¶

kogvet_ip_y.png

Var är matematiken?¶

Lite definitioner och notationer¶

$$ A = \{ a_1, a_2, \ldots, a_n \} $$

  • $A$ är en mängd som består av $n$ stycken unika element
  • Mängder noteras ofta med versal och ofta i exempel som $A$, $B$ och $C$ (snarare än $X$, $Y$ och $Z$)
    • (Undantag är vanliga)
  • Elementen noteras ofta med gemen, med samma bokstav som mängden, och med ett index som börjar på $1$
  • Begreppet mängd (eng. set)
  • Betecknas vanligast med en versal
  • Innehåller noll eller flera element
  • Element i en mängd skrivs mellan klammerparenteser
    • "måsvingar", {}
  • Ordningen på elementen spelar ingen roll
  • En mängd kan innehålla andra mängder

Venn-diagram och matematisk notation¶

kogvet_ip_y.png

$$ L_{KogVet} = \{Charlie, Kacper, Simon\} \quad L_{IP} = \{Charlie, Johan\} \quad L_{Y} = \{Kacper, Michael, Mio\} $$

Mängder är oordnade¶

$$ \{ Erik, Sam \} = \{ Sam, Erik \} $$

  • Elementens ordning har ingen betydelse ur mängdläre-perspektiv.
  • Gäller även mängder av tal

$$ \{ 1,2,3 \} = \{ 2,3,1 \} = \{ 3,2,1 \} = \{ 1,3,2 \} $$

Element i mängder är unika¶

$$ \{ Ludde, Annika, Ludde \} = \{ Ludde, Annika \} $$

  • Ett vanligt sätt att i programmering ta ut alla unika element i t.ex. en lista är att konvertera till språkets datatyp för mängder. Per definition måste då eventuella upprepningar försvinna.
    • Det kommer inte på duggan, men att förstå och kunna använda detta kan definitivt underlätta på duggan.

Måste mängder beskrivas genom uppräkning?¶

$$ \mathbb{Z} = \{ x | x \text{ är ett heltal}\} $$

  • Här används så kallad mängdbyggare för att beskriva mängden $\mathbb{Z}$, som är det generellt accepterade namnet för mängden av alla heltal. Utläses ofta som "$\mathbb{Z}$ är mängden av alla $x$ sådana att $x$ är ett heltal". Några andra vanliga talmängder:
    • $\mathbb{N}$ naturliga talen ( $\{ 0, 1, 2, 3, \ldots \}$ )
    • $\mathbb{Z}^+$ positiva heltalen ( $\{ 1, 2, 3, \ldots \}$ )
    • $\mathbb{Z}^-$ negativa heltalen ( $\{ \text{-}1, \text{-}2, \text{-}3, \ldots \}$ )
    • $\mathbb{Q}$ rationella talen
    • $\mathbb{R}$ reella talen
    • $\mathbb{C}$ komplexa talen
  • Kuriosa: När en mängd istället definieras genom uppräkning, t.ex. $\mathbb{Z} = \{\ldots, \text{-}2, \text{-}1, 0, 1, 2, 3, \ldots \}$ kallas det för roster-notation.

Mängdbyggare, exempel¶

  • $ A = \{ n | n \text{ har egenskapen...}\} $
  • $ M = \{ x | x \text{ är ett udda heltal}\} $
    • $M$ är mängden av alla $x$ sådana att $x$ är ett udda heltal
  • $ N = \{ x | x \in \mathbb{Z}, x \text{ är udda}\} $
    • (Notera att här är $M = N$ )

  • Rationella tal: $\mathbb{Q} = \{ x/y | x,y \in \mathbb{Z} \}$
    • $\mathbb{Q}$ är mängden av alla $x/y$ sådana att $x$ och $y$ tillhör mängden hela tal

Tillhörighet¶

  • Om $x$ är ett värde som finns i mängden $A$ så säger vi att $x$ tillhör $A$: $x \in A$

  • Givet

    • $L_{KogVet} = \{Charlie, Kacper, Simon\}$,
    • $L_{IP} = \{Charlie, Johan\}$ och
    • $L_{Y} = \{Kacper, Michael, Mio\}$

  • Så gäller att

    • $ Charlie \in L_{KogVet} $ ($Charlie$ tillhör mängden $L_{KogVet}$)
    • $ Kacper, Michael \notin L_{IP} $ ( $Kacper$ och $Michael$ tillhör inte mängden $L_{IP}$ )

Delmängd¶

  • Om $A$ och $B$ är mängder och alla element i $A$ också är i $B$ så är $A$ en delmängd till $B$: $A \subseteq B$
    • $\{ Charlie, Simon \} \subseteq L_{KogVet}$
  • Om samma situation som ovan gäller, men det finns något $x$ sådant att $x \in B$ men $x \notin A$ så är $A$ en strikt delmängd till $B$: $A \subset B$
    • $\{ Charlie, Simon \} \subset L_{KogVet}$ men
    • $\{ Charlie, Simon, Kacper \} \not\subset L_{KogVet}$
    • Jämför med relationen $\leq$

  • OBS! Delmängd och tillhörighet är inte samma sak.
    • Tillhörighet är en relation mellan vilka värden som helst och någon mängd
    • Delmängd är en relation mellan mängder

Ett par speciella mängder: $\mathbb{U}$¶

  • Universum, $\mathbb{U}$, eller universella mängden, mängden av alla element.
    • I verkligheten finns ingen sådan mängd (det går till och med att bevisa matematiskt att ingen sådan mängd kan existera, men det är överkurs).
    • Vi definierar $\mathbb{U}$ på ett sätt som är lämpligt för det problem vi behandlar.
    • När vi t.ex. diskuterar lärare i den här kursen och vilka program vi läst, så kan vi säga att
    • $\mathbb{U} = \{ Charlie, Johan, Kacper, Michael, Mio, Simon\}$

Ett par speciella mängder: $\emptyset$¶

  • Tomma mängden, $\emptyset$ eller $\{\}$, mängden utan några element.
  • $\emptyset$ har den speciella egenskapen att $\emptyset \subseteq S$ för alla mängder $S$
    • Dvs. $\emptyset$ är en delmängd till alla mängder

Kardinalitet¶

Räkna storleken av en mängd vapen, för den som har sett sketchen.

Kardinalitet¶

  • Storleken på en mängd $A$ kallas för $A$:s kardinalitet och skrivs $|A|$
  • Kardinaliteten är antalet element i en mängd
  • T.ex. $ L_Y = \{ Kacper, Michael, Mio \}$ så $|L_Y| = 3$

  • Överkurs: Vad är kardinaliteten hos en oändlig mängd som t.ex. $\mathbb{N}$?
    • Det beror på hur stor oändlighet vi pratar om men alla uppräkningsbara oändliga mängder, t.ex. $\mathbb{N}$, har kardinaliteten $\aleph_0$, större oändligheter har kardinaliteten $\aleph_1$, $\aleph_2$, osv.
    • (Det är rimligt att få åtminstone viss ångest av ovanstående helt sanna påstående, fråga Georg Cantor, mängdlärans fader.)

Mängder i Python¶

  • Klassen set
In [3]:
kogvetare = {"Charlie", "Kacper", "Simon", "Charlie"} # explicit beskrivning av en mängd
print(kogvetare)
ylist = ["Kacper", "Michael", "Mio"]
yset = set(ystudenter) # omvandla en lista med värden till en mängd

{'Kacper', 'Simon', 'Charlie'}

Mängder i mängder¶

xzibit_sets.png

Mängder i mängder¶

  • En mängd kan vara ett element i en annan mängd

$$ \begin{align} L_{IP} &= \{Charlie, Johan\} & & \\ L_{Y} &= \{Kacper, Michael, Mio\} & & \\ L_{TekS} &= \{Charlie, Johan, Kacper, Michael, Mio\} \qquad & |L_{TekS}| &= 5 \\ L_{TekP} &= \{L_{IP}, L_{Y}\} & & \\ L_{TekP} &= \{\{Charlie, Johan\}, \{Kacper, Michael, Mio\}\} & |L_{TekP}| &= 2 \end{align} $$

  • OBS! Mängden $L_{TekS} \neq L_{TekP}$
  • Nedanstående uttryck är sanna:

$$ \begin{align} Johan &\in L_{IP} \\ Johan &\notin L_{TekP} \\ L_{IP} &\in L_{TekP} \end{align} $$

Igen, notera skillnaden mellan tillhör och delmängd¶

$ \begin{align} L_{IP} &= \{Charlie, Johan\} & & \\ L_{Y} &= \{Kacper, Michael, Mio\} & & \\ L_{TekS} &= \{Charlie, Johan, Kacper, Michael, Mio\} & & \\ L_{TekP} &= \{L_{IP}, L_{Y}\} & & \\ L_{TekP} &= \{\{Charlie, Johan\}, \{Kacper, Michael, Mio\}\} & & \end{align} $

  • $Johan \in L_{IP}$
    • värdet $Johan$ tillhör $L_{IP}$ eftersom $Johan$ är ett element i $L_{IP}$
  • $L_{IP} \notin L_{TekS}$
    • Värdet $L_{IP}$ tillhör inte $L_{TekS}$ eftersom $L_{IP}$ inte är ett element i $L_{TekS}$
  • $L_{IP} \in L_{TekP}$
    • Värdet $L_{IP}$ tillhör $L_{TekP}$ eftersom $L_{IP}$ är ett element i $L_{TekP}$
  • $\{Johan\} \notin L_{IP}$
    • Värdet som är mängden som innehåller $Johan$ tillhör inte $L_{IP}$ eftersom $\{Johan\}$ inte är ett element i $L_{IP}$
  • $\{Johan\} \subset L_{IP}$
    • Däremot mängden som innehåller $Johan$ är en strikt delmängd av $L_{IP}$ eftersom alla element i $\{Johan\}$ finns i $L_{IP}$

Disjunkta mängder¶

  • Mängderna $A$ och $B$ är disjunkta (eng. disjoint) om $A$ och $B$ inte har några gemensamma element
  • Alternativt uttryckt
    • inget element i $A$ finns i $B$ och
    • inget element i $B$ finns i $A$
  • Exempelvis, givet
    • $L_{IP} = \{Charlie, Johan\}$ och
    • $L_{Y} = \{Kacper, Michael, Mio\}$
  • så är $L_{IP}$ och $L_{Y}$ disjunkta.

Mängdalgebra¶

Mängdalgebraiska operationer¶

  • Union
  • Snitt
  • Differens
  • Komplement
  • Symmetrisk differens

Mängdalgebra: Union, $\cup$¶

  • Unionen (eng. union) av $A$ och $B$
  • Informellt: Skapa en ny mängd där alla element från $A$ ingår, och alla element från $B$ ingår
  • I Python: |-operatorn

  • $A = \{bil,buss,motorcykel\}$
  • $B = \{cykel,motorcykel\}$
  • $ A \cup B = \{bil,buss,cykel,motorcykel\}$
  • I Python:
{"bil", "buss", "motorcykel"} | {"cykel", "motorcykel"}

Venn-diagram: Union¶

  • Vi kan färglägga vissa delar av ett Venn-diagram för att visa vilken del som representerar resultatet av en operation venn_ab_AuB.png $$ A \cup B $$

Mängdalgebra: Snitt, $\cap$¶

  • Snittet (eng. intersection) av mängden $A$ och $B$
  • Informellt: Skapa en ny mängd med alla element som finns både i $A$ och $B$
  • I Python: &

  • $A = \{bil,buss,motorcykel\}$
  • $B = \{cykel,motorcykel\}$
  • $ A \cap B = \{motorcykel\}$
  • I Python:
{"bil", "buss", "motorcykel"} & {"cykel", "motorcykel"}

Venn-diagram: Snitt¶

venn_ab_AnB.png

$$ A \cap B $$

Snitt och disjunkta mängder¶

  • Kom ihåg: $A$ och $B$ är disjunkta om de inte har några gemensamma element, dvs $$ A \cap B = \emptyset $$

Union och snitt, räkneregler¶

  • Kommutativitet
    • $A \cup B = B \cup A$
    • $A \cap B = B \cap A$
  • Associativitet
    • $(A \cup B) \cup C = A \cup (B \cup C)$
    • $(A \cap B) \cap C = A \cap (B \cap C)$
  • Distributivitet
    • $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
    • $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$

Mängdalgebra: Komplement, $^\complement$¶

  • Komplementet (eng. complement) till mängden $𝐴$
  • Informellt: Skapa en ny mängd med alla element som finns i $\mathbb{𝑈}$ men inte i $𝐴$ (ta bort element i $𝐴$ från $\mathbb{𝑈}$)
  • Ekvivalent med differensen mellan $\mathbb{𝑈}$ och $𝐴$

  • $\mathbb{𝑈} = \mathbb{Z}$ (alla heltal)
  • $ A = \{x | x \text{ är ett primtal}\} $
  • $ A^\complement = \{x | x \text{ är ett heltal men inte ett primtal}\} $

Venn-diagram: Komplement¶

venn_ab_Acomp.png $$ A^\complement $$

Venn-diagram: Komplement¶

venn_ab_Bcomp.png $$ B^\complement $$

Räkneregler, komplement¶

  • Involution eller dubbelkomplement

    • $(A^\complement)^\complement = A$

  • Komplementlagarna för universum och tomma mängden

    • $\emptyset^\complement = \mathbb{U} $
    • $\mathbb{U}^\complement = \emptyset $

  • De Morgans lagar

    • $(A \cup B)^\complement = A^\complement \cap B^\complement$
    • $(A \cap B)^\complement = A^\complement \cup B^\complement$

Mängdalgebra: Differens eller relativt komplement, $\setminus$¶

  • Differensen (eng. set difference) eller relativa komplementet (eng. relative complement) av mängden $A$ och mängden $B$
  • Informellt: Skapa en ny mängd där alla element finns i $A$, men inte i $B$ (ta bort element i $B$ från $A$)
  • I Python: -

  • $A = \{bil,buss,motorcykel\}$
  • $B = \{cykel,motorcykel\}$
  • $ A \setminus B = \{bil,buss\}$
  • I Python:
{"bil", "buss", "motorcykel"} - {"cykel", "motorcykel"}

Venn-diagram: Differens eller relativt komplement¶

venn_ab_A-B.png

$$ A \setminus B $$

Venn-diagram: Snitt¶

venn_ab_B-A.png

$$ B \setminus A $$

Mängdalgebra: Symmetrisk differens, $\Delta$¶

  • Symmetriska differensen (eng. symmetric difference), disjunkta unionen (eng. disjunctive union), eller mängdsumman (eng. set sum) av mängden $A$ och mängden $B$
  • Informellt: Skapa en ny mängd med alla element som finns i $A$ eller $B$ men inte i båda (ta bort snittet från unionen)
  • Ekvivalent med
    • $(A \cup B) \setminus (B \cap A)$
  • och
    • $(A \setminus B) \cup (B \setminus A)$

  • $A = \{bil,buss,motorcykel\}$
  • $B = \{cykel,motorcykel\}$
  • $ A \Delta B = \{bil,buss,cykel\}$
  • I Python:
{"bil", "buss", "motorcykel"}.symmetric_difference({"cykel", "motorcykel"})

Formell definition av en Turingmaskin¶

Following Hopcroft and Ullman (1979,p. 148), a (one-tape) Turing machine can be formally defined as a 7-tuple $M = \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle$ where

  • $\Gamma$ is a finite, non-empty set of tape alphabet symbols;
  • $b \in \Gamma$ is the blank symbol (the only symbol allowed to occur on the tape infinitely often at any step during the computation);
  • $\Sigma\subseteq\Gamma\setminus\{b\}$ is the set of input symbols, that is, the set of symbols allowed to appear in the initial tape contents;
  • $Q$ is a finite, non-empty set of states;
  • $q_0 \in Q$ is the initial state;
  • $F \subseteq Q$ is the set of final states or accepting states. The initial tape contents is said to be accepted by $M$ if it eventually halts in a state from $F$.
  • $\delta: (Q \setminus F) \times \Gamma \not\to Q \times \Gamma \times \{L,R\}$ is a partial function called the transition function, where L is left shift, R is right shift. If $\delta$ is not defined on the current state and the current tape symbol, then the machine halts; intuitively, the transition function specifies the next state transited from the current state, which symbol to overwrite the current symbol pointed by the head, and the next head movement.

Inlämningsuppgift 1¶

  • Övningar i mängdlära
  • 8 uppgifter som ger 1 eller 2 poäng med möjlighet till max 10 poäng
  • 7 av 10 poäng krävs för godkänt
  • Lämnas in som pdf i Sendlab (tema1_matte) senast 9e september kl 23.59
  • Eventuell komplettering genom att förklara varför de fel man gjorde var fel