B012999 - MATHEMATICAL METHODS FOR COMPUTER SCIENCE

Italian

Introduction to the use of Discrete Mathematics and Enumerative Combinatorics in Computer Science. Formal power series and generating functions. Rational and algebraic generating functions. A brief outline of asymptotic analysis tools for the estimate of the coefficients of a generating function. Exhaustive generation of combinatorial structures: lexicographic algorithms and Gray codes. Algorithms for discrete structures: reconstruction, consistency and uniqueness problems related to finite sets of points, with or without a priori information.

Enumerative Combinatorics vol.I e II
CAMBRIDGE University Press.
E. Munarini, N. Zagaglia Salvi, Matematica Discreta, Citta’ Studi
Edizioni.
D.E. Knuth, The Art of Computer Programming, vol. 4, Addison-Wesley
Discrete Tomography: Foundations, Algorithms and Applications – G.T. Herman and A. Kuba eds. – Springer - 1999

Knowledge acquired:
Use of generating functions for the enumeration of combinatorial
structures, also in connection with the analysis of algorithms.
Techniques for the generation of combinatorial structures.
Techniques for the analisys and the reconstruction of discrete structures.
Competence acquired:
Competences in Combinatorics and its applications to computer science
problems.
Skills acquired (at the end of the course):
At the end of the course the students should be able to address and solve
many enumeration problems with the use of generating functions, also in
view of possible applications to the analysis of algorithms. Furthermore,
they should be able to use and design algorithms for the generation of
combinatorial structures and for their reconstruction in polynomial time, if possible, otherwise to prove the NP-hardness of the problem.

Courses recommended:
Computer Science
Algebra
Discrete Structures
Formal Languages and Codes
Logic and Computability

Total hours of the course (including the time spent in attending lectures,
seminars, private study, examinations, etc...): 225
Hours reserved to private study and other indivual formative activities:
153
Hours for lectures: 72
Hours for laboratory: 0
Hours for laboratory-field/practice: 0
Seminars (hours): 0
Stages (hours): 0
Intermediate examinations (hours): 0

Attendance of lectures, practice and lab:
Not mandatory
Teaching tools:
None
Office hours:
By appointment
Contact:
Viale Morgagni, 65 - 50134 Firenze
Phone: 055 2751484 (Ferrari)
055 2751482 / 329 2985755 (Barcucci)
055 2751476 (Frosini)
E-mail: luca.ferrari@unifi.it
elena.barcucci@unifi.it
andrea.frosini@unifi.it
Web: http://www.dsi.unifi.it/~ferrari/
e-l.unifi.it

Oral exam

Introduction to the use of Discrete Mathematics and Enumerative Combinatorics in Computer Science with examples and applications. Introduction of the concept of generating function and examples. Algebra of formal power series. Rational generating functions and classes of rational objects (lattice paths, polyominoes, trees, permutations). Lagrange inversion theorem. Algebraic generating functions and classes of algebraic objects (lattice paths, polyominoes, trees, permutations). Schutzenberger methodology. A brief outline of asymptotic analysis tools for the estimate of the coefficients of a generating function; applications to the analysis of algorithms. Generation of combinatorial structures (tuples, permutations, partitions, combinations, trees). Lexicographic algorithms. Combinatorial Gray codes: algorithmic and graph-theoretic aspects.Definition of the reconstruction, consistency and uniqueness problems for discrete structures from projections. Main results on the topic, and some examples of polynomial and NP-hard problems. Introduction of geometrical constraints and a priori information on the structures. Open problems.