Modellierung

Modellierung
Der Tübinger Parkplatz
Das Problem des Handlungsreisenden
Eine Formelsprache für Musik
Algorithmen und Datenstrukturen 1
Robert Giegerich
Faculty of Technology
Bielefeld University
[email protected]
Lecture, U. Bielefeld, Winter 2006/2007
Robert Giegerich
A&D 1 Vorlesung Winter 2006/2007
Bielefeld University
Modellierung
Der Tübinger Parkplatz
Das Problem des Handlungsreisenden
Eine Formelsprache für Musik
Was ist Informatik
Siehe Text von Kapitel 1
Robert Giegerich
A&D 1 Vorlesung Winter 2006/2007
Bielefeld University
Modellierung
Der Tübinger Parkplatz
Das Problem des Handlungsreisenden
Eine Formelsprache für Musik
Technische und Theoretische, Praktische und Angewandte
Informatik
Siehe Text von Kapitel 1
Robert Giegerich
A&D 1 Vorlesung Winter 2006/2007
Bielefeld University
Modellierung
Der Tübinger Parkplatz
Das Problem des Handlungsreisenden
Eine Formelsprache für Musik
Kapitel 2 Modellierung
In diesem Kapitel betrachten wir – ohne großen Formalismus –
einige Beispiele zu der zentralen Aufgabe der Informatik: die
Verwandlung von Problemen der realen Welt in Rechenaufgaben.
Wir werfen einen ersten Blick auf die Lösungswege und die
Schwierigkeiten verschiedenster Art, die sich hier auftun.
Robert Giegerich
A&D 1 Vorlesung Winter 2006/2007
Bielefeld University
Modellierung
Der Tübinger Parkplatz
Das Problem des Handlungsreisenden
Der Tübinger Parkplatz
Eine Formelsprache für Musik
(nach Klaeren/Sperber)
Auf einem Parkplatz der Uni Tübingen stehen Pkw und Motorräder
(ohne Beiwagen).
1 Wir zählen p Pkw und m Motorräder.
Wie viele Räder haben sie insgesamt?
Lösung: Wir bringen etwas Weltwissen ein –
1 Pkw
= 4 Räder
(1)
1 Motorrad
= 2 Räder
(2)
= 4p + 2m
(3)
Zahl der Räder:
r
Genauer betrachtet ist r eine Funktion von p und m:
r (p, m) = 4p + 2m.
(4)
Aufgabe 1 ist damit befriedigend gelöst.
Robert Giegerich
A&D 1 Vorlesung Winter 2006/2007
Bielefeld University
Modellierung
2
Der Tübinger Parkplatz
Das Problem des Handlungsreisenden
Eine Formelsprache für Musik
Wir erfahren, dass auf dem Parkplatz n Fahrzeuge mit
insgesamt r Rädern stehen.
Wieviele Pkw bzw. Motorräder stehen da?
Spontane Fragen:
Kann man das lösen?
Ist die Lösung eindeutig?
Inverses Problem zum vorigen – von r (p, m) sollen wir auf
p, m schließen. Das geht (nur) dank zusätzlicher Information
über die Zahl n der Fahrzeuge
r
= 4p + 2m
n = p+m
Robert Giegerich
A&D 1 Vorlesung Winter 2006/2007
(5)
(6)
Bielefeld University
Modellierung
Der Tübinger Parkplatz
Das Problem des Handlungsreisenden
Eine Formelsprache für Musik
Wir lösen (6) nach m auf und setzen in (5) ein
r
= 4p + 2(n − p)
(7)
und lösen nach p auf
r − 2n
2
r − 2n
m = n−
2
p =
(8)
(9)
Hier müssten wir eigentlich
p(n, r ) = . . .
m(n, r ) = . . .
schreiben.
Robert Giegerich
A&D 1 Vorlesung Winter 2006/2007
Bielefeld University
Modellierung
Der Tübinger Parkplatz
Das Problem des Handlungsreisenden
Eine Formelsprache für Musik
Haben wir nun eine allgemeine Lösung?
Für
n = 13, r = 46
erhalten wir
p = 10, m = 3
Jedoch gibt es auch Überraschungen ...
Robert Giegerich
A&D 1 Vorlesung Winter 2006/2007
Bielefeld University
Modellierung
Der Tübinger Parkplatz
Das Problem des Handlungsreisenden
Eine Formelsprache für Musik
Haben wir nun eine allgemeine Lösung?
Für
n = 13, r = 46
erhalten wir
p = 10, m = 3
Jedoch gibt es auch Überraschungen ...
n = 3,
r =9⇒
p = 1.5 , m = 1.5
n = 5,
p = −4,
=2⇒
m=9
n = 2,
p=3
r = 10 ⇒
m = −1
Robert Giegerich
A&D 1 Vorlesung Winter 2006/2007
halbe Autos und Motorräder?
neben 9 Motorrädern fehlen 4 Pkw?
mehr Autos als Fahrzeuge?
Bielefeld University
Modellierung
Der Tübinger Parkplatz
Das Problem des Handlungsreisenden
Eine Formelsprache für Musik
Hier gibt es also halbe Fahrzeuge, negative Motorräder und
gelegentlich mehr Pkw als Fahrzeuge insgesamt.
Wir müssen die Verwendung der Lösung einschränken:
n und r sind natürliche Zahlen
r ist gerade
2n ≤ r ≤ 4n
Minimale/maximale Räderzahl
Nur wenn die Eingabe diese Anforderung erfüllt, ist die Anwendung
unserer Formeln zulässig und das Ergebnis korrekt.
Robuste Programme überprüfen stets die Anforderungen an die
Eingabe, bevor sie damit rechnen.
Robert Giegerich
A&D 1 Vorlesung Winter 2006/2007
Bielefeld University
Modellierung
Der Tübinger Parkplatz
Das Problem des Handlungsreisenden
Eine Formelsprache für Musik
Das Problem des Handlungsreisenden
Ein Vertreter der Intelligent Design Bewegung will in
missionarischer Absicht 12 deutsche Elite-Universitäten besuchen.
Die Standorte und ihre Entfernungen (Straßenkilometer) sind in
Tabelle Dist angegeben, in der folgenden Beispieltour sieht man
ihre ungefähre Lage. Aber Vorsicht – Straßenkilometer sind keine
Entfernungen in Luftlinie.
Robert Giegerich
A&D 1 Vorlesung Winter 2006/2007
Bielefeld University
Modellierung
Der Tübinger Parkplatz
Das Problem des Handlungsreisenden
Eine Formelsprache für Musik
Tabelle der Entfernungen
AC
Aachen
Berlin
Bielefeld
Bremen
Freiburg
Hamburg
Köln
Leipzig
München
Münster
Nürnberg
Tübingen
B
633
BI
257
390
HB
378
412
175
FB
505
819
685
730
HH
488
284
262
119
759
K
70
569
191
312
435
422
L
585
179
437
362
659
391
515
M
648
584
598
753
412
782
578
425
MS
211
466
74
171
572
271
150
438
688
N
475
437
434
580
391
609
405
278
167
506
TÜ
446
634
492
640
207
668
376
589
220
502
207
Tabelle Dist: Entfernungen in Straßenkilometern
Robert Giegerich
A&D 1 Vorlesung Winter 2006/2007
Bielefeld University
Modellierung
Der Tübinger Parkplatz
Das Problem des Handlungsreisenden
Eine Rundtour
HB
378
MS
74
HH
Eine Formelsprache für Musik
284
119
B
BI
179
150
K
AC
L
70
278
685
N
167
TUE
207
FB
Robert Giegerich
A&D 1 Vorlesung Winter 2006/2007
220
M
Bielefeld University
Modellierung
Der Tübinger Parkplatz
Das Problem des Handlungsreisenden
Eine Formelsprache für Musik
Die Aufgabe
Sein Ziel ist: Eine Rundtour mit beliebigem Ausgangspunkt und
minimaler Gesamtstrecke. Jede Stadt darf nur einmal besucht
werden (weil der Vertreter sich nach seinem Auftritt an einer
Universität oft in dieser Stadt nicht mehr blicken lassen darf).
Robert Giegerich
A&D 1 Vorlesung Winter 2006/2007
Bielefeld University
Modellierung
Der Tübinger Parkplatz
Das Problem des Handlungsreisenden
Eine Formelsprache für Musik
Vorüberlegungen
Vorüberlegung 1:
Die Länge einer Rundtour bleibt gleich, wenn wir nur den
Start/Zielort ändern. Es ist also nicht nötig, einen besten
Startpunkt zu suchen.
Wir können eine Tour ebensogut immer in Aachen oder immer in
Bielefeld beginnen lassen.
Robert Giegerich
A&D 1 Vorlesung Winter 2006/2007
Bielefeld University
Modellierung
Der Tübinger Parkplatz
Das Problem des Handlungsreisenden
Eine Formelsprache für Musik
Vorüberlegung 2:
Wieviele verschiedene Rundtouren gibt es allgemein für n Städte?
Zahl der Permutationen p(n) = n ∗ (n − 1) ∗ . . . ∗ 1 = n!(10)
Zahl derTouren t(n) = p(n − 1)
(11)
Für 12 Städte t(12) = 39916800
(12)
Robert Giegerich
A&D 1 Vorlesung Winter 2006/2007
Bielefeld University
Modellierung
Der Tübinger Parkplatz
Das Problem des Handlungsreisenden
Eine Formelsprache für Musik
Notation
{}, {x1 , x2 , . . .}
[], [x1 , x2 , . . .]
x : xs
X
Dist
s
Robert Giegerich
A&D 1 Vorlesung Winter 2006/2007
Mengen von Elementen
Listen von Elelemten - hier spielen Anordnung und
Häufigkeit eine Rolle
Liste mit Anfangselement x und Restliste xs
gegebene Liste von Städten
Distanztabelle für X
beliebig gewählter Startpunkt aus X
Bielefeld University
Modellierung
Der Tübinger Parkplatz
Das Problem des Handlungsreisenden
Eine Formelsprache für Musik
Berechnung von Permutationen einer Menge
Die Permutationen einer Menge sind eine Menge von Listen:
perm {}
= {[ ]}
perm(X ) = {x : xs|x ∈ X , xs ∈ perm(X − {x})}
(13)
(14)
for X 6= {}
Robert Giegerich
A&D 1 Vorlesung Winter 2006/2007
Bielefeld University
Modellierung
Der Tübinger Parkplatz
Das Problem des Handlungsreisenden
Eine Formelsprache für Musik
Bewertung einer Rundtour
n−1
X
laenge [x1 , ..., xn ] = Dist(xn , x1 ) +
Dist(xi , xi+1 ) (15)
i=1
Die Gesamtstrecke ist einfach die Summe der einzelnen Abschnitte.
Robert Giegerich
A&D 1 Vorlesung Winter 2006/2007
Bielefeld University
Modellierung
Der Tübinger Parkplatz
Das Problem des Handlungsreisenden
Eine Formelsprache für Musik
Strategie 1: Erschöpfende Suche
Wir berechnen alle Rundtouren ausgehend von Startort s =
Bielefeld, bewerten sie und wählen die kürzeste:
tsp(X ) = argmint {laenge(s : t)|t ∈ perm(X − {s})} (16)
argmint bedeutet dasjenige t, das den Ausdruck laenge(t)
minimiert.
Robert Giegerich
A&D 1 Vorlesung Winter 2006/2007
Bielefeld University
Modellierung
Der Tübinger Parkplatz
Das Problem des Handlungsreisenden
Eine Formelsprache für Musik
Strategie 2 : Opportunistische Suche (Greedy)
Wir fahren von jedem Ort zum nächstgelegenen, der noch nicht
besucht wurde. Sei X die Menge der Städte und x1 , x2 , ... unsere
Route. Wir definieren einfach
greedy(a, {}) = [a]
(17)
greedy(a, X ) = a : greedy (z, X − {z})
(18)
wobei z = argminx {Dist(a, x)|x ∈ X }
tspgreedy (X ) = greedy(s, X − {s})
(19)
Hier bedeutet argminx dasjenige x, das den Ausdruck Dist(s, x)
minimiert. tspgreedy berechnent die opportunistische Lösung des
TSP-Problems.
Robert Giegerich
A&D 1 Vorlesung Winter 2006/2007
Bielefeld University
Modellierung
Der Tübinger Parkplatz
Das Problem des Handlungsreisenden
Eine Formelsprache für Musik
Exakte versus heuristische Lösung
Die von tsp berechnente Lösung ist exakt – wir finden garantiert
das Optimum. Der Aufwand ist allerdings hoch.
Die von tspgreedy berechnete Lösung ist heuristisch. Wir erhalten
mit wenig Aufwand eine Antwort, aber vermutlich ist dies nicht die
kürzeste Rundtour.
Eine spannende Frage wäre, wie oft diese Lösung wie nahe am
Optimum liegt . . .
Robert Giegerich
A&D 1 Vorlesung Winter 2006/2007
Bielefeld University
Modellierung
Der Tübinger Parkplatz
Das Problem des Handlungsreisenden
Eine Formelsprache für Musik
Ergebnisse der Strategien
Für unser Beispiel erhalten wir:
Die opportunistische Strategie ab Bielefeld liefert die in der
Karte eingetragene Rundtour. Sie ist 2690 km lang und nicht
optimal.
Von Bielefeld erst nach Bremen, das wäre besser ausgegangen!
In Aachen anfangend, hätte das opportunistische Verfahren
vermutlich eine bessere Tour gefunden.
Die erschöpfende Suche wird in den Übungen implementiert
werden.
Robert Giegerich
A&D 1 Vorlesung Winter 2006/2007
Bielefeld University
Modellierung
Der Tübinger Parkplatz
Das Problem des Handlungsreisenden
Eine Formelsprache für Musik
Abschätzung des Rechenaufwands
Wir betrachten die Anzahl der berechnenten Routen, und die
Berechnung einer Entfernungssumme für n Städte:
Strategie 1 braucht etwa (n − 1)! ∗ n = n! Rechenschritte.
Strategie 2 braucht etwa n2 Rechenschritte.
Robert Giegerich
A&D 1 Vorlesung Winter 2006/2007
Bielefeld University
Modellierung
Der Tübinger Parkplatz
Das Problem des Handlungsreisenden
Eine Formelsprache für Musik
Erste Begegnung mit dem praktisch Unmöglichen
Unser Problem ist unter dem Namen “Traveling Salesman
Problem” (TSP) bekannt; es ist eines der meist untersuchten
Probleme der Informatik.
Man kennt keinen Algorithmus, der das optimale Ergebnis
mit einer (in n) polynomialen Anzahl von Rechenschritten
bestimmt.
Die bekannten Algorithmen haben entweder exponentiellen
Aufwand (wie Strategie 1), oder finden nur eine
Näherungelösung (wie Strategie 2).
Verfahren mit exponentiellem Aufwand nennt man “nicht
praktikabel”.
Für Informatiker sind solche Probleme eine besonders
interessante Herausforderung.
Robert Giegerich
A&D 1 Vorlesung Winter 2006/2007
Bielefeld University
Modellierung
Der Tübinger Parkplatz
Das Problem des Handlungsreisenden
Eine Formelsprache für Musik
Hegel über die Musik
“Zwar bedarf in dieser Beziehung die eine Kunst mehr als die andere des
Bewusstseins und der Erkenntnis solchen Gehaltes. Die Musik z.B., welche es
sich nur mit der ganz unbestimmten Bewegung des geistigen Innern, mit dem
Tönen gleichsam der gedankenlosen Empfindung zu tun macht, hat wenigen
oder keinen geistigen Stoff im Bewusstsein vonnöten. Das musikalische Talent
kündigt sich darum auch am meisten in sehr früher Jugend, bei noch leerem
Kopfe und wenig bewegtem Gemüte an und kann beizeiten schon, ehe noch
Geist und Leben sich erfahren haben, zu sehr bedeutender Höhe gelangt sein;
wie wir denn auch oft genug eine sehr große Virtuosität in musikalischer
Komposition und Vortrage neben bedeutender Dürftigkeit des Geistes und
Charakters bestehen sehen.”
Hegel, Aesthetik, Abschnitt: Das Kunstwerk als Produkt menschlicher
Tätigkeit (siehe auch http://www.textlog.de/3642-2.html)
Robert Giegerich
A&D 1 Vorlesung Winter 2006/2007
Bielefeld University
Modellierung
Der Tübinger Parkplatz
Das Problem des Handlungsreisenden
Eine Formelsprache für Musik
Musik als formales System
Hegel zeichnet sich hier als Wissenschaftler (und nicht als
Musikliebhaber) aus, indem er an die Stelle des begriffslosen Staunens
(“Wunderkind”) ein Moment der Erklärung setzt.
Er verweist darauf, dass, musikalisches Talent vorausgesetzt, wenig
weiteres Wissen dazugehört, um dieses Talent zu entwickeln.
Ganz im Unterschied zu einem Physiker oder Schriftsteller . . .
Wir machen uns den formalen Charakter der Musik zu Nutze. Die
Modellierung haben hier schon andere erledigt . . .
Robert Giegerich
A&D 1 Vorlesung Winter 2006/2007
Bielefeld University
Modellierung
Der Tübinger Parkplatz
Das Problem des Handlungsreisenden
Eine Formelsprache für Musik
Formeln für Musik
Die Musik ist weitgehend ein formales System aufgrund der
Harmoniegesetze. Deshalb gibt es längst eine Programmiersprache
für Musik - die Notenschrift. Allerdings ist sie eher eine
zweidimensionale Bilderschrift und nicht so gut für die Behandlung
durch Computer geeignet. Wir zeigen, wie man Musikstücke
einfach als Datenstrukturen darstellen kann, in Gestalt einer
Formelsprache für Musik.
Formel = Datenstruktur? Ja genau – das ist das konkrete
Material, mit dem man rechnet und auch rechnen lässt!
Robert Giegerich
A&D 1 Vorlesung Winter 2006/2007
Bielefeld University
Modellierung
Der Tübinger Parkplatz
Das Problem des Handlungsreisenden
Eine Formelsprache für Musik
Wir führen Namen ein für die 12 Tonstufen der Tonleiter:
Ce, Cis, De, Dis, Eh, Ff , Fis, Ge, Gis, Ah, Ais, Ha;
(20)
Jeder Ton und damit jede Note hat eine Tonstufe und eine Dauer.
Die Dauer messen wir in Taktanteilen, und schreiben sie als
Brüche, etwa
1/1, 1/2, 1/4, 1/16 usw.
Robert Giegerich
A&D 1 Vorlesung Winter 2006/2007
(21)
Bielefeld University
Modellierung
Der Tübinger Parkplatz
Das Problem des Handlungsreisenden
Eine Formelsprache für Musik
Die kleinsten Musikstücke sind einzelne Noten und Pausen. Wir
schreiben Noten als
N(Ce, 1/2), N(Fis, 1/16), allgemein N(t, d)
(22)
und Pausen als
P(1/1), P(1/2), P(1/4), allgemein P(d)
(23)
worin t für eine beliebige Tonstufe steht, und d für eine beliebige
Dauer.
Robert Giegerich
A&D 1 Vorlesung Winter 2006/2007
Bielefeld University
Modellierung
Der Tübinger Parkplatz
Das Problem des Handlungsreisenden
Eine Formelsprache für Musik
Konstruktoren
Die Symbole N und P dienen dazu, aus kleineren Komponenten
Formeln für Noten und Pausen aufzubauen. Man kann sie als
Funktionen sehen, die gegeben Tonstufe t und Dauer d, die Note
N(t, d) ergeben. Deshalb werden sie wie Funktionen geschrieben Name vorne und Klammer um die Argumente. Andererseits
berechnen diese Funktionen nicht wirklich etwas - diese von ihnen
gebildeten Formeln sind ihr eigenes Ergebnis, mithin
Daten(strukturen). Deshalb nennt man solche Funktionen
Konstruktoren.
Konvention: Konstruktoren fangen mit Großbuchstaben an, andere
“richtige” Funktionen mit Kleinbuchstaben.
Robert Giegerich
A&D 1 Vorlesung Winter 2006/2007
Bielefeld University
Modellierung
Der Tübinger Parkplatz
Das Problem des Handlungsreisenden
Eine Formelsprache für Musik
Verknüpfungen von Musikstücken
Um aus einzelnen Noten größere Musikstücke machen zu können,
müssen wir sie miteinander verknüpfen: Nacheinander sowieso,
aber auch gleichzeitig für mehrstimmige Stücke. Wir verwenden
Konstruktoren Dann und Zugleich. Hier eine Folge von drei Noten,
und ein C-Dur-Dreiklang:
Dann(N(Ce, 1/4), Dann(N(De, 1/4), N(Eh, 1/4)))
(24)
Zugleich(N(Ce, 1/4), Zugleich(N(Eh, 1/4), N(Ge, 1/4)))
(25)
Ziemlich unleserlich – für uns. Etwa so wie Plus(1, Plus(2, 3))
statt 1 + 2 + 3.
Robert Giegerich
A&D 1 Vorlesung Winter 2006/2007
Bielefeld University
Modellierung
Der Tübinger Parkplatz
Das Problem des Handlungsreisenden
Eine Formelsprache für Musik
Infix-Schreibweise
Wir benennen Dann um in * und Zugleich in + und erlauben uns,
sie in Infix-Schreibweise zu benutzen:
N(Ce, 1/4)*N(De, 1/4)*N(Eh, 1/4)
(26)
N(Ce, 1/4)+N(Eh, 1/4)+N(Ge, 1/4)
(27)
Dabei sollen für * und + die üblichen Klammer-Regeln gelten (a la
Punkt vor Strichrechnung), zum Beispiel
x*y +z = (x*y )+z
(28)
Darin sind x, y , z beliebige Musikstücke.
Robert Giegerich
A&D 1 Vorlesung Winter 2006/2007
Bielefeld University
Modellierung
Der Tübinger Parkplatz
Das Problem des Handlungsreisenden
Eine Formelsprache für Musik
Wiederholungszeichen: Konstruktor oder Funktion?
Oft werden musikalische Phrasen wiederholt. Wir führen den
Konstruktor Wdh ein
Wdh(m) Musikstück m in Wiederholungsklammern
(29)
Andereseits kommt dadurch nichts in die Modellwelt, was wir nicht
schon schreiben können, nämlich als m*m. Wir können auch
einfach statt des Konstruktors Wdh eine “richtige”Funktion
definieren:
wdh(m) = m*m
(30)
Generell will man nicht unnötig viele Konstruktoren einführen, um
die Modellwelt einfach zu halten.
Robert Giegerich
A&D 1 Vorlesung Winter 2006/2007
Bielefeld University
Modellierung
Der Tübinger Parkplatz
Das Problem des Handlungsreisenden
Eine Formelsprache für Musik
Bruder Jakob
Wir schreiben nun einen Kanon auf. Wir fangen mit den einzelnen
Phrasen an, denen wir beliebige, aber “sprechende” Namen geben:
bruderjakob
=
N(Ce, 1/4)*N(De, 1/4)*N(Eh, 1/4)
(31)
*N(Ce, 1/4)
schlaefstdunoch
=
N(Eh, 1/4)*N(Ff , 1/4)*N(Ge, 1/2)
(32)
hoerstdunicht
=
N(Ge, 1/8)*N(Ah, 1/8)*N(Ge, 1/8)
(33)
=
*N(Ff , 1/8)*N(Eh, 1/4)*N(Ce, 1/4)
=
N(Ce, 1/4)*N(Gg , 1/4)*N(Ce, 1/2)
dingdingdong
(34)
Dabei haben wir einen neuen Tonstufenkonstruktor Gg für das Ge
eine Oktave tiefer erfunden. Das ist natürlich keine gute Lösung für
das Problem, dass die Tonstufen sich in jeder Oktave wiederholen.
Beachte: Alle Phrasen sind genau einen Takt lang.
Robert Giegerich
A&D 1 Vorlesung Winter 2006/2007
Bielefeld University
Modellierung
Der Tübinger Parkplatz
Das Problem des Handlungsreisenden
Eine Formelsprache für Musik
In einer Strophe werden alle Phrasen wiederholt:
(35)
strophe = wdh(bruderjakob)*wdh(schlaefstdunoch)
*wdh(hoerstdunicht)*wdh(dingdingdong )
Wie gut, dass wir die Namen eingeführt haben. So behalten wir
die Übersicht. Mittels der Definition von wdh kann man (wir oder
der Computer) die strophe in allen Details ausrechnen.
Robert Giegerich
A&D 1 Vorlesung Winter 2006/2007
Bielefeld University
Modellierung
Der Tübinger Parkplatz
Das Problem des Handlungsreisenden
Eine Formelsprache für Musik
Was heißt Rechnen in der Formelwelt?
1
Wir haben Daten, dargestellt durch Konstruktorformeln.
2
Wir haben Funktionen, definiert durch Gleichungen.
3
Wir haben gemischte Formeln (aus Funktionen und
Konstruktoren), die ausgerechnet werden können.
4
Ein Rechenschritt ist das Anwenden einer definierenden
Gleichung von links nach rechts, irgendwo in der Formel.
5
Ausrechnen einer gemischten Formel heißt, so lange rechnen,
bis keine Gleichung mehr anwendbar ist. Dann ist die Formel
in Normalform.
Dazu ein paar Anmerkungen:
Robert Giegerich
A&D 1 Vorlesung Winter 2006/2007
Bielefeld University
Modellierung
Der Tübinger Parkplatz
Das Problem des Handlungsreisenden
Eine Formelsprache für Musik
1
Die Formeln können beliebig groß sein - eine Formel, die 1MB
groß ist, macht dem Computer nichts aus.
2
Zu den Funktionen gehören auch Konstanten als Spezialfall –
das sind einfach Funktionen ohne Argument.
3
Enthält eine Formel keine definierten Funktionen, so ist sie
schon in Normalform und es gibt nichts Auszurechnen.
4
“Ausrechnen” ist nun genau definiert. Wir dürfen beim
Ausrechnen nichts anderes verwenden als die Gleichungen,
und auch die nur von links nach rechts. Wir werden auch
schon mal andere Rechenschritte machen, aber der Rechner
darf das nicht. Eigentlich ist er ein Aus-rechner.
5
Manchmal endet das Ausrechnen bei einer gemischten Formel,
wenn keine der gegebenen Gleichungen passt. Normalerweise
ist das ein Fehler.
Robert Giegerich
A&D 1 Vorlesung Winter 2006/2007
Bielefeld University
Modellierung
Der Tübinger Parkplatz
Das Problem des Handlungsreisenden
Eine Formelsprache für Musik
Weiter mit dem Kanon ...
Wer auf seinen Einsatz wartet, hat Pausen. Dafür erlauben wir
auch Pausen, die länger sind als ein Takt.
spaeter (d, m) = P(d)*m
stimme2 = spaeter (2/1, strophe)
mal(1, m) = m
(36)
(37)
(38)
mal(n + 1, m) = m ∗ mal(n, m)
(39)
ad libidum(m) = m ∗ ad libidum(m)
(40)
Die 2. Stimme setzt nach zwei Takten Pause ein.
Mehrfaches Wiederholen durch mal. n ist die Anzahl, m das zu
wiederholende Musikstück.
ad libidum(m) ist ein unendlich langes Musikstück.
Robert Giegerich
A&D 1 Vorlesung Winter 2006/2007
Bielefeld University
Modellierung
Der Tübinger Parkplatz
Das Problem des Handlungsreisenden
Eine Formelsprache für Musik
Modellwelt versus modellierte Welt
Aufgabe: Beweise, dass in der Formelwelt gilt
mal(4, m) = wdh(wdh(m))
(41)
Versuch 1 (Wirkliche Welt)
mal(4, m) ist vierfache Wiederholung von m, wdh(wdh(m)) ist
einfache Wiederholung des einfach wiederholten m.
4 = 2 ∗ 2, also gilt die Aussage.
Robert Giegerich
A&D 1 Vorlesung Winter 2006/2007
Bielefeld University
Modellierung
Der Tübinger Parkplatz
Das Problem des Handlungsreisenden
Eine Formelsprache für Musik
Modellwelt versus modellierte Welt
Aufgabe: Beweise, dass in der Formelwelt gilt
mal(4, m) = wdh(wdh(m))
(41)
Versuch 1 (Wirkliche Welt)
mal(4, m) ist vierfache Wiederholung von m, wdh(wdh(m)) ist
einfache Wiederholung des einfach wiederholten m.
4 = 2 ∗ 2, also gilt die Aussage.
Versuch 2 (Modellwelt)
Wir rechnen aus:
mal(4, m) ⇒ m ∗ mal(3, m) ⇒ m ∗ (m ∗ mal(2, m)) ⇒
m ∗ (m ∗ (m ∗ mal(1, m)) = m ∗ (m ∗ (m ∗ m))
wdh(wdh(m)) ⇒ wdh(m ∗ m) ⇒ (m ∗ m) ∗ (m ∗ m)
Die beiden Ergebnisse bedeuten das gleiche, sind aber nicht (als
Formel) gleich!
Robert Giegerich
A&D 1 Vorlesung Winter 2006/2007
Bielefeld University
Modellierung
Der Tübinger Parkplatz
Das Problem des Handlungsreisenden
Eine Formelsprache für Musik
Vier Stimmen mit verzögertem Einsatz
kanonBJ = ad libidum(strophe)+
(42)
= spaeter (2, ad libidum(strophe))+
= spaeter (4, ad libidum(strophe))+
= spaeter (6, ad libidum(strophe))
Robert Giegerich
A&D 1 Vorlesung Winter 2006/2007
Bielefeld University
Modellierung
Der Tübinger Parkplatz
Das Problem des Handlungsreisenden
Eine Formelsprache für Musik
Fazit zur Modellierung durch Formelwelten
1
Auch komplizierte strukturierte Objekte der Realwelt lassen
sich gut durch Formeln repräsentieren.
2
Wichtig ist hier die geschickte Auswahl der Konstruktoren, bei
denen es immer verschiedene Möglichkeiten gibt
3
Im Idealfall existiert eine bijektive Abbildung zwischen
Konstruktorformeln und Realweltobjekten.
4
Der Idealfall ist selten.
5
In der Formelwelt gelten erst einmal nur die Gesetze, die durch
die Gleichungen für die definierten Funktionen gegeben sind.
6
Ob das Modell (die Formelwelt mit ihren Funktionen ) weitere
Eigenschaften der realen Welt korrekt wiederspiegelt, muss
bewiesen werden.
Robert Giegerich
A&D 1 Vorlesung Winter 2006/2007
Bielefeld University
Modellierung
Der Tübinger Parkplatz
Das Problem des Handlungsreisenden
Eine Formelsprache für Musik
Algorithmusbegriff
Ein Algorithmus ist eine Rechenvorschrift, die so genau beschrieben
ist, dass sie von einem Automaten ausgeführt werden kann.
Konsequenz:
Das gilt für eine Folge von Maschinenbefehlen für den Pentium
Prozessor ebenso für unseren Kanon canonBJ. Der Automat wäre
hier eine Gleichungsanwendungsmaschine (die selbst wieder durch
Pentium-Instruktionen realisiert sein kann).
Auf die Abstraktionsebene der Beschreibung eines Algorithmus
kommt es wesentlich an für uns, die Entwickler von Algorithmen,
aber nicht für den Algorithmusbegriff selbst.
Robert Giegerich
A&D 1 Vorlesung Winter 2006/2007
Bielefeld University
Modellierung
Der Tübinger Parkplatz
Das Problem des Handlungsreisenden
Eine Formelsprache für Musik
Erste Begegnung mit der Unendlichkeit
Es ist einfach, Formeln zu definieren, die unendlich groß sind,
wie etwa ad libidum(strophe).
Mit den gegebenen Definitionen können wir eine solche Formel
soweit ausrechnen, wie wir wollen. Dann hören wir damit auf.
Vgl. Kapitel 1: Selbst wenn wir unseren Verstand als
(Aus)rechner benutzen, haben wir einen Begriff von unserem
Tun, und können den Rechenprozess beobachten, eventuell
abkürzen, oder innehalten.
Der Rechner weiss nicht, dass er rechnet. Verstricken wir ihn
in eine unendliche Berechnung, muss diese von aussen
abgebrochen werden.
Unentscheidbarkeit des Halteproblems: Es gibt keinen
allgemeinen Algorithmus, der vorab feststellt, ob eine
Rechnung terminiert oder in sich ins Unendliche fortsetzt.
Robert Giegerich
A&D 1 Vorlesung Winter 2006/2007
Bielefeld University

Download Report