73093 - Theoretical Informatics (1) (LM)

Academic Year 2023/2024

  • Docente: Aldo Gangemi
  • Credits: 6
  • SSD: INF/01
  • Language: Italian
  • Teaching Mode: Traditional lectures
  • Campus: Bologna
  • Corso: Second cycle degree programme (LM) in Philosophical Sciences (cod. 8773)

Learning outcomes

At the end of the course, the student knows the principles of computability and the principles for solving problems efficiently. The student is able to understand and use the main data structures for organising information and algorithms for computationally related tasks.

Course contents

The course consists of frontal lectures. Each lecture introduces a specific topic. The lectures are associated with hands-on sessions.

List of lectures (reduced and adapted from Silvio Peroni's Computational Thinking course):

  • Introduction to Computational Thinking
    - Comparing natural languages and programming languages
    - Abstraction: the main tool of Computational Thinking
  • Algorithms
    - What is an algorithm?
    - How to develop an algorithm: flowcharts
    - A basic algorithm: input, process, decision, output
  • Computability
    - The computational cost of an algorithm
    - The halting problem
    - Assessing the output: test-driven development
  • Programming Languages
    - A basic Python algorithm with variables, assignments, and conditional statements
  • Ordered data structures
    - Data structures
    - List
    - Stack
    - Queue
  • Brute-force algorithms
    - Iterations: for and while constructs
    - Linear search
    - Insertion sort
  • Unordered data structures
    - Infinite data structures?
    - Set
    - Dictionary
  • Recursion
    - An intuition
    - Recursive approaches and algorithms
  • Divide and conquer algorithms
    - Ordering billions of books
    - Merge sort
  • Trees
    - Genealogy and document markup
    - Trees
  • Graphs
    - Königsberg bridges
    - Graphs

Readings/Bibliography

(Sections of) the "Computational Thinking and Programming book" that has been created by Silvio Peroni for the Computational Thinking course.

Teaching methods

Frontal classes and hands-on sessions.

Assessment methods

A written test for assessing the competences acquired by the students on the topics of the course.

Teaching tools

Silvio Peroni's GitHub repository of the course will be freely used to exemplify and exercise over the contents of the course.

A group in a messaging application will be set for informal interaction among students, and with the teacher.

Office hours

See the website of Aldo Gangemi