15305 - Foundations of Informatics A

Academic Year 2008/2009

  • Docente: Mirko Viroli
  • Credits: 9
  • SSD: ING-INF/05
  • Language: Italian
  • Moduli: Mirko Viroli (Modulo 1) Matteo Casadei (Modulo 2)
  • Teaching Mode: Traditional lectures (Modulo 1) Traditional lectures (Modulo 2)
  • Campus: Cesena
  • Corso: First cycle degree programme (L) in Biomedical Engineering (cod. 0946)

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.

Algorithms and Complexity. Algorithms to sort and access sequences. Elements of complexity theory.

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

Theoretical Computer Science and Programming

  • 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), scaricabile al sito http://java.sun.com/docs/books/jls/index.html  
Programming:
  • “Algoritmi+Strutture Dati=Programmi”, Niklaus Wirth, Tecniche Nuove, 1987

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

Links to further information

http://www.ingce.unibo.it/~mviroli/

Office hours

See the website of Mirko Viroli

See the website of Matteo Casadei