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
  • 086065 - ALGORITMI E PRINCIPI DELL'INFORMATICA (MOD 2 - INFORMATICA 3)
Docente Comai Sara
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) - CO (360) INGEGNERIA INFORMATICAI1AAZZZZ086067 - 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

Il modulo di algoritmi ha lo scopo di presentare i concetti fondamentali dell’algoritmica, ovvero quella branca dell’informatica che si occupa della definizione e la progettazione degli algoritmi, l’analisi della loro efficienza e complessità. Verranno introdotte strutture dati lineari (liste, pile, code) e non lineari (alberi, grafi) e numerosi algoritmi ad esse collegati, strutture dati avanzate (alberi B/B+, heap, tabelle hash, ecc.). Vengono forniti cenni sulle metodologie di progettazione di algoritmi (divide et impera, programmazione dinamica, metodo greedy, backtracking). 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.

 


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

Programma delle lezioni e delle esercitazioni

Teoria della complessità

  • Nozioni e notazioni fondamentali per l'analisi di complessità
  • I modelli di calcolo e le relazioni tra le loro complessità computazionali

Algoritmi e strutture dati

  • Introduzione agli algoritmi e strutture dati. Analisi di complessità di algoritmi e strutture dati. 
  • Strutture dati e algoritmi fondamentali: Liste, Code e Pile, Alberi binari e generici
  • Algoritmi di ordinamento
  • Algoritmi di ricerca. Hashing e Indicizzazione
  • Grafi, loro rappresentazione e gestione

Argomenti avanzati

  • Tecniche di progettazione di algoritmi
  • Problemi NP-completi

  

 


Prerequisiti

Il programma del corso presuppone una buona conoscenza di tutti gli argomenti trattati nel corso di Fondamenti di Informatica.

 


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 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 facoltativaAlan A. Bertossi, Alberto Montresor, Algoritmi e strutture di dati, Editore: CittàStudi, Anno edizione: 2014, ISBN: 978-8825173956
Risorsa bibliografica obbligatoriaCormen, Leiserson, Rivest, Stein, Introduction to Algorithms, Editore: Mit Pr, Anno edizione: 2009, ISBN: 978-0262033848

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
Disponibilità di supporto didattico in lingua inglese
schedaincarico v. 1.6.5 / 1.6.5
Area Servizi ICT
25/10/2020