Scientific Disciplinary Sector (SSD)
INF/01 - INFORMATICS
II semestre dal Mar 4, 2019 al Jun 14, 2019.
The course introduces the fundamental discrete structures by emphasizing their use in the definition of mathematical models of biological relevance. The students will acquire knowledge about the es-sentials of discrete mathematics; formal notions and methods for studying problems by means of computers; methods for representation of biological information; and they will be able to apply such knowledge to analyze biological data of different types (genomic sequences, biological processes, networks of biological interactions) by means of information theoretic concepts.
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. Recurrent schemata. Outlines of first order logical languages (terms, formulas, interpretations). Elements of combinatorics: allocations and partitions, binomial and multinomial coefficients. Multisets, Partitions of sets and integers. Formal languages, grammars and automata. Patterns and regular expressions, Chomsky hierarchy, finite state automata. Computing automata and Turing macjine. Decidability, semidecidability ed undecidability.
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.
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).