Fondamenti di Informatica A 2014/2015

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

• 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. Comparing 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 management in C.

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

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

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

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