Architettura di un elaboratore: codifica dell'informazione, circuiti combinatori e sequenziali, CPU, RAM, periferiche.
Algoritmi e strutture dati: iterazione e ricorsione, strutture dati concrete e astratte. Complessità, algoritmi di ricerca. Algoritmi di ordinamento.
"Reti logiche" - C. Bolchini, C. Brandolese, F. Salice, D. Sciuto – Apogeo
"Struttura e progetto dei calcolatori" - D. A. Patterson, J. L. Hennessy – Zanichelli
"Introduzione all’informatica" - P. Tosoratti – Ambrosiana.
"Introduzione ai sistemi informatici" - D. Sciuto, G. Buonanno, L. Mari – Mc Graw-Hill
"Algoritmi e strutture dati" - Demetrescu, Finocchi, Italiano - McGraw-Hill
Obiettivi Formativi
Acquisizione di conoscenze teoriche e tecniche di base sul funzionamento e sulle caratteristiche proprie dei processori, memoria centrale, memorie di massa, dispositivi comuni di I/O. Apprendere come risolvere un problema mediante un algoritmo ottimo. Conoscenza sulle strutture dati interne e astratte e dei principali algoritmi di ricerca e di ordinamento.
Prerequisiti
Conoscenze di matematica e fisica di scuola media secondaria.
Capacità logiche-astratte.
Metodi Didattici
Conoscenza e capacità di comprensione: lezioni frontali
Conoscenza e capacità di comprensione applicate: esercitazioni in classe e esercizi da svolgere in autonomia
Autonomia di giudizio:
discussione degli argomenti in programma
Capacità di apprendere: lezioni frontali
Altre Informazioni
Frequenza delle lezioni in aula e in laboratorio: raccomandata.
Orario di ricevimento: per appuntamento (contattare il docente tramite e-mail o numero di telefono).
Modalità di verifica apprendimento
L’esame finale ha lo scopo di accertare l’acquisizione delle conoscenze e delle abilità tramite lo svolgimento di una prova scritta della durata di 2 ore senza l'aiuto di appunti o libri. La prova scritta consiste di 6 quesiti divisi tra esercizi e parti teoriche sul programma svolto a lezione.
La prova orale è facoltativa e consiste, eventualmente, in una conversazione con il docente volta a far emergere la capacità di di problem solving e le conoscenze acquisite.
Programma del corso
Architettura di un elaboratore:
- Codifica delle informazioni: numeriche (naturali, interi, reali), alfanumeriche (ASCII e UNICODE), analogiche e istruzioni con riferimento al linguaggio macchina.
- Caratteristiche e funzionalità dei dispositivi che compongono una macchina secondo l’architettura di Von Newmann con particolare riferimento a central processing unit (ALU+CU), registri, cache, buffer, RAM, e ROM (PROM, EPROM,EEPROM, Flash ROM) introducendo i circuiti combinatori e sequenziali. Studio delle caratteristiche e delle funzionalità delle periferiche: memorie di massa (dischi ottici e magnetici), dispositivi di puntamento, dispositivi di input/output di uso comune.
Il ragionamento algoritmico:
- definizione del problema, modello,produzione di una soluzione, descrizione della soluzione formulata (tramite istruzioni di I/O, istruzioni
operative, istruzioni di controllo ossia condizionali e cicli), definizione e proprietà di un algoritmo
- algoritmi iterativi e ricorsivi
- complessità di un algoritmo nel caso migliore, medio e peggiore e ordini di grandezza con definizione di algoritmo ottimo per una data classe di problemi, calcolo tramite elementi di calcolo combinatorio e metodi per la risoluzione di ricorrenze
Strutture dati:
- strutture dati interne: variabili, array e record
- strutture dati astratte: liste, pile, code e alberi con implementazione delle operazioni di base per ciasun tipo con valutazione delle complessità computazionali.
Algoritmi di ricerca: sequenziale, dicotomica, alberi di ricerca, alberi AVL , alberi 2-3, funzioni hash con metodi per la risoluzione delle collisioni con loro valutazione della complessità computazionale.
Algoritmi di ordinamento: insertion sort, a bolle, quick sort, merge sort e radix sort con loro valutazione della complessità computazionale.
Dall'algoritmo al codice eseguibile: i linguaggi di programmazione, compilazione, interpretazione e linkaggio.