185SM - INFORMATICA 2020
Section outline
-
Libri
Per la parte di algoritmi e strutture dati si consiglia:
- Cormen, Leiserson, Rivest, Stein
Introduction to Algorithms (Introduzione agli algoritmi)
MIT Press (McGraw Hill per l’edizione italiana) - Per questo corso la lingua o l’edizione (da 1 a 3) del libro non sono importanti.
Per la parte di programmazione Python esistono molti libri e tutorial di buona qualità. Controllate sempre che siano per Python 3 e non la versione precedente (Python 2). Un libro disponibile gratuitamente online è "Think Python":
- Allen B. Downey
Think Python, 2nd Edition
https://greenteapress.com/wp/think-python-2e/
Software
L'interprete Pyhton è disponibile alla pagina https://www.python.org.
Se utilizzate una distribuzione linux potreste avere un interprete Python già installato, controllate nel vostro gestore di pacchetti. Nel caso usiate macOS, una versione di Python è già installata, ma potrebbe non essere la versione 3.
È possibile utilizzare un intero ambiente di programmazione totalmente online senza installare nulla utilizzando https://repl.it/, scegliendo "+ new repl" (in alto nella pagina) e "Python" come linguaggio. Repl è utilizzabile anche su tablet (una tastiera aiuta notevolmente la scrittura di codice).
Configurare un editor di testo per scrivere codice Python
In aggiunta all'interprete Python, per scrivere codice è utile avere un editor di testo adatto alla scrittura di codice. Esempi di questi editor sono Visual Studio Code, Sublime Text, Emacs, Vim, etc. Ecco alcuni di questi editor e le istruzioni su come configurarli per lavorare con Python:
- Visual Studio Code. Viene richiesta l'installazione del plugin per Python all'apertura di un file con estensione .py
- Sublime Text. Editor di testo per programmatori, con trial senza limiti temporali. Plugin per Python disponibile qui.
- PyCharm. Ambiente completo specifico per Python.
- Emacs. Uno degli editor storici. Per lo sviluppo di Python si consiglia di installare il pacchetto elpy.
- Vim e NeoVim. L'altro editor storico. Per configurarlo per Python si veda questo post.
- Notepad++. Editor specifico per piattaforma Windows. Per configurarlo per Python si vedano queste istruzioni.
- Atom. Editor moderno sviluppato da GitHub. Package per Python disponibile qui.
Lezioni in streaming
Esami
L'esame consiste di un progetto e di un esame orale. Per accedere all'orale è necessario il superamento del progetto. Le date per la sessione estiva sono le seguenti:
Appello di giugno
- pubblicazione del progetto: 14 giugno 2021
- consegna del progetto: 18 giugno 2021 (ore 23:59)
- orali: 25 giugno 2021
Appello di luglio
- pubblicazione del progetto: 12 luglio 2021
- consegna del progetto: 16 luglio 2021 (ore 23:59)
- orali: 22-23 luglio 2021
Primo appello di settembre
- pubblicazione del progetto: 30 agosto 2021
- consegna del progetto: 3 settembre 2021 (ore 23:59)
- orali: 10 settembre 2021
Secondo appello di settembre
- pubblicazione del progetto: 13 settembre 2021
- consegna del progetto: 17 settembre 2021 (ore 23:59)
- orali: 24 settembre 2021
Primo appello di febbraio
- pubblicazione del progetto: 31 gennaio 2022
- consegna del progetto: 4 febbraio 2022 (ore 23:59)
- orali: 10 febbraio 2022
Secondo appello di febbraio
- pubblicazione del progetto: 15 febbraio 2022 (era 14 febbraio)
- consegna del progetto: 20 febbraio 2022 (ore 23:59) (era 18 febbraio)
- orali: 24 febbraio 2022
- Cormen, Leiserson, Rivest, Stein
-
Registrazione della lezione:
-
Registrazione della lezione:
-
Registrazione della lezione:
-
-
-
Registrazione delle lezione:
-
Registrazione della lezione:
-
-
Registrazione della lezione:
-
Registrazione delle lezioni:
-
Registrazioni della lezione:
-
-
-
Alberi binari di ricerca: definizione, inserimento, massimo, minimo, successore, predecessore.
-
Lavagna File PDF
-
Alberi binari di ricerca: cancellazione e rotazioni. Bilanciamento ed alberi AVL (cenni). Splay tree.
-
Slides File PDF
-
Lavagna File PDF
-
Complessità ammortizzata, metodo dell'aggregazione, banchiere e potenziale. Analisi ammortizzata degli alberi splay.
-
Slides File PDF
-
Lavagna File PDF
-
Tabelle di hash. Hash con chaining. Analisi del tempo medio di ricerca.
-
Slides File PDF
-
Lavagna File PDF
-
Grafi. Definizioni: orientato, non orientato, cammini, componenti connesse e fortemente connesse, isomorfismo, sottografi.
-
Slides File PDF
-
Lavagna File PDF
-
Alberi non radicati e loro proprietà. Visita in ampiezza e complessità.
-
Lavagna File PDF
-
Correttezza della visita in ampiezza
-
Lavagna File PDF
-
Visita in profondità, classificazione degli archi di un grafo orientato, algoritmo di Tarjan per componenti fortemente connesse.
-
Slides File PDF
-
Lavagna File PDF
-
-
Correttezza dell'algoritmo di Tarjan. Cammini minimi in grafi pesati: algoritmo di Bellman-Ford, identificazione di cicli di peso negativo, algortimi di Dijkstra.
-
Slides File PDF
-
Lavagna File PDF
-
-
Correttezza dell'algoritmo di Dijkstra. Programmazione dinamica. Rod splitting problem. Longest Common Subsequence.
-
Slides File PDF
-
Lavagna File PDF
-
-
Programmazione dinamica: calcolo della edit distance e algoritmo di Floyd Warshall per all-pairs shortest path
-
Slides File PDF
-
Lavagna File PDF
-
-
Registrazione delle lezione:
-
Registrazione della lezione:
-
Registrazione della lezione:
Per interesse personale: "Classic Nintendo Games are (Computationally) Hard"
-
Registrazione della lezione: