OVERVIEW

The course studies the main computer science models (grammars automaton, turing machines. This theoretical part is complemented with a practical part using JAVA, where the theoretical topics are showed thorugh impelemtation.

AIMS AND CONTENT

AIMS AND LEARNING OUTCOMES

The student will acquire competences related to:

- understand syntax and semantics of propositional logic

- given a language, understand what type of grammar/automaton/turing machines can recognize it, and define the related grammar/automaton/turing machines

- being able to implement in JAVA tasks related to the topics above, e.g., (a) given a propositional formula, state whether it is satisfiable or not; (b) implement a parser for a given grammar that recognizes a certain languag; (c) implement (basic) simulators for automaton and turing machines.

PREREQUISITES

Basics of Computer Science: Given a problem being able to define its solving algorithms. Basic concept about programming languages (e.g., C)

TEACHING METHODS

The course is organize in theoretical (approx. 50%) and practical (approx. 50%) lectures.

SYLLABUS/CONTENT

- Course introduction

- Propositional logic: syntax and semantics Logica Proposizionale: Sintassi e Semantica

- Induction

- Grammars (linear, contestual)

- Linguaggi

- Finite, non deterministic automaton; pushdown automaton

- Turing machines

- JAVA: introduction, main constructs, object oriented programming

- Implementation in JAVA of tasks related to the theoretical topcis above

RECOMMENDED READING/BIBLIOGRAPHY

All slides and exercises done in class will be made available through AulaWeb.

Such material should be enough, but there are also the following books the students may want to consider:

(Teoria) L.C. Aiello, F. Pirri. Strutture, Logica, Linguaggi. Pearson / Addison Wesley editore

(Pratica) C.S. Horstmann, G. Cornell. Core JAVA 2 Volume I – Fondamenti. Pearson / Prentice Hall editore

TEACHERS AND EXAM BOARD

Exam Board

ARMANDO TACCHELLA (President)

LUCA ONETO

ALESSIO MERLO (President Substitute)

LESSONS

LESSONS START

In the week of 20-24 February 2023

Class schedule

The timetable for this course is available here: Portale EasyAcademy

EXAMS

EXAM DESCRIPTION

The exam is composed by a written exam, an oral exam, and a practical project.

The written exam spans all theoretical topcis, mainly exercises related to these topcis, plus an exercise in JAVA (material can NOT be used).

The oral exam is on all topcis. Students can access the oral exam if they passed the written exam and have completed the project.

ASSESSMENT METHODS

The written exam will verify if the student has acquired sufficient competences via excercises related to the topics of the course.

The oral exam will verify if the student has acquired sufficient competences also on the theoretical aspects, the interaction with the exercises, and on JAVA.

Exam schedule