# Informational Methods (2016/2017)

Course code
4S00995
Name of lecturers
Vincenzo Manca, Giuditta Franco
Coordinator
Vincenzo Manca
Number of ECTS credits allocated
6
INF/01 - INFORMATICS
Language of instruction
Italian
Location
VERONA
Period
II sem. dal Mar 1, 2017 al Jun 9, 2017.

#### Lesson timetable

II sem.
Day Time Type Place Note
Monday 4:30 PM - 6:30 PM lesson Lecture Hall Gino Tessari from Mar 6, 2017  to Jun 9, 2017
Wednesday 3:30 PM - 6:30 PM lesson Lecture Hall A from Mar 8, 2017  to Jun 9, 2017

#### Learning outcomes

The course intends to introduce the fundamental discrete structure by emphasizing their use in the definition of mathematical models of biological relevance. In the first part, after an introduction to the basic discrete structures, the number systems are analyzed, with the number representation systems, and the principle of structural induction. Then, the main concepts of formal language theory are presented, by concluding with the study of the principal combinatorial schemata.

#### Syllabus

Discrete structures: sets, multisets, sequences, strings, operations, relations, functions, variables, parentheses and expressions. Numbers and induction: number systems, number representations, proofs by induction, definitions by induction of important number sequences. Structural induction over strings, trees e graphs. Outlines of first order logical languages (terms, formulas, interpretations). Formal languages, grammars and automata. Patterns and regular expressions, Chomsky hierarchy, finite state automata. Computing automata and Turing macjine. Decidability, semidecidability ed undecidability. Elements of combinatorics: allocations and partitions, binomial and multinomial coefficients. Enumeration of partitions and multisets.

 Author Title Publisher Year ISBN Note Vincenzo Manca Infobiotics Springer 2013

#### Assessment methods and criteria

Written and oral examination.

The written exam requires that the student is able to use correctly the formalism taught in the course for expressing synthetically and correctly the solutions to the problems asked in the exam text.

The oral examination starts by checking the answers given by the student in the written exam, possibly by asking specific clarifications and motivations to specific passages and statements. During this verification the student is also asked to refer about specific points of the course, with the intention of checking the understanding of the main concepts that the course intends to teach.

Teaching Material
Manca, V. - Infobiotics. Springer, 2013 (Chapters 5, 6, 7).
Manca V. - Vademecum all'Esame di Metodi Informazionali (with a list of definitions and theorems plus 100 exercises with the corresponding solutions).