Problems and their learning goals

Case 0 Morse alphabet -- Basic consepts

Goal: To learn the basic concepts like alphabet, strings, languages, consideration that all symbolic languages can be coded by binary alphabet. Practising the problem-based method.

Case 1 Problem solving company -- Modelling problems, their difficulty and solvability

Goal: Overview of modelling problems, their difficulty and solvability. The need for formal languages (descriptions), Chomsky hierarchy of languages, existence of unsolvable problems. (In a more profound way in the end of course.)

Case 2 Search for mail addresses -- Regular expressions

Goal: To understand the idea of regular expressions and construct a describing expression for a given problem. (Also about restrictions of understanding the meaning of text, when only syntactic means are used.)

Case 3 Coffee automaton -- Deterministic finite automata

Goal: To learn how to construct a deterministic finite automaton and represent it as a program.

Case 4 Anssi and Yengeny checking exams -- Finite automata vs. regular expressions, epsilon-automata.

Goal: To learn how to construct a finite automaton corresponding a regular expression and vice versa. Also epsilon-automata and determinization and minimization are needed.

Case 5 Grandma's rhyme -- Pumping Lemma

Goal: To understand the limits of regular languages and how to recognize irregular languages. Pumping Lemma.

Case 6 L-systems -- grammars

Goal: To understand the idea of grammars, especially context-free grammars, and how to program simple grammar-based systems.

Case 7 Parantheses parsing -- Pushdown automaton

Goal: To learn to construct pushdown automata and how they can be programmed.

Case 8 Parser for simple programming language -- LL(1)-grammars, recursive parser

Goal: To understand the idea of LL(1)-grammars, how to transform nearly LL(1)-grammars into LL(1)-form and how to implement a recursive parser for it. (Also the idea of ''hidden'' stack in the recursive programs.)

Case 9 Summing machine -- basics of Turing machines

Goal: To understand the basic idea of Turing machines and how to construct them. Understanding that multiple tape machines are equivalent with standard TM's.

Case 10 Joensuu Safety & Trust -- solvable and unsolvable properties, meaning of the Universal machine

Goal: To understand the idea Universal machines and equivalence of Turing machines and computer programs. How to study properties of Turing machines/computer programs? The unsolvability of semantic properties.

Case 11 Extra problem: Philosophical considerations

Goal: To consider the meaning of main results concerning solvability and Church-Turing theses. Limits of computation.

Case 1 revisited -- overview of the principles learnt

Goal: To create an overview, how we can use the techniques and principles learnt in this course to analyze the computability and difficulty of any given problem.

Nondeterministic automata, the CYK-algorithm and Chomsky normal form, non-deterministic Turing machines

We didn't have any problems about these. They are still important learning goal. Could you invent good problems about these?

Other learning goals

The general learning goals of problem-based learning: to learn and get practise in general problem solving skills, to develop mature analytic thinking, learn to retrieve and organize information, cooperational skills and ability to express yourself, ... what else?