15305 - Foundations of Informatics A

Academic Year 2013/2014

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

Theoretical Computer Science. The concept of computing machine and algorithmic computation. Formal grammars as tool to describe syntax of data and programs. Main result of classic computer science theory: automata, recursive functions, Church's thesis, Goedel incompleteness. Programming Languages.

Evaluation of Expressions. Concepts of value, data type, operator, and expression. Primitive types in Java, strings and arrays, their operators. Compilation and interpretation schemata. Abstract Syntax Tree, typing and expression evaluation.

Functional Programming. The functional abstraction: motivation, syntax, main typing and evaluation aspects. Recursion and algorithms to access sequences. Engineering functions: analysis and design. Designing signature, test function, implementation schemata: recursion and composition.

Imperative and Structured Programming. Assignment, variables and statements. Constructs for structured programming. Main typing, syntax, and evaluation aspects. Iterative algorithms to elaborate sequences.    
Functional Programming. The functional abstraction. Activation record. Omparing recursive and iterative algorithms. Tail recursion. Assignments and arrays: side-effects.

Procedural and Modular Programming. The Java class as a module. Java Development Kit.

Construction of Algorithms. Basic Algorithms: search and sort. Elements of Computational Complexity.

Programming in the C language. Data structures in C. Arrays and pointers. Input/Output. Compiling C programs. Elements of operating systems and file managment 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

See the website of Sara Montagna