Architettura di un elaboratore: codifica e decodifica dell'informazione, circuiti combinatori e sequenziali, CPU, RAM.
Algoritmi e strutture dati: iterazione e ricorsione, strutture dati concrete e astratte. Complessità, algoritmi di ricerca e ordinamento.
"Reti logiche" - C. Bolchini, C. Brandolese, F. Salice, D. Sciuto – Apogeo
"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.
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.
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 5 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), alfanumeriche (ASCII e UNICODE), 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 introducendo i circuiti combinatori e sequenziali. Studio delle caratteristiche e delle funzionalità delle periferiche: memorie di massa (dischi ottici, magnetici, memorie elettronche).
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 ciascun tipo con valutazione delle complessità computazionali.
Algoritmi di ricerca: sequenziale, dicotomica, alberi di ricerca, alberi AVL, valutazione della complessità computazionale.
Algoritmi di ordinamento: insertion sort, bubble sort, quick sort, merge sort ricorsivi e iterativi, valutazione della complessità computazionale.