INF/01

Curriculum: PERCORSO COMUNE

A.Y. Credits Duration (hours)
Period Location
2017/2018 12 96 Annual Course URBINO

Courses taught in foreign languages
Course with optional materials in a foreign language: English

* This course is entirely taught in Italian. Study materials can be provided in the foreign language and the final exam can be taken in the foreign language.

Belonging to the Degree Courses

Lecturer

Marco Bernardo


marco.bernardo@uniurb.it
Office Hours for Students: Wednesday 16.00 - 18.00

Learning Objectives
The objective of this course is to illustrate the basic principles, the techniques, and the tools for programming computer applications, through the presentation of the concepts typical of procedural imperative programming and logical declarative programming.

Syllabus
01. Introduction to computer programming
       01.01 Basic definitions in informatics
       01.02 A bit of history of informatics
       01.03 Elements of computer architecture
       01.04 Elements of operating systems
       01.05 Elements of programming languages and compilers
       01.06 A methodology for developing software "in the small"

02. Procedural programming: the language ANSI C
       02.01 A bit of history of C
       02.02 Format of a program with a single function
       02.03 Library inclusion
       02.04 Function main
       02.05 Identifiers
       02.06 Predefined data types: int, double, char
       02.07 Library functions for interactive input/output
       02.08 Library functions for file-based input/output

03. Expressions
       03.01 Symbolic constant definition
       03.02 Variable declaration
       03.03 Arithmetical operators
       03.04 Relational operators
       03.05 Logical operators
       03.06 Conditional operator
       03.07 Assignment operators
       03.08 Increment/decrement operators
       03.09 Operator comma
       03.10 Type of the expressions
       03.11 Precedence and associativity of the operators

04. Statements
       04.01 Assignment statement
       04.02 Compound statement
       04.03 Selection statements: if, switch
       04.04 Repetition statements: while, for, do-while
       04.05 Statement goto
       04.06 Fundamental theorem of structured programming

05. Procedures
       05.01 Format of a program with several functions on a single file
       05.02 Function declaration
       05.03 Function definition and formal parameters
       05.04 Function invocation and actual parameters
       05.05 Statement return
       05.06 Parameters and result of function main
       05.07 Passing parameters by value and by reference
       05.08 Recursive functions
       05.09 Stack-based sequential execution model
       05.10 Format of a program with several functions on several files
       05.11 Scope of local and nonlocal identifiers

06. Data types
       06.01 Data type classification and sizeof operator
       06.02 Type int: representation and variants
       06.03 Type double: representation and variants
       06.04 Mathematical library functions
       06.05 Type char: representation and library functions
       06.06 Enumerated types
       06.07 Type conversions and cast operator
       06.08 Arrays: representation and indexing operator
       06.09 Strings: representation and library functions
       06.10 Structures and unions: representation and dot operator
       06.11 Pointers: operators and library functions

07. Correctness of procedural programs
       07.01 Hoare triples
       07.02 Determining the weakest precondition
       07.03 Verifying the correctness of iterative procedural programs
       07.04 Verifying the correctness of recursive procedural programs

08. Introduction to mathematical logic
       08.01 A bit of history of logic
       08.02 Elements of set theory
       08.03 Relations, functions, operations
       08.04 Induction principle

09. Propositional logic
       09.01 Syntax of propositional logic
       09.02 Semantics and decidability of propositional logic
       09.03 Consequence and equivalence in propositional logic
       09.04 Algebraic properties of the logical connectives
       09.05 Deduction systems for propositional logic

10. Predicate logic
       10.01 Syntax of predicate logic
       10.02 Semantics and undecidability of predicate logic
       10.03 Consequence and equivalence in predicate logic
       10.04 Algebraic properties of the quantifiers
       10.05 Deduction systems for predicate logic

11. Logic programming: the language Prolog
       11.01 Normal forms for propositional and predicate logic
       11.02 Herbrand theory and refutation algorithm
       11.03 Robinson resolution for propositional logic
       11.04 Unification of predicate logic formulas
       11.05 Robinson resolution for predicate logic
       11.06 Prolog: Horn clauses and SLD resolution strategy
       11.07 Prolog: terms and predicates
       11.08 Prolog: input/output, cut, negation, miscellany

12. Laboratory activities in Linux
       12.01 A bit of history of Linux
       12.02 File management in Linux
       12.03 The editor gvim
       12.04 The compiler gcc
       12.05 The maintenance utility make
       12.06 The debugger gdb
       12.07 Implementation of the C programs introduced in the lectures
       12.08 The compiler/interpreter gprolog
       12.09 Implementation of the Prolog programs introduced in the lectures

Bridging Courses
There are no mandatory prerequisites.

It is recommended to take the exam of Procedural and Logic Programming after taking the exam of Discrete Structure and Linear Algebra and before taking all the other exams except those of mathematics and physics.

Learning Achievements (Dublin Descriptors)
Knowledge and understanding
The student will acquire the fundamental knowledge in the field of computer programming, especially for the procedural imperative programming paradigm exemplified through the ANSI C language and the logical declarative programming paradigm exemplified through the Prolog language, and will become familiar with the terminology for constant definitions, variable declarations, arithmetical-logical expressions, programming statements, functions, predicates, parameters, libraries, and data types. Moreover, the student will know a methodology for developing small-size software systems, as well as the technique of Hoare triples for verifying their correctness. Finally, the student will learn the syntactical, semantical, algebraic, and deductive concepts underpinning propositional logic and predicate logic that are necessary for logic programming.

Applying knowledge and understanding
The student will be able to design and develop small-size software systems by means of the application of a methodology that covers problem analysis, algorithm design, and program implementation, testing, verification, and maintenance. As far as the implementation phase is concerned, the student will know to carry it out through both a procedural imperative programming language and a logical declarative programming language.

Making judgements
The student will be able to evaluate and compare alternative designs of the same small-size software system, as well as to analyze and contrast alternative implementations of the same software design.

Communication skills
The student will be able to appropriately use the terminology of procedural imperative programming languages and of logical declarative programming languages. Furthermore, the student will know to illustrate the main characteristics of the design and the implementation of a small-size software system, including the production of the software system documentation in terms of technical report, internal comments, and user manual.

Learning skills
The student will acquire the capacity of learning the syntactical and semantical features of any procedural imperative programming language and of any logical declarative programming language.

Didactics, Attendance, Course Books and Assessment
Didactics
Theory lectures and laboratory exercises.
Attendance
Although strongly recommended, course attendance is not mandatory.
Course Books
Hanly, Koffman, "Problem Solving and Program Design in C", Addison-Wesley, 2016
(Hanly, Koffman, "Problem Solving e Programmazione in C", Apogeo, 2013).

Kernighan, Ritchie, "The C Programming Language", Prentice Hall, 1988
(Kernighan, Ritchie, "Il Linguaggio C", Pearson/Prentice Hall, 2004).

Asperti, Ciabattoni, "Logica a Informatica", McGraw-Hill, 1997
(Schöning, "Logic for Computer Scientists", Birkhäuser, 2008).

Console, Lamma, Mello, Milano, "Programmazione Logica e Prolog", UTET, 1997
(Sterling, Shapiro, "The Art of Prolog", MIT Press, 1997).

Assessment
Project, written exam, and oral exam.

The project, which changes at each exam session, has to be submitted at least 10 days before the written exam. It is passed if the mark is at least 18/30; the mark is valid until the second exam session after the one in which the project is submitted. In case of late submission, a 3/30 penalty is applied for each day after the deadline. Should the project be resubmitted in a subsequent exam call, the mark of the previously submitted project is canceled; if the resubmission takes place in the same exam session, a 5/30 penalty is applied to the mark of the newly submitted project because the developers can benefit from the correction of the previously submitted project.

The written exam, which changes at each exam call and can be taken only if the project has been passed, consists of 9 questions plus 2 exercises to carry out in 90 minutes. It is passed if the mark is at least 18/30; the mark is valid only for the exam call in which the written exam is taken.

The oral exam, which can be taken only if the project and the written exam have been passed, consists of a discussion of the project and of the written exam, plus further questions. If passed, it determines an adjustment between -5/30 and 5/30 of the average of the two previous marks, thus yielding the final mark.

For further information about projects and written exams > www.sti.uniurb.it/bernardo/teaching/prog_proc_logi/

Note
The course offers additional e-learning facilities on the Moodle platform > elearning.uniurb.it