Previously…
So far, we dealt with
models of automata and more sophisticated
machines.
Today, we will start delving into algorithms.
Remember?
Escape the maze.
Possible solutions:
What functionality do you need to design
these high-level
heuristics as algorithms?
move() to move your agent forwardturnLeft() and
turnRight() to turn your agentcanMove() to tell you’re blocked by a
wallvisitedBefore() to tell you if you
have visited a path beforeisExit() which tells you if you have
reached the exitWhy have we just written the functionality like this?
move()
In program code, this is how we call functions. More on that later.
What else do we need?
We need control instructions to control the flow of execution.
Control instructions are core components of
imperative
programming.
In imperative programming, algorithms are
described as a sequence
of commands to be executed.
Your algorithm is a description of how to achieve a certain result.
Imperative programming is a programming paradigm.
That is a high-level way to conceptualize and structure the implementation of a computer program.
In imperative programming, we have
There are also other paradigms:
https://www.getyarn.io/yarn-clip/87e76303-46c4-4cb3-9552-2b5cf2a9b2e7/gif
What kind of control instructions do we need to escape our maze?
To escape our maze, we need to
To decide, we use conditional statements.
If (A) Then
(B)
Else
(C)
End IfA is a Boolean expression. More on that
later.
The Else-part is optional!
To repeat, we use loops, here a condition-controlled loop:
While (A) do
(B)
DoneB is executed and repeated as long as the condition
A holds.
Another variant of this loop called do while loop:
Do
(B)
While (A)It executes B once before checking A the
first time.
To save our state, we need variables and assignments.
Variables are abstract storage locations with a symbolic name.
Variables contain some data or object referred to as a value.
Variables in CS are different from variables in mathematics!
In mathematics, variables refer to something that can be modified.
In computers, variables can actually change their value.
Assignments are the most fundamental construct in imperative programming.
x = 5This assigns the value 5 to a variable named
x.
The value of x can be changed later in the program
through subsequent assignments.
x = 5
# some other stuff
# happening here
x = 7To evaluate our state, we need expressions.
It is a syntactic entity that may be evaluated to determine its value.
Example expressions:
x + y
2 * (i + 1)
pow(x,2)Expressions combine values of variables to a new value.
And what are Boolean expressions?
If (A) Then
(B)
End IfBoolean expressions are expressions that evaluate to
either
true or false.
Example Boolean expressions:
x < 5
x >= y
x == y
x != yWhat does this count-controlled loop do?
for ( i=1; i<=100; i+=1){
print i;
}A brief summary of control flows:
Can you design an algorithm for one of the possible solutions?
e.g. “Choose a random direction if you hit a wall”.
move()turnLeft() and turnRight()canMove()visitedBefore()isExit()Does your algorithm…
The question of efficiency will be
an important topic
later in this course.
mirco.schoenfeld@uni-bayreuth.de
