ID:
192/2
Durata (ore):
48
CFU:
6
Url:
INGEGNERIA ELETTRONICA E INFORMATICA/PERCORSO COMUNE Anno: 1
Anno:
2023
Dati Generali
Periodo di attività
Ciclo Annuale (25/09/2023 - 17/05/2024)
Syllabus
Obiettivi Formativi
MODULO B
Fornire le conoscenze di base dell’informatica moderna con particolare riferimento ai principali algoritmi e alle relative strutture dati presenti in letteratura. Introdurre la loro implementazione tramite un linguaggio di programmazione di alto livello.
Trasmettere agli studenti la capacità di progettare algoritmi anche avanzati e di codificarli in programmi eseguibili da un calcolatore elettronico attraverso un linguaggio di programmazione di alto livello.
Favorire lo sviluppo dell’autonomia dello studente che sarà reso in grado di selezionare opportunamente, tra gli algoritmi e le strutture dati noti, quelli più opportuni per giungere alla risoluzione dei problemi considerati con particolare attenzione all’ottimizzazione delle risorse di calcolo e di memoria richieste.
Far acquisire la terminologia di base relativa alle tecniche di programmazione tramite linguaggi di alto livello. Lo studente sarà reso in grado di comunicare le motivazioni delle scelte tecniche adottate e di rappresentare adeguatamente i risultati ottenuti.
Sviluppare nello studente una capacità di aggiornamento autonomo rispetto all’avanzamento delle tecnologie con particolare riferimento ai linguaggi di programmazione di alto livello, alle strutture dati avanzate e agli algoritmi correlati.
Prerequisiti
Sono richieste conoscenze di base di analisi matematica, geometria, logica matematica e informatica.
Testi
-B. Kernighan, D. Ritchie, “Il linguaggio C -Principi di programmazione e manuale di riferimento.”, II edizione, Pearson, 2018.
- R. Sedgewick, “Algoritmi in C.”, IV edizione, Pearson, 2015
- S. Berretti, L. Carnevali, E. Vicario, “Fondamenti di Programmazione –linguaggio C, strutture dati e algoritmi elementari, C++.” IV edizione, Esculapio, 2017
- R. Sedgewick, “Algoritmi in C.”, IV edizione, Pearson, 2015
- S. Berretti, L. Carnevali, E. Vicario, “Fondamenti di Programmazione –linguaggio C, strutture dati e algoritmi elementari, C++.” IV edizione, Esculapio, 2017
Contenuti
- ALGORITMI AVANZATI: Algoritmi ricorsivi: funzioni ricorsive e parametri di funzioni ricorsive in C, condizione di terminazione, esempi di algoritmi ricorsivi e loro implementazione in C. Calcolo della complessità: introduzione alla valutazione della complessità di un algoritmo, utilizzo di espressioni asintotiche per esprimere la complessità computazionale di un algoritmo eloro proprietà e regole. Complessità computazionale di operazioni semplici, cicli e funzioni (ricorsive e non). Esempi di calcolo di complessità computazionale di programmi in C. Ricerca e ordinamento in strutture dati semplici. Algoritmi di ricerca: ricerca sequenziale e ricerca binaria. Loro implementazione in C e calcolo della loro complessità computazionale. Algoritmi di ordinamento semplici e evoluti: Bubble sort, Selection sort, Insertion sort, Shell sort, Quick sort, Merge sort. Loro implementazionein C e calcolo della relativa complessità computazionale.
- STRUTTURE DATI ELEMENTARI E AVANZATE: Tipi di dato astratto: liste, pile e code. Liste concatenate: ricerca, inserimento in testa, in coda e ordinato, cancellazione. Liste doppiamente concatenate:ricerca, inserimento in testa, in coda e ordinato, cancellazione. Implementazione delle liste tramite array collegati e tramite allocazione dinamica della memoria e puntatori in C. Implementazione di pile e code con liste concatenate e con array monodimensionali in C. Code circolari. Operazioni di push, pop e peak. Operazioni di enqueue e dequeue. Strutture dati complesso: grafi e alberi. Definizione di grafo. Grafi orientati e non orientati. Rappresentazione dei grafi con matrici di adiacenza e liste di adiacenza in C. Algoritmi di attraversamento dei grafi: in ampiezza e in profondità. Loro implementazione in C. Definizione di albero come grafo aciclico. Definizione di albero binario, algoritmi di attraversamento e loro implementazione in C. Definizione di albero binario di ricerca. Algoritmi di creazione, inserimento ordinato, cancellazione, ricerca e loro implementazione in C.
- STRUTTURE DATI ELEMENTARI E AVANZATE: Tipi di dato astratto: liste, pile e code. Liste concatenate: ricerca, inserimento in testa, in coda e ordinato, cancellazione. Liste doppiamente concatenate:ricerca, inserimento in testa, in coda e ordinato, cancellazione. Implementazione delle liste tramite array collegati e tramite allocazione dinamica della memoria e puntatori in C. Implementazione di pile e code con liste concatenate e con array monodimensionali in C. Code circolari. Operazioni di push, pop e peak. Operazioni di enqueue e dequeue. Strutture dati complesso: grafi e alberi. Definizione di grafo. Grafi orientati e non orientati. Rappresentazione dei grafi con matrici di adiacenza e liste di adiacenza in C. Algoritmi di attraversamento dei grafi: in ampiezza e in profondità. Loro implementazione in C. Definizione di albero come grafo aciclico. Definizione di albero binario, algoritmi di attraversamento e loro implementazione in C. Definizione di albero binario di ricerca. Algoritmi di creazione, inserimento ordinato, cancellazione, ricerca e loro implementazione in C.
Corsi
Corsi
3 anni
No Results Found
Persone
Persone
Professori/esse Associati/e
No Results Found