====== Informatica 3 ====== __**[[teaching:info3:blog|News]]**__ __**[[teaching:info3en|English version]]**__ Il corso di Informatica 3 viene svolto, quest'anno, in tre sezioni (Proff. Agosta, Campi e Matera). I contenuti del corso sono gli stessi per le tre sezioni, e la parte scritta dell'esame viene svolta su testi comuni. Il corso si divide in due parti, all'incirca di dimensioni uguali: la prima tratta i linguaggi di programmazione e i relativi criteri di progetto, mentre la seconda affronta il tema della progettazione di algoritmi e strutture dati efficienti. Il corso è composto da 30 ore di lezione e 20 di esercitazione. Il responsabile delle esercitazioni per questa sezione è l'ing. [[http://crypto.dei.polimi.it/doku.php?id=team:gerardo_pelosi|Gerardo Pelosi]]. ===== Programma del corso: Linguaggi di Programmazione ===== - I linguaggi di programmazione: concetti generali e classificazioni fondamentali; cenni storici - Sintassi e semantica - La struttura dei dati - La struttura di controllo - Modularizzazione - Linguaggi orientati agli oggetti - Cenni ai linguaggi Interpretati ===== Programma del corso: Algoritmi e Strutture Dati ===== - Introduzione alla complessità del calcolo - La notazione “Theta-grande” - La realizzazione di tipi astratti di dati in Java - Strutture dati e algoritmi fondamentali - Algoritmi di ricerca e ordinamento - Alberi e loro gestione - Realizzazione mediante puntatori - Alberi binari - Algoritmi di visita e gestione - B-trees - Grafi, loro rappresentazione e gestione - Pile, code e tabelle hash - Applicazioni di elaborazioni numeriche e simboliche: a scelta e a rotazione alcuni tra: string matching, compressione dei dati, crittografia (cenni), moltiplicazione tra matrici, trasformata veloce di Fourier (FFT) ===== Materiale didattico ===== Per il corso di Informatica 3, si adottano formalmente due libri di testo: * Per la prima parte: Ghezzi C., Jazayeri M.: //Programming language concepts//, 4th edition, John Wiley & Sons, 2002. * Per la seconda parte: C.A.Shaffer: //A practical Introduction to data structures and algorithm analysis//. Lo Shaffer è sostituibile con T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: //Introduzione agli algoritmi e strutture dati 2/ed//. Questo secondo testo rimane utile anche al di fuori del corso come testo di riferimento, ed ha un'impostazione più vicina a quella seguita da me a lezione. L'altra faccia della medaglia è che si tratta di un testo più complesso, con un'impostazione matematica più formale. Potete inoltre fare riferimento alle [[http://webspace.elet.polimi.it/lanzi/?page_id=14|slide]] usate nelle altre sezioni del corso, e, per la seconda parte, al [[http://people.cs.vt.edu/~shaffer/Book/|materiale]] associato al libro di testo. Per finire, il classico libro di David Harel, "Algorithmics: The Spirit of Computing", fornisce una introduzione meno traumatica ai concetti visti nel corso. === Python === A lezione, gli algoritmi vengono presentati, invece che in pseudo-codice o in C++/Java, in [[http://www.python.org|Python]] (al contrario, Java viene usato nelle esercitazioni). Potete (e dovete, dato che la programmazione Python è argomento d'esame) scaricare l'interprete Python dal link qui sopra, sia per Linux che per Windows. Se usate Linux, quasi certamente l'interprete è già presente nel sistema. Per avvicinarsi a Python, è possibile avvalersi di vari testi liberamente disponibili in formato pdf o html, fra cui: * Mark Pilgrim, [[http://diveintopython.org/|Dive Into Python]]: molto completo; * Allen B. Downey, Jeffrey Elkner and Chris Meyers [[http://www.openbookproject.net/thinkcs/python/english/|How to Think Like a Computer Scientist - Learning with Python]]: testo introduttivo alla programmazione, va bene se avete bisogno di un ripasso dei concetti fondamentali di programmazione; * Bruce Eckel, [[http://www.mindview.net/Books/TIPython|Thinking in Python]]: questo //non// è un testo introduttivo; si tratta della version Python del classico //Thinking in Java//. ===== Il programma in dettaglio ===== Qui trovate il programma dettagliato del corso. Le note allegate alle lezioni future fanno riferimento al programma 2008/2009, e potranno subire (lievi) cambiamenti. ^ Argomento ^ Data ^ Tipo ^ | [[teaching:info3:introduzione|Sintassi e semantica]] | 30/9 | L | | [[teaching:info3:semantica_operazionale_delle_chiamate_a_funzione|Chiamate a funzione]] | 5/10 | L | | [[teaching:info3:python|Python]] | 7/10 | L | | [[http://home.dei.polimi.it/agosta/files/Esercizi_SIMPLESEM.pdf|Semantica operazionale]] | 12/10 | E | | [[teaching:info3:concorrenza_threading|Concorrenza e Threading]] | 14/10 | L | | [[teaching:info3:mutex_threading|Threading & Mutua Esclusione]] | 19/10 | L | | {{teaching:thread_task.pdf|Parallelismo e Threading}} | 21/10 | E | | [[teaching:info3:liste_pile_e_code|Liste, pile e code]] | 26/10 | L | | [[teaching:info3:iteratori_generatori_e_coroutine|Iteratori, generatori e coroutine]] | 28/10 | L | | [[teaching:info3:complessita_computazionale|Complessità]] | 2/11 | L | | [[teaching:info3:Notazioni_O,_Ω_e_Θ|Notazioni O, Ω e Θ]] | 4/11 | L | | [[teaching:info3:complessita_induzione_e_ricorrenze|Induzione e ricorrenze]] | 9/11 | L | | [[teaching:info3:algoritmi_di_ordinamento|Algoritmi di ordinamento]] | 11/11 | L | | {{teaching:internal_sorting_array.pdf|Algoritmi di ordinamento}} | 23/11 | E | | [[teaching:info3:alberi_binari|Alberi Binari]], parte 1 | 25/11 | L | | [[teaching:info3:alberi_binari|Alberi Binari]], [[teaching:info3:binary_search_tree_e_heap|Binary Search Tree]] | 30/11 | L | | {{teaching:bt-bst-heap-java.pdf|Alberi}} | 2/12 | E | | {{teaching:cuda.pdf|Seminario: algoritmi paralleli su schede video NVIDIA}} | 9/12 | S | | [[teaching:info3:binary_search_tree_e_heap|Heap]] | 14/12 | L | | [[teaching:info3:b-tree|B-Tree]] | 16/12 | L | | [[teaching:info3:esercitazione_b-tree|B-Tree]] | 21/12 | E | | [[teaching:info3:grafi|Grafi]] | 11/01 | L | | {{teaching:graphs2009.pdf|Grafi}} | 13/01 | E | | [[teaching:info3:hash|Hash & Huffman code]] | 18/01 | L | | Seminario: {{teaching:introductiontocryptography.pdf|Crittografia}} | 18/01 | S | | {{teaching:hashing.pdf|Hash}} e {{teaching:riepilogocomplessita.pdf|complessità}} | 20/01 | E | | {{teaching:esercizi.zip|Esercitazione riassuntiva 1}} | 25/01 | E | | {{teaching:esercizi.zip|Esercitazione riassuntiva 2}} | 27/01 | E | Inoltre sono disponibile i [[oldcalender|calendari degli anni precedenti]]. ===== Temi d'esame ===== * {{teaching:i3_20090903final.pdf|Quarto appello 2009 (settembre)}} * {{teaching:i3-2009-luglio.pdf|Terzo appello 2009 (luglio)}} * {{teaching:i3-2009second.pdf|Secondo appello 2009}} * {{teaching:i3-2009first.pdf|Primo appello 2009}} * {{teaching:i3-20080902.pdf|02/09/2008}} * {{teaching:i3-20080709.pdf|09/07/2008}} * {{teaching:i3-20080214.pdf|14/02/2008}}