15305 - Foundations of Informatics A

Course Unit Page

Academic Year 2009/2010

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. Activation record. Omparing recursive and iterative algorithms. Tail recursion. Assignments and arrays: side-effects.

Procedural and Modular Programming. The Java class as a module. Global variables and initialization. Access modifiers. Packages and usage of Java library. Java Development Kit.

Programming with Abstract Data Types. Java objects: constructors, methods, fields. Syntax, typing, evaluation. Run-time management. ADTS and their implementation as objects. Implementing data structures in Java.

Elements of Object-Oriented Programming. Classes, objects, methods and fields. Inheritance. Java Libraries.

Programming in the C language. Data structures in C. Arrays and pointers. Input/Output. Compiling C programs.

Readings/Bibliography

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

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 topics

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://www.ingce.unibo.it/~mviroli/

Office hours

See the website of Mirko Viroli

See the website of Sara Montagna