Topics in mathematical foundations of computer science

2025/2026

Programme:

Doctoral Programme Mathematics and Physics

Orientation:

Mathematics

Year:

1 ali 2 year

Semester:

first or second

Kind:

optional

ECTS:

Language:

slovenian, english

Course director:

Prof. Dr. Andrej Bauer, Prof. Dr. Sergio Cabello Justo, Assoc. Prof. Dr. Matija Pretnar, Prof. Dr. Alexander Keith Simpson

Lecturer (contact person):

Prof. Dr. Alexander Keith Simpson, Assist. Prof. Doctor of philos Andrew Wakelin Swan

Hours per week – 1. or 2. semester:

Lectures

Seminar

Tutorial

Lab

There are no prerequisites.

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.

T. H. Cormen ... [et al.]: Introduction to Algorithms, 2nd ed. - Cambridge (Mass.) : MIT Press ; Boston : McGraw-Hill, cop. 2001.
P. Doreian, V. Batagelj, A. Ferligoj: Generalized blockmodeling, Cambridge : Cambridge University Press, 2005.
M. Huth, M. Ryan: Logic in computer science : modelling and reasoning about systems, 2nd ed., Cambridge : Cambridge University Press, 2019.
J. Matoušek: Lectures on discrete geometry, New York : Springer, cop. 2002.
M. Petkovšek, H. S. Wilf, D. Zeilberger: A=B, Wellesley (Massachusetts) : A. K. Peters, cop. 1996.
B. C. Pierce: Types and programming languages, Cambridge (Massachusetts) : The MIT Press, cop. 2002.
H. Rogers: Theory of recursive functions and effective computability, New York : McGraw-Hill, cop. 1967.
D. R. Stinson: Cryptography : theory and practice, 3rd ed., Boca Raton : Chapman & Hall/CRC, cop. 2006.

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

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

Lectures, consultations, problem sessions

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

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]