3-1 Problem Solving

• 3-1-1 Information Hiding and Abstraction
• 3-1-2 Comparing Algorithms
• 3-1-3 Finite State Machines
• 3-1-4 Turing Machines
• 3-1-5 Intractable Problems
• 3-1-6 Regular Expressions, BNF and RPN

3-1-6 Regular Expressions, Backus-Neur Form and Reverse Polish Notation

Natural Language:

• Set of words,
• Syntax- rules for putting words together,
• Semantics- meanings.

Formal Language:

• Alphabet.
• Syntax.
• (no Semantics)
  e.g. post codes, number plates

Meta Language:

• Used to express the rules of a formal language.
  e.g. Regular, expressions, Backus-Naur Form

Regular Language:

• One that can be expressed as a Finite State Automata (non-deterministic FSM).

Regular Expression:

• Describes Valid Strings in a Formal Language
  e.g. of a Regular Expression Notation

                                                 a(a|b)* (* = no. of occurrences)
                    (This has to start with an a, and be followed by any number of a's or b's)

                             Valid: a, aa, aabab                                  Invalid: b, ba, abc
 

 

3-1-5 Intractable Problems

Algorithmic Problems

• can be solved using rules or a series of steps e.g. making a cake.

Non-Algorithmic Problems

• cannot be solved using rules or a series of steps e.g. who would win in a fight between B@man and Superman?

Algorithmic problems can be sorted into:

Finite Problems- a finite set of inputs which is solvable.

Infinite Problems- an infinite set of inputs which isn't necessarily solvable.


Non-Computable Problem

• a problem that has no algorithm to solve it. Not possible to compute.

Decision Problem

• a problem with a yes or no answer e.g. is this an odd number?

Decidable Problem

• a problem with an answer e.g. Do you wish to delete this file?

Undecidable Problem

• a decision-type algorithmic problem that isn't computable e.g. this statement is false.

Tractable Problem

• a problem that has a reasonable (Polynomial) time solution as the size of the input increases e.g. add up a row of numbers.

Intractable Problem

• a problem for which no reasonable (Polynomial) time solution has been found e.g. Travelling Salesman Problem.

The Heuristic Approach

• uses know-how and experiance to make guesses which help solve an intractable algorithmic problem in reasonable (Polynomial) time.
• the "Common Sense" approach.