Informational Methods (2014/2015)

Course code
4S00995
Name of lecturer
Vincenzo Manca
Coordinator
Vincenzo Manca
Number of ECTS credits allocated
6
Academic sector
INF/01 - INFORMATICS
Language of instruction
Italian
Period
II sem. dal Mar 2, 2015 al Jun 12, 2015.

Lesson timetable

II sem.
Day Time Type Place Note
Tuesday 11:30 AM - 1:30 PM lesson Lecture Hall D  
Wednesday 8:30 AM - 11:30 AM lesson Lecture Hall D  

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. Numbers of Stirling, Bell, Catalan. Magnitude orders and asymptotic orders. Outlines of discrete probability.

Assessment methods and criteria

Written and oral examination.

Statistics about transparency requirements (Attuazione Art. 2 del D.M. 31/10/2007, n. 544)

Statistics
Outcomes Exams Outcomes Percentages Average Standard Deviation
Positive 100.0% 23 3
Rejected --
Absent --
Ritirati --
Canceled --
Distribuzione degli esiti positivi
18 19 20 21 22 23 24 25 26 27 28 29 30 30 e Lode
3.3% 20.3% 20.3% 5.0% 6.7% 3.3% 10.1% 10.1% 5.0% 5.0% 5.0% 0.0% 5.0% 0.0%

Data from AA 2014/2015 based on 59 students. I valori in percentuale sono arrotondati al numero intero più vicino.