logo-polimi
Loading...
Risorse bibliografiche
Risorsa bibliografica obbligatoria
Risorsa bibliografica facoltativa
Scheda Riassuntiva
Anno Accademico 2019/2020
Scuola Scuola di Ingegneria Industriale e dell'Informazione
Insegnamento 086067 - ALGORITMI E PRINCIPI DELL'INFORMATICA
  • 086065 - ALGORITMI E PRINCIPI DELL'INFORMATICA (MOD 2 - INFORMATICA 3)
Docente Pradella Matteo
Cfu 5.00 Tipo insegnamento Modulo Di Corso Strutturato

Corso di Studi Codice Piano di Studio preventivamente approvato Da (compreso) A (escluso) Insegnamento
Ing Ind - Inf (1 liv.)(ord. 270) - MI (358) INGEGNERIA INFORMATICAI1AEP086067 - ALGORITMI E PRINCIPI DELL'INFORMATICA
I1TEP086067 - ALGORITMI E PRINCIPI DELL'INFORMATICA
I3IEP086067 - ALGORITMI E PRINCIPI DELL'INFORMATICA
IC3EP086067 - ALGORITMI E PRINCIPI DELL'INFORMATICA
II3EP086067 - ALGORITMI E PRINCIPI DELL'INFORMATICA
IT1EP086067 - ALGORITMI E PRINCIPI DELL'INFORMATICA

Obiettivi dell'insegnamento

L'informatica ha subito un’evoluzione estremamente rapida dai suoi albori ai giorni d’oggi. Ciò ha prodotto notevoli benefici alla qualità della vita ma ha anche creato problemi legati all’affidabilità dei sistemi informatici. Spesso infatti le tecniche di progetto adottate si sono rivelate inadeguate alla complessità dei problemi affrontati.

Da più parti si è individuata, tra le cause principali della scarsa affidabilità dei sistemi informatici, la mancanza di solidi principi teorici su cui basare le tecniche di progettazione.

Il corso di algoritmi e principi dell'informatica ha lo scopo di colmare questa lacuna affrontando in maniera sistematica i problemi fondamentali dell’informatica e mettendo in evidenza come un approccio rigoroso e basato sui fondamenti teorici della disciplina abbia grande rilevanza nelle applicazioni pratiche. Soprattutto, il corso intende sviluppare l'attitudine ad affrontare problemi nuovi e non ben precisati e ricavarne un modello preciso e adatto all'individuazione della miglior (o adeguata) soluzione.

Il corso di algoritmi e principi dell'informatica è articolato in due moduli: Informatica Teorica e Informatica 3. I due moduli sono fruibili separatamente (in casi particolari) e in modo integrato (adozione prevista nei casi normali). Gli argomenti trattati nel modulo Informatica 3 sono specificati nell'apposita sezione.


Risultati di apprendimento attesi

Descrittori di Dublino

Risultati di apprendimento attesi

Conoscenza e comprensione

A seguito del superamento dell’esame lo studente conosce:

  • I principi di base della progettazione e dell’analisi degli algoritmi e delle strutture dati.

Capacità di applicare conoscenza e comprensione

Attraverso le esercitazioni su problemi specifici, e a seguito del superamento dell’esame, lo studente acquisisce:

·         Capacità di applicare, adattare e valutare in situazioni pratiche algoritmi e strutture dati.

Autonomia di giudizio

A seguito del superamento dell’esame lo studente è in grado di:

·         Scegliere ed eventualmente ideare opportune strutture dati e algoritmi per il problema che sta considerando.

Capacità di apprendimento

·         Gli studenti saranno in grado di valutare in maniera critica algoritmi e strutture dati.

·         Gli studenti saranno in grado di creare  nuovi algoritmi e nuove strutture dati.

 

 


Argomenti trattati
  1. Teoria della complessità

1.1 Nozioni e notazioni fondamentali per l’analisi di complessità
1.2 I modelli di calcolo e le relazioni tra le loro complessità computazionali

1.2.1 Definizione di complessità spaziale e temporale per macchina di Turing deterministica

1.2.2 Astrazioni e notazione asintotica

1.2.3 Complessità di automi a stati finiti, a pila e macchina di Turing a nastro singolo

1.2.4 Accelerazione lineare

1.3 La macchina RAM

1.3.1 Valutazione di complessità con criterio del costo costante
1.3.2  Il criterio logaritmico

1.4 Il teorema di correlazione polinomiale
1.5 Gerarchie di complessità

1.6 Cenni all'NP-completezza

  1. Strutture dati e algoritmi fondamentali

2.1 Algoritmi di ricerca e ordinamento
2.2 Strutture dati elementari (pile, code, liste): rappresentazione, algoritmi di ricerca e gestione

2.3 Tabelle hash: funzioni di hash, indirizzamento aperto.

2.4 Alberi e loro gestione

2.4.1 Alberi binari

2.4.2 Algoritmi di visita e gestione

2.4.3 Alberi rosso-neri

2.5 Grafi, loro rappresentazione e gestione (cenni)


Prerequisiti

Il programma del corso assume la conoscenza degli argomenti trattati nel corso di Fondamenti di Informatica.


Modalità di valutazione

Di norma l’esame è esclusivamente scritto; il docente si riserva però la possibilità di approfondire e perfezionare la propria valutazione mediante opportune domande integrative in forma orale; durante lo scritto è permessa la consultazione dei testi. Gli appelli d'esame sono svolti secondo le regole della scuola. In caso di valutazione gravemente insufficiente, lo studente non potrà partecipare all'appello successivo.

Modalità di verifica

Descrizione

Risultato di apprendimento perseguito (descrittore di Dublino)

Esame scritto

  • Risoluzione di problemi numerici: calcolo della complessità
  • Risoluzione di esercizi di tipo progettuale: progettazione di algoritmi e strutture dati
  • Domande di carattere teorico a risposta aperta sugli argomenti del corso

1, 2

1, 2, 3, 5

1, 2, 5

 

 

 


Bibliografia
Risorsa bibliografica obbligatoriaMandrioli Dino; Spoletini Paola, Informatica teorica, Editore: CittaStudi, Anno edizione: 2011
Note:

Il testo copre l'intero programma del primo modulo e la parte Teoria della complessita' del secondo.

Risorsa bibliografica obbligatoriaCormen T., Leiserson C., Rivest R., Stein C, Introduzione agli algoritmi e strutture dati, Editore: McGraw-Hill, Anno edizione: 2010, ISBN: 9788838665158
Note:

Il testo copre la parte Strutture dati e algoritmi fondamentali del secondo modulo. E' disponibile una versione breve (versione "Create") ritagliata dalla casa editrice appositamente per le esigenze di questo corso sulla base delle indicazioni fornite dai docenti.

Risorsa bibliografica obbligatoriaBertossi A., Montresor A,, Algoritmi e strutture di dati, Editore: De Agostini, Anno edizione: 2010
Note:

Il testo puo' surrogare il testo principale di Cormen et al.

Risorsa bibliografica obbligatoriaMandrioli D., Lavazza L., Morzenti, A., San Pietro P.L., Spoletini P., Esercizi di Informatica Teorica, III Edizione., Editore: Esculapio, Anno edizione: 200
Note:

Il testo e' un eserciziario che tratta gli argomenti del programma del primo modulo e della parte Teoria della complessita' del secondo


Forme didattiche
Tipo Forma Didattica Ore di attività svolte in aula
(hh:mm)
Ore di studio autonome
(hh:mm)
Lezione
30:00
45:00
Esercitazione
20:00
30:00
Laboratorio Informatico
0:00
0:00
Laboratorio Sperimentale
0:00
0:00
Laboratorio Di Progetto
0:00
0:00
Totale 50:00 75:00

Informazioni in lingua inglese a supporto dell'internazionalizzazione
Insegnamento erogato in lingua Italiano
Disponibilità di libri di testo/bibliografia in lingua inglese
Possibilità di sostenere l'esame in lingua inglese
schedaincarico v. 1.6.1 / 1.6.1
Area Servizi ICT
02/04/2020