Discrete Structures
Weekly outline
-
Predstavitev predmeta in ekipe.
Logika. Izjave. Izjavni vezniki. Izjavni izrazi.
Resničnostna tabela izjavnega izraza. Konstrukcijsko drevo izjavnega izraza. Tavtologija, protislovje.
Enakovrednost izjavnih izrazov. Zakoni izjavnega računa.
-
-
DNO in KNO.
Polni nabori izjavnih veznikov. Še trije izjavni vezniki.
-
Sklepanje v izjavnem računu. Pravila sklepanja.
Pomožni sklepi: pogojni sklep, sklep s protislovjem, analiza primerov.
Notranja zgradba izjav. Kvantifikatorji. Interpretacija in formalizacija. Izjavne formule.
Enakovrednosti v predikatnem računu.
-
Predavanja so že za nami.
-
-
Preimenovanje spremenljivk. Enakovrednosti z omejitvami. Preneksna normalna oblika.
Teorija množic. Russellov paradoks. Enakost in vsebovanost pri množicah. Operacije z množicami. Lastnosti operacij z množicami.
-
-
Lastnosti operacij z množicami, nadaljevanje.
Reševanje sistemov enačb z množicami z eno neznanko.
Družine množic. Pokritje in razbitje.
Urejeni pari in kartezični produkt.
-
Relacije. Lastnosti relacij.
Operacije z relacijami.Potence relacij. Graf relacije.
Ovojnice relacij.
Ekvivalenčna relacija, uvod. -
-
Ekvivalenčna relacija, nadaljevanje.
Relacije urejenosti.
Preslikave. -
Moč množic.
Deljivost celih števil. Največji skupni delitelj in najmanjši skupni večkratnik. Računanje.Linearne diofantske enačbe z dvema neznankama.
Praštevila.
-
-
Praštevila. Eulerjeva funkcija fi (ne nujno).
Permutacije. Zapis s tabelico in disjunktnimi cikli.
Potenciranje permutacij in ciklična struktura. -
-
Izrek o parnosti, igra 15.
Potenčna enačba. -
Predavanj in vaj v tem tednu ni.
V tem razdelku učilnice so/bodo prikazane dodatne (neobvezne) vsebine poglavja Teorija števil: Eulerjeva funkcija, kongruence, Eulerjev in Mali Fermatov izrek, RSA kriptosistem
-
Ta teden so na sporedu samo vaje.
-
-
Grafi. Stopnje točk. Izomorfizem.
Sprehodi. Povezanost. Eulerjevi grafi. Dvodelni grafi.
-
Drevesa in gozdovi.
Hamiltonovi grafi.
Barvanje grafov.
-