Einfuehrung Flashcards
Definition of an algorithm (general)
An algorithm is a precise and finite description of a process consisting of elementary steps
Usually we also want: “and (c) solves a given problem”
– But algorithms can be wrong …
Definition of an algorithm (computer science)
An algorithm is a precise and finite description of a
computational process that is (a) given in a formal
language and (b) consists of elementary and machineexecutable steps
Euclidean Algorithm
Recipe: Given two integers a, b. As long as neither a nor b is 0, take the smaller of both and subtract it from the greater. If this yields 0, return the other number
Euclidean Algorithm - proof ?
- Assume our function “euclid” returns x
- We write “b|a” if (a mod b)=0
– We say: “b teilt a” - We define x|0 for any x
- Note: if c|a and c|b and a>b ⇒ c|(a-b)
- We prove the claim in two steps
– We show that x is a common divisor
– We prove that no greater common divisor
can exis
Algorithm properties
terminating?
An algorithm is called terminating if it stops after a finite number of steps for every finite input.
– We so-far required that the algorithm (specification) is finite; here we require that the time for execution is finit
Algorithm properties
deterministic?
deterministic if it always performs the same series of steps given the same input
Exemplary questions
- Give a definition of the concept “algorithm”
Exemplary questions
- What different types of complexity exist?
Exemplary questions
- Given the following algorithm …, analyze its worst-case
time complexity
Exemplary questions
- The following algorithm … uses a double-linked list as basic
set data structure. Replace this with an arra
Exemplary questions
- When do we say an algorithm is optimal for a given
problem?
Exemplary questions
- How does the complexity of an algorithm depend on (a) the data structures it uses and (b) the complexity of the problem it solves?
What is a data structure
- Algorithms work on input data, generate intermediate data,
and finally produce result data - A data structure is the way how “data” is represented
inside the machine
– In memory or on disc (see Database course) - Data structures determine what algs may do at what cost
– More precisely: … what a specific step of an algorithm costs - Complexity of algorithms is tightly bound to the data
structures they use
– So tightly that one often subsumes both concepts under the term
“algorithm”
Wie wurde die Doppelhelix gefunden?
Biophysikalische Daten
Biophysikalische Daten (Linus Pauling) –
es gibt mehrere Stränge (erste Vermutungen: 3)
Wie wurde die Doppelhelix gefunden?
Roentgenkristallografie
Roentgenkristallografie – helikale Struktur
(Rosalind Franklin)
