View syllabus
FOUNDATION OF COMPUTING
UGO GIOVANNI ERASMO MONTANARI
Academic year2020/21
CourseCOMPUTER SCIENCE
Code648AA
Credits6
PeriodSemester 2
LanguageEnglish

ModulesAreaTypeHoursTeacher(s)
FOUNDATION OF COMPUTINGINF/01LEZIONI48
UGO GIOVANNI ERASMO MONTANARI unimap
Syllabus not available in selected language
Learning outcomes
Knowledge

Students are expected to learn the essential properties of some widely employed models of computation for higher order, concurrency, interaction, mobility. Algebraic semantics and elementary category theory are employed.

Assessment criteria of knowledge

The student can choose between two kinds of assessment.

(i) With an oral exam, the student should demonstrate his/her ability to discuss the main course contents using the appropriate notation and terminology.

(ii) With a public seminar, the student should demonstrate his/her ability to approach a circumscribed research problem chosen with the help of the teacher, to study the relevant literature, and to organize an effective exposition of the results.

Methods:

  • Final oral exam
  • Final essay
Teaching methods

Delivery: face to face

Learning activities:

  • attending lectures
  • participation in seminar
  • individual study
  • bibliography search

Attendance: Advised

Teaching methods:

  • Lectures
  • Seminar
  • project work
Syllabus

Logic and algebraic foundations of computer science

Simply typed lambda calculus

Curry-Howard isomorphism PCF and its cpo model, with applications to functional programming languages

Elements of recursive and polymorphic types, with applications to object oriented programming languages

Categories as partial algebras

Monoidal, cartesian and cartesian closed (CCC) categories

CCC as models of simply typed lambda calculus

Algebraic specifications, categories of models and adjunctions

Petri nets and their (strictly) symmetric monoidal models

Milner Calculus for Communicating Processes (CCS)

Labelled Transition Systems (LTS) as coalgebras

Compositional LTS as bialgebras, CCS

The Pi-Calculus and its presheaf coalgebraic models

HD Automata

Quantum processes

Bibliography

John Mitchell, "Foundations for Programming Languages", MIT Press, 1996. Chapters: 2.5,4,5,7.2,9,10,11.

Roberto Bruni, Ugo Montanari, Costruzioni per la Semantica Operazionale della Concorrenza, in: Claudio Bartocci e Piergiorgio Odifreddi, Eds., La Matematica, Vol. 4, Pensare il Mondo, Einaudi, 2010, or equivalent papers in English.

Handwritten notes by the teacher.

Updated: 19/01/2021 16:59