logo-polimi
Loading...
Risorse bibliografiche
Risorsa bibliografica obbligatoria
Risorsa bibliografica facoltativa
Scheda Riassuntiva
Anno Accademico 2018/2019
Scuola Scuola di Ingegneria Industriale e dell'Informazione
Insegnamento 086067 - ALGORITMI E PRINCIPI DELL'INFORMATICA
Docente Bersani Marcello Maria , Comai Sara
Cfu 10.00 Tipo insegnamento Corso Integrato

Corso di Studi Codice Piano di Studio preventivamente approvato Da (compreso) A (escluso) Insegnamento
Ing Ind - Inf (1 liv.)(ord. 270) - CO (360) INGEGNERIA INFORMATICAI1AAZZZZ070325 - INFORMATICA TEORICA
086067 - ALGORITMI E PRINCIPI DELL'INFORMATICA
Ing Ind - Inf (Mag.)(ord. 270) - MI (486) ENGINEERING PHYSICS - INGEGNERIA FISICA*AZZZZ086067 - 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 è 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).


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 e i modelli fondamentali del calcolo automatico.
  • 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à critica relativa all’uso, alla creazione e all’adattamento di modelli per il calcolo.
  • 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 adattare i modelli di calcolo al problema che sta considerando.
  • 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 modelli computazionali, algoritmi e strutture dati.
  • Gli studenti saranno in grado di creare nuovi modelli computazionali, nuovi algoritmi e nuove strutture dati.

 


Argomenti trattati

Primo modulo: Informatica teorica

1. I modelli dell'informatica 

  • Automi (a stati finiti, a pila, Macchine di Turing)
  • Modelli nondeterministici (automi)
  • Grammatiche
  • Introduzione alla logica matematica 
  • Uso della logica matematica per modellare sistemi e descriverne proprietà.

2. Teoria della computazione

  • Potenza dei modelli di calcolo
  • Tesi di Church
  • Problemi indecidibili
  • Tecniche di dimostrazione di indecidibilità

 

Secondo modulo:Informatica 3

3. Teoria della complessità

3.1 Nozioni e notazioni fondamentali per l’analisi di complessità
3.2. I modelli di calcolo e le relazioni tra le loro complessità computazionali

3.3 La macchina RAM

3.4 Il teorema di correlazione polinomiale

3.5 Gerarchie di complessità

3.6 Cenni all'NP-completezza

4. Strutture dati e algoritmi fondamentali

4.1 Introduzione ai concetti di strutture dati e algoritmi

4.2 Strutture dati lineari (pile, code, liste)

4.3 Alberi e loro gestione

4.3.1 Alberi binari

4.3.2 Algoritmi di visita e gestione

4.3.3 BST, Heap

4.3.4 Alberi n-ari e alberi generici

4.4 Algoritmi di orginamento

4.5 Algortimi di ricerca

4.5.1 Hashing

4.5.2 Alberi 2-3, B, B+

4.6 Grafi, loro rappresentazione e gestione 

4.7 Tecniche di progettazione di algoritmi (cenni)


Prerequisiti

Il programma del corso assume la conoscenza degli argomenti trattati nel corso di Fondamenti di Informatica.
Inoltre, costituiscono prerequisito anche parte dei contenuti del corso di Logica e Algebra.


Modalità di valutazione

L'esame è scritto e con possibilità di consultazione dei testi. Gli appelli d'esame sono svolti secondo le regole della scuola. Per il corso integrato gli appelli saranno basati su una prova unica.  In caso di consegna di un compito fortemente 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 modelli astratti, 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

Forme didattiche
Tipo Forma Didattica Ore di attività svolte in aula
(hh:mm)
Ore di studio autonome
(hh:mm)
Lezione
60:00
90:00
Esercitazione
40:00
60:00
Laboratorio Informatico
0:00
0:00
Laboratorio Sperimentale
0:00
0:00
Laboratorio Di Progetto
0:00
0:00
Totale 100:00 150: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
Disponibilità di supporto didattico in lingua inglese
schedaincarico v. 1.6.1 / 1.6.1
Area Servizi ICT
22/02/2020