Notes

In questa nota andiamo a trattare argomenti come tabelle di verità. Mappe di Karnaugh. E piccolissima introduzione ai circuiti integrati. Boole Un signor Boole ha creato le basi dell’algebra booleana su cui si basano le porte logiche dei computer moderni. Tabelle di verità Le tabelle di verità sono sufficienti per descrivere il funzionamento di una porta logica. Questa cosa è possibile grazie alla limitatezza delle funzioni all’interno dell’insieme $\{0,1\}$ dominio di partenza e fine dell’algebra booleana. ...

6.1 Codifiche Si utilizzano codifiche, che sono delle convenzioni, qualcosa che un gruppo di umani ha deciso fosse utile darci un significato. 6.1.1 Codifica posizionale Dove $d_i$ è il valore in posizione $i$ e $b$ è la base $$ \sum_{i=0}^k d_ib $$6.1.2 Ottale, esadecimale e binario Queste sono le codifiche principali per i computer in quanto sono comodi da visualizzare. Inoltre Ottale e esadecimale in particolare sono riassunti dei binari, cioè sono dei sottoinsiemi che possiedono ancora tutte le caratteristiche e quindi sono comodi ...

Iterazione Questo metodo semplicemente consiste di calcolare tutte le operazioni e scriverlo con una notazione asintotica. slide Sostituzione (induzione) slide Analisi della relazione di ricorrenza di fibonacci Si può dimostrare utilizzando l’induzione che una relazione di questo tipo $$ T(n) = \begin{cases} O(1) \\ T(n-1) + T(n-2) + 1 \end{cases} $$Si trova che è $O(2^n), \Omega(2^{n/2})$ Analisi finale. ...

Molto importante questo documento per avere chiara la differenza fra la logica intuizionista e la Logica Proposizionale classica. Questa logica intuizionista non si preoccupa del noumeno platonico, ma solo di una prova reale. Introduzione: wikipedia 9 11 Scopi di intuizionista (3) Semantica dell’evidenza → costruzione della prova Semantica della conoscenza diretta = conoscenza diretta Semantica della calcolabilità = programma, algoritmo della soluzione 9.1 Invenzione o scoperta La semantica intuizionista vede la matematica come una creazione (e questa cosa interessa molto all’informatico perché è una prova., mentre la semantica classica vede la matematica come una scoperta ...

Programmare e dimostrare sono sostanzialmente la stessa attività ~Coen Ma non secondo l’industria… 4.1.1 Definizione e necessità Branca della linguistica, studia creazione di proposizione e il loro collegamento per la creazione di un periodo In seguito la semantica dà un metodo a queste proposizioni in modo che abbiano un senso. Utile o necessario per la definizione del linguaggio artificiale 4.1.2 Alfabeto, stringa, linguaggio e grammatica Alfabeto: Insieme non vuoto di simboli (che spesso sono diversi fra di loro) Stringa seguenza finita (vuoto è possibile) di simboli $\epsilon = \varnothing$ Linguaggio: insieme di stringhe (di qualunque tipo, finito o infinito). Grammatica formalismo (un insieme di regole che lo rende finito) che definisce un linguaggio ...

3.1 Introduzione 3.1.1 Cosa sono Le strutture di dati si interessano solamente di come memorizzare i dati, non necessariamente va a memorizzare un tipo di dato concreto. Quindi + sul come - sul cosa. 3.1.2 Prototipo e implementazione Avevamo introdotto la differenza fra algoritmo e programma all’inizio del corso, andiamo ora a definire la differenza fra prototipo e implementazione: Prototipo: va a fare una descrizione dei metodi che deve avere una determinata struttura di dati. Lo puoi intendere come una specie di interfaccia. ...

Questa è una necessità per stabilire il significato di una sintassi definiti. 5.1 Verità e Realtà La verità ha solamente senso quando lo si relaziona con un mondo sensibile, ossia il mondo che si può percepire con i nostri sensi. 5.1.1 Verità parametrica e assoluta Se un esperimento è ripetibile all’interno del mondo sensibili allora questa è considerata come una verità parametrica, ossia dipende da uno stato del mondo sensibile. ...

Alberi BST e AVL 4.1 Alberi binari di ricerca (BST) Queste sono delle varianti rispetto all’albero, descritto in modo molto sommario sopra (binario perché ogni nodo ha al massimo due figli, mentre l’albero può averne quanti se ne vuole). 4.1.1 Introduzione La caratteristica principale dell’albero di ricerca è una condizione sulle chiavi (che hanno i figli). Infatti questo albero binario di ricerca si può vedere come una implementazione della struttura astratta del dizionario. (che ricordiamo, è un struttura in cui a ogni nodo sono presenti due valori, una chiave (tute differenti) e un dato, e sono definite tre operazioni principali, possiamo vederla come interfaccia). ...

Logica del primo ordine Questa è la logica più utilizzata dai matematici Limitatezza della logica proposizionale La logica proposizionale classica non è in grado di ragionare sull’infinito Fino ad ora abbiamo utilizzato una metalogica per giustificare il per ogni e l’esiste nelle dimostrazioni fin’ora. Dobbiamo quindi dare una definizione più formale dei quantificatori. Obiettivo della logica del primo ordine Si può quindi identificare come l’obiettivo della logica di primo ordine l’introduzione dei quantificatori dell’universale e dell’esiste ...

Introduzione Definizione normalità Test del sottogruppo normale Dimostrazione Il gruppo quoziente L’importanza del gruppo normale è che quando esso vale, possiamo avere il gurppo fattore Dimostrazione !