Notes

Introduzione Note filosofiche (non impo) Bisogna in primo momento cercare di definire cosa è la computazione e cosa è un computer. Aristotele faceva la distinzione fra proprietà essenziali e accidentali. Quelle essenziali sono proprie dell’oggetto. Una sedia può essere fatta di legno o di metallo, ma questa proprietà è accidentale, ovvero, essa rimane una sedia indipendentemente dal materiale di cui è fatta. Solitamente in matematica si prova ad astrarre (vedi Astrazione sul controllo per nota generale sull’astrazione). Però in questo campo si sono trovati molte concezioni equivalenti. Fino ad arrivare a concepire la tesi di Church-Turing. Il prof. nota che questo è strano, perché in altre discipline si converge in unico modello, mentre qui molte cose sono indifferenti. Questo è importante per capire come la concezione di Computer Science si è evoluta (Denning 2010). ...

Introduction to the Rice Theorem Ci sono molti teoremi che non possono essere decisi, vedere Halting Theorem and Reducibility. Qui andiamo a chiederci quale sia l’insieme dei problemi decidibili. Proprietà dei linguaggi TM🟩 $$ L_{\mathcal{M}} = \left\{ x \in \Sigma^{*}: \mathcal{M} \text{ accetta } x \right\} $$$$ L_{\mathcal{M}} = L_{\mathcal{M}'} \implies P(\mathcal{M}) = P(\mathcal{M}') $$ Definiamo questa non triviale se esiste una macchina per cui è 0, e una per cui è 1 (ossia non è costante). Practically this definition is useful when we need to have a difference between the language and the Turing machine that decides that language. ...

Questa parte è strettamente collegata conl a parte di Astrazione sul controllo. Si parla di passare le funzioni come dati. e quindi possono essere passati come se fossero dei parametri. un linguaggio di programmazione è di ordine superiore qualora ammetta funzioni sia come parametro che come risultato di altre funzioni. La parte molto simile alla precedente è il fatto di valutare la funzione nell’ambiente iniziale, quindi bisogna utilizzare un sistema simile a quello del passaggio per nome. ...

Introduction to the probabilistic Turing Machine Most of real phenomena are better comprehended by a probabilistic view. This pushes to build a formal model that takes probability into account Def: Probabilistic TM $$ \mathbb{P}(b) = 2^{-k} $$ Where $k$ is the length of the branch. Then the probability of accepting the word is given by this: $$ \mathbb{P}(\mathcal{M} \text{ accepts } \omega) = \sum_{b \text{ is an accepting branch}} \mathbb{P}(b) $$ Note that this is very similar to the Algorithmic probability defined in Kolmogorov complexity. ...

Lempel-Ziv-Welch Algorithm Introduzione sul funzionamento Primo scan con un dizionario indexato dei singoli caratteri Poi viene cercato di raggruppare caratteri a coppie. Se una coppia è già presente nel dizionario, allora aggiungo al dizionario una cosa più lunga e metto un code diverso Esempio di sopra. La cosa carina è che il dizionario si può ricostruire in fase di decoding. ...

Significato di astrazione L’astrazione è una cosa fondamentale nell’informatica, l’abbiamo visto anche nella prima lezione in assoluto per architettura, il sistema a strati di Architettura e livelli 1, 2 reti e simili. Il principali metodi sono astrazioni sul controllo e sui dati sui dati stiamo cominciando a parlarne in Teoria dei Tipi. Le astrazioni sono utili a nascondere dettagli per qualche fenomeno o simile (ricorda l’esempio della mappa, che non è il territorio è una astrazione su essa, che contiene ancora informazioni utili). Vogliamo quindi concentrarci su quanto ci interessa ...

Per l’analisi lessicale vogliamo cercare di ricordare le parole legali all’interno di questo linguaggio e questo è fatto con i linguaggi regolari. Introduzione a analizzatori lessicali Token 🟩 Struttura del token è fatto da due parti Identificatore della classe del token Identificatore del valore del token Pattern e lessema ci sono direi boh Pattern e Lessema 🟩 I pattern sono una descrizione generale della forma dei valori di una classe di token. ...

Descrivo ora alcune domande utili per ripasso: Quali sono schematicmente quali sono le operazioni migliori per un parser top-down? Cosa è un prefisso viabile? Quali sono i conflitti possibli, e come risolverli… Non sai nemmeno definire inmodo formale cosa sia un item Bottom up Intro shift-reduce e LR 🟩 Slide In breve: Shift = simbolo terminale messo nella stack Riduzione utilizzando una produzione LR = dettura da Sinistra, creazione della stringa da destra (derivazione rightmost) Algoritmo classico 🟨+ Quello che credo che intendevo per questo algoritmo classico è quello non deterministico, nel senso che prova a fare backtracking, finché non ha finito tutte le possibilità, oppure trova la derivazione giusta. ...

Si può osservare che per il parser costruito in Bottom-up Parser LR(0)), non riesce a riconoscere di linguaggi semplici come $L = \{a, ab\}$. Esempio di quanto detto Parser SLR(1) Questi parser qui utilizzano l’idea del look ahead ampiamente utilizzata in Top-down Parser, per escludere molte produzioni. La s sta per simple, perché utilizza una idea semplice :D, credo ahah boh. Riduzione con follow 🟩 noi vogliamo ridurre solamente se ho follow corretto il terminale finale della stringa. ...

Introduction Capire in che modo una rete convoluzionale ci può dare insight migliori su come funzionano questi networks. Visualizzazione dei hidden layers Slide visualization Potremmo fissare una immagine anche a caso, e modificare la x in modo che sia più simile a quanto vuole computare il neurone. In questo modo genero una immagine che generi una activation forte nel neuron trainato, e si potrebbe dire che sia il genere di immagine che viene generata da essa. ...