Sillabo dell'insegnamento

• A - Fondamenti
V - Varie
+ DS-SRF - Sets, Relations, and Functions
Teoria degli insiemi. Terminologia fondamentale. Definizione di insiemi in modo esplicito e in modo implicito. Inclusioni. Operatori insiemistici. Diagrammi di Eulero-Venn. Prodotto Cartesiano. Relazioni fra insiemi. Relazione di equivalenza e relazione d'ordine. Classi di equivalenza. Congruenze aritmetiche. Insiemi con operazioni (Monoidi, Semigruppi e Gruppi). Proprietà delle classi resto modulo m. Funzioni. Concetto di funzione iniettiva e suriettiva. Cardinalità di un insieme. Composizione di funzioni, funzione inversa
L - Logica
+ DS-PT - Proof Techniques
Elementi di Logica Matematica. Proposizioni e predicati. Operatori Logici. Metodi di dimostrazione (diretta, per assurdo, per contrapposizione). Equivalenze logiche. Operatori esistenziali e universali
• B - Algoritmi
* A - Algoritmi fondamentali
+ DS-BC - Basics of Counting
Divisori e Multipli. L'algoritmo della divisione. Massimo Comun divisore. L'algoritmo di Euclide per il Massimo Comun Divisore. Numeri primi. Fattorizzazione in numeri primi. Il teorema della fattorizzazione unica.
• C - Programmazione
* PSA - Problem Solving e Algoritmi
+ DS-BC - Basics of Counting
Calcolo combinatorio: Il principio delle scelte multiple. Applicazioni: numero di funzioni fra insiemi finiti. Numero di funzioni iniettive fra insiemi finiti. Numero di funzioni biiettive tra insiemi finiti. Esercizi. Disposizioni semplici e con ripetizione. Permutazioni. Combinazioni semplici e con ripetizione. Significato insiemistico.
* R - Ricorsione
+ DS-BC - Basics of Counting
Aritmetica degli interi. Assioma del minimo. Principio di induzione (prima e seconda forma). Applicazioni: Cardinalità dell'insieme delle parti. Formula di Gauss. Progressione geometrica. Successioni. Successione di Fibonacci. Il problema delle Torri di Hanoi.
* PSA - Problem Solving e Algoritmi
+ DS-BC - Basics of Counting
Proprietà del coefficiente binomiale. Partizioni e Il principio dei cassetti. Il principio di inclusione-esclusione. Uso positivo e uso negativo del principio di inclusione-esclusione. Applicazioni. Il principio del contare per righe e per colonne.