15305 - Foundations of Informatics A

Academic Year 2012/2013

Learning outcomes

By the end of the course, students will have basic knowledge about computation, imperative, structured and OO programming, of data structures and algorithms. In particular, he/she will be able to: design basic algorithms to manipulate data structures, implement such algorithms and simple applications in Java and C

Course contents

Introduzione. Il concetto di elaboratore elettronico e computazione algoritmica. I principali risultati delle teoria della computazione classica: automi, funzioni ricorsive primitive, tesi di Church, incompletezza di Goedel. I linguaggi di programmazione e il sistema operativo.
La valutazione delle espressioni. I concetti di valore, tipo di dato, operatore ed espressione. I tipi primitivi, stringhe ed array, e loro operatori. Schemi di compilazione ed interpretazione. Abstract Syntax Tree e valutazione di una espressione.
La programmazione imperativa e strutturata. I concetti di assegnamento, variabile, e statement. I costrutti di programmazione strutturata. Principali aspetti di sintassi, e esecuzione. Algoritmi iterativi per l'elaborazione di sequenze. 
La programmazione funzionale. L'astrazione di funzione. Ricorsione e algoritmi ricorsivi per l'accesso alle sequenze.  Il record di attivazione. Confronto fra algoritmi ricorsivi ed algoritmi iterativi. La ricorsione tail. Assegnamento ed array: il problema del side-effect.
La programmazione con strutture dati. La classe Java come modulo. Oggetti, costruttori, metodi e campi. I tipi di dato e la loro implementazione con gli oggetti. Implementazione di strutture dati rilevanti in Java.
Costruzioni Algoritmi. Aspetti metodologici nella costruzione degli algoritmi. Algoritmi base: ricerca, ordinamento, analisi numerica.
La programmazione nel linguaggio C. Strutture dati e operatori in C. Costrutti per la programmazione imperativa e per la ricorsione. Array e puntatori. Input e Output. 
Sviluppo di programmi C. Compilazione di programmi C. Librerie per il linguaggio C. Costruzione di applicazioni in C.

Readings/Bibliography

Suggested only to deepen some topic:
Informatica teorica e Programmazione
    * Ceri, Mandrioli, Sbattella. “Informatica: arte e mestiere”, McGraw Hill     * Aho, Ullman. “Fondamenti di Informatica”, Zanichelli, Ghezzi, Mandrioli.     * “Informatica Teorica”, CLUP, Milano, 1989
Java
    * “Java2: i Fondamenti”, McGraw-Hill (Sun Microsystems Press), 1999     * “Java Language Specification”, McGraw-Hill (Sun), can be downloaded through: http://java.sun.com/docs/books/jls/index.html     * Goodrich, Tamassia, "Strutture dati e algoritmi in Java", Zanichelli
C:
    * Bellini, Guidi. "Linguaggio C: guida alla programmazione", McGraw-Hill     * Deitel, Deitel. "C: How to Program", Pearson International Edition

Teaching methods

Approximately 7 hours of lesson per week, typically 4/5 in the teaching room and 2/3 in the lab

Assessment methods

Written test on Java and C programming in lab   Quiz-based theory test on all the course topic

Teaching tools

Slides projected during the lessons, published on the web site   Software: Java Development Kit, GNU C Compiler (GCC)

Links to further information

http://apice.unibo.it/xwiki/bin/view/MirkoViroli/

Office hours

See the website of Mirko Viroli