Topics in mathematical foundations of computer science

2022/2023
Programme:
Doctoral Programme Mathematics and Physics
Orientation:
Mathematics
Year:
1 ali 2 year
Semester:
first or second
Kind:
optional
ECTS:
6
Language:
slovenian, english
Hours per week – 1. or 2. semester:
Lectures
2
Seminar
0
Tutorial
0
Lab
0
Content (Syllabus outline)

The content consists of a selection of standard topics in graduate-level computational mathematics such as: symbolic computation, computability theory, computational geometry, logic in computer science, theory of programming languages, algorithms and data structures, cryptography, network analysis, etc. The choice depends on students' research interests.

Readings

M. Petkovšek, H. S. Wilf, D. Zeilberger, A=B, Wellesley, Massachusetts, A K Peters, 1996.
J. Matoušek: Lectures on Discrete Geometry, Springer-Verlag, 2002.
T. H. Cormen, C. E. Leiserson, R. L. Rivest: Introduction to Algorithms, McGraw-Hill, 1990.
D. R. Stinson: Cryptography. Theory and practice, 3. izdaja, CRC Press, 2006.
B. C. Pierce: Types and Programming Languages, MIT Press, 2002.
M. Huth, Mark Ryan: Logic in Computer Science: Modelling and Reasoning about Systems, Cambridge University Press, 2000.
H. Rogers: Theory of Recursive Functions and Effective Computability, MIT Press, 1987.
P. Doreian, V. Batagelj, A. Ferligoj: Generalized Blockmodeling, Cambridge University Press, 2005.
S. Wasserman, K. Faust: Social Network Analysis: Methods and Applications, Cambridge University Press, 1994.

Objectives and competences

The main goal of the course is to provide students with some important topics in computational mathematics.

Intended learning outcomes

Knowledge and comprehension of presented concepts.
Ability to use acquired knowledge and skills.

Learning and teaching methods

Lectures, consultations, problem sessions

Assessment

Writen exam (homeworks), oral exam
grading: 5 (fail), 6-10 (pass) (according to the Statute of UL)

Lecturer's references

BAUER, Andrej, CVETKO-VAH, Karin. Stone duality for skew Boolean algebras with intersections. Houston journal of mathematics, ISSN 0362-1588, 2013, vol. 39, no. 1, str. 73-109. [COBISS-SI-ID 16620377]
BAUER, Andrej, STONE, Christopher A. RZ: a tool for bringing constructive and computable mathematics closer to programming practice. Journal of logic and computation, ISSN 0955-792X, 2009, vol. 19, no. 1, str. 17-43. [COBISS-SI-ID 15325785]
AWODEY, Steve, BAUER, Andrej. Propositions as [Types]. Journal of logic and computation, ISSN 0955-792X, 2004, vol. 14, no. 4, str. 447-471. [COBISS-SI-ID 13374809]
BAUER, Andrej, PETKOVŠEK, Marko. Multibasic and mixed hypergeometric Gosper-type algorithms. Journal of symbolic computation, ISSN 0747-7171, 1999, let. 28, št. 4-5, str. 711-736. [COBISS-SI-ID 9210969]
CABELLO, Sergio, GIANNOPOULOS, Panos. The complexity of separating points in the plane. Algorithmica, ISSN 0178-4617, 2016, vol. 74, iss. 2, str. 643-663. [COBISS-SI-ID 17195097]
CABELLO, Sergio. Hardness of approximation for crossing number. Discrete & computational geometry, ISSN 0179-5376, 2013, vol. 49, iss. 2, str. 348-358. [COBISS-SI-ID 16340313]
CABELLO, Sergio. Many distances in planar graphs. Algorithmica, ISSN 0178-4617, 2012, vol. 62, no. 1-2, str. 361-381. [COBISS-SI-ID 15702873]
SIMPSON, Alex. A characterization of the least-fixed-point operator by dinaturality. Theoretical computer science, ISSN 0304-3975, 1993, vol. 118, iss. 2, str. 301-314. [COBISS-SI-ID 17181017]
SIMPSON, Alex. Computational adequacy for recursive types in models of intuitionistic set theory. Annals of pure and applied Logic, ISSN 0168-0072. [Print ed.], 2004, vol. 130, iss. 1-3, str. 207-275. [COBISS-SI-ID 17117017]
AWODEY, Steve, BUTZ, Carsten, SIMPSON, Alex, STREICHER, Thomas. Relating first-order set theories and elementary toposes. Bulletin of symbolic logic, ISSN 1079-8986, 2007, vol. 13, no. 3, str. 340-358. [COBISS-SI-ID 17096537]
Matija Pretnar:
BAUER, Andrej, PRETNAR, Matija. An effect system for algebraic effects and handlers. Logical methods in computer science, ISSN 1860-5974, 2014, vol. 10, iss. 4, paper 9 (str. 1-29). http://arxiv.org/pdf/1306.6316 [COBISS-SI-ID 17191001]
PRETNAR, Matija. Inferring algebraic effects. Logical methods in computer science, ISSN 1860-5974, 2014, vol. 10, iss. 3, paper 21 (str. 1-43) [COBISS-SI-ID 17190745]
PLOTKIN, Gordon, PRETNAR, Matija. Handling algebraic effects. Logical methods in computer science, ISSN 1860-5974, 2013, vol. 9, iss. 4, paper 23 (str. 1-36) [COBISS-SI-ID 16816729]