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?