Obiettivi Formativi

Il corso di Fondamenti di Informatica intende fornire le conoscenze di base degli aspetti teorici e pratici dell'informatica moderna che rappresentano per gli studenti un prerequisito fondamentale per proseguire con successo nella loro formazione nellambito dellingegneria dellinformazione. Obiettivo formativo del corso è quello di trasmettere agli studenti una forma di pensiero computazionale ovvero la capacità di pensare in maniera algoritmica e di codificare gli algoritmi progettati in programmi eseguibili da un calcolatore elettronico attraverso un linguaggio di programmazione di alto livello. Gli studenti saranno resi in grado di analizzare un problema complesso, suddividerlo in sotto-problemi, ognuno dei quali può essere risolto tramite lutilizzo di strutture dati e algoritmi noti, e ricombinare i risultati ottenuti per giungere alla soluzione del problema iniziale. Il corso ha un taglio sia teorico che pratico che permetterà agli studenti di partire dai fondamenti e dalle metodologie dell'informatica di base e di arrivare ad essere in grado di progettare e implementare programmi informatici in grado di risolvere semplici problemi nellambito delle tecnologie dell'ingegneria dell'informazione.

Metodi didattici

Lezioni frontali, attività laboratoriali ed esercitazioni in classe. Il corso si svolge prevalentemente attraverso lezioni frontali su specifici aspetti disciplinari ma sono previste anche frequenti attività laboratoriali ed esercitazioni in classe che consentiranno agli studenti di prendere manualità con i principi di base della programmazione.

Prerequisiti

Sono richieste conoscenze di base di analisi matematica, geometria e logica matematica.

Verifiche dell'apprendimento

Sono previste due prove in itinere e una prova finale. La prima prova in itinere (con domande a risposta multipla e aperta) verterà sugli argomenti relativi alla prima fase del corso e mirerà a verificare che gli studenti abbiano acquisito le conoscenze di base relative allinformatica moderna. La seconda prova in itinere sarà effettuata al calcolatore e consisterà nella progettazione e implementazione di un programma in linguaggio C che rispetti i requisiti richiesti. Tale prova mirerà a verificare che gli studenti abbiano acquisito la capacità di valutare e selezionare le alternative disponibili per la soluzione di un problema e che siano in grado di progettare e sviluppare nuove applicazioni attraverso un linguaggio di programmazione di alto livello. Infine la prova finale sarà un esame orale che verterà sugli argomenti dellultima parte del corso. In particolare, gli studenti saranno chiamati a dimostrare di conoscere e di sapere utilizzare le strutture dati e i relativi algoritmi mostrati a lezione.

Programma del Corso

Prima fase FONDAMENTI DELLINFORMATICA MODERNA: Introduzione all'informatica. Il calcolatore elettronico, macchina di Von Neumann. Gerarchie di memorie. Sistemi numerici posizionali. Sistema binario. Conversioni di base. Operatori aritmetici nel sistema binario. Algoritmi, dati ed istruzioni, programmazione strutturata, Teorema di Böhm-Jacopini. Codifica degli algoritmi, linguaggio naturale, linguaggio di programmazione, pseudo-codice. Diagrammi di flusso. Algebra booleana. Linguaggi e grammatiche. Grammatiche formali. Backus-NaurForm (BNF). Linguaggi di programmazione: linguaggio macchina, Assembler, linguaggi di alto livello. Compilatori ed interpreti. Compilatori per linguaggio C, GCC. Seconda Fase IL LINGUAGGIO C: Caratteristiche del linguaggio C, struttura di un programma C, principali librerie. Tipi di dato, tipi elementari. Stringhe e I/O da terminale. Operatori ed espressioni, precedenza ed associatività, overloading degli operatori, conversioni di tipo. Istruzioni semplici, istruzioni di controllo, blocchi, regole di visibilità. Costrutto if e costrutto switch-case. Costrutti while, do-while e for. Tipi di dato strutturato in C. Array: definizione, operatori, inizializzazione. Gestione della memoria, Heap. Puntatori e loro operatori. Implementazione di array con puntatore. Le strutture. Tipi enumerativi. Le unioni. Tipi di dato definiti dall'utente. Le funzioni. Passaggio dei parametri per valore e per riferimento, utilizzo dei puntatori. Gestione dei file, file di testo e binari, canali standard, uso dei buffer. Terza Fase ALGORITMI E STRUTTURE DATI: 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 e loro 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 implementazione in C e calcolo della relativa complessità computazionale. 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.