Vorlesung 2 Seidl

Aus ProgrammingWiki

Inhaltsverzeichnis 1 Prinzipiell Unlösbares S. 5 2 Abzählbar unendliche Menge S. 6 3 S. 7 4 R ist eine überabzählbar unendliche Menge S. 11 5 Kreativaufgabe: Der Hilbertbus S. 17 6 Mit Generatoren

Prinzipiell Unlösbares S. 5

Nicht formalisierbare "Fragestellungen", also etwas das sich nicht in eine Abfolge von Berechnungen fassen lässt:
- Wie ist die Stimmung einer Person (fehlen von Informationen um das herauszufinden)

Praktisch Unmögliches (wg. Effizienz):
- Alle Primzahlen zu "berechnen" (da unendlich viele, Algorithmus würde nie terminieren)
- Wie wird das Wetter am heutigen Tag in 100 Jahren

Abzählbar unendliche Menge S. 6

S. 7

def f(n): if n == 1: return 1 if n % 2 == 0: return f(n / 2) + 1 else: return 1 / (f(n - 1))

print(f(3))

ausführen

Mit memoizing:

saved_function_values = {} def f(n): if n == 1: return 1 if n % 2 == 0: if n / 2 in saved_function_values: value = saved_function_values.get(n / 2) print("benutze gecachten wert!") else: value = f(n / 2) saved_function_values[n / 2] = value return value + 1 else: if n - 1 in saved_function_values: value = saved_function_values.get(n - 1) print("benutze gecachten wert!") else: value = f(n - 1) saved_function_values[n - 1] = value return 1 / value

max_n = 7 for n in range(1, max_n + 1): print(f(n))

ausführen

R ist eine überabzählbar unendliche Menge S. 11

Kreativaufgabe: Der Hilbertbus S. 17

# Baue Hotel raum_gast_zuordnung = {} # Einzelbuchung def book_gast(zimmer_nr, attribut): if zimmer_nr in raum_gast_zuordnung: print("Zimmer " + str(zimmer_nr) + " bereits gebucht!") return raum_gast_zuordnung[zimmer_nr] = attribut print(str(attribut) + " in Zimmer " + str(zimmer_nr) + " gebucht!") # Konstruktion eines Busses mit einer endlichen Anzahl an Personen def baue_kleinbus(bus_nr, anzahl_personen): kleinbus = [] for person in range(0, anzahl_personen + 1, 1): kleinbus.append([bus_nr, person]) return kleinbus # Buchung von mehreren Gästen auf einmal (z.B. Bus) def gruppenbuchung(bus): for i in range(0, max(raum_gast_zuordnung) + len(bus) + 1, 1): if i > len(bus) - 1: break if i in raum_gast_zuordnung: buche_gruppe_in_naechste_freie_raeume(i, raum_gast_zuordnung, bus, i) else: raum_gast_zuordnung[i] = bus[i] # Gehe durch Raum-Gast Zuordnungstabelle und buche Gäste aufsteigend in freie Räume def buche_gruppe_in_naechste_freie_raeume(i, raum_gast_zuordnung, bus, bus_i): if i in raum_gast_zuordnung: i += 1 buche_gruppe_in_naechste_freie_raeume(i, raum_gast_zuordnung, bus, bus_i) else: raum_gast_zuordnung[i] = bus[bus_i] # Alle Gäste des Hotels umziehen in Raum 2*n def move_gaeste_n_2n(raum_gast_zuordnung): zwei_n_raum_gast_zuordnung = {} for raum in raum_gast_zuordnung: zwei_n_raum_gast_zuordnung[2*raum] = raum_gast_zuordnung.get(raum) return zwei_n_raum_gast_zuordnung # Cantor Diagonalisierung def diagonalisierung(pb): # Person + 1 pb[0] = pb[0] + 1 add_diagonalisierungs_gast(pb[0], pb[1]) # Herunterzählen der Person bis 1 for person_next in range(pb[0] - 1, 0, -1): pb[1] = pb[1] + 1 pb[0] = person_next add_diagonalisierungs_gast(pb[0], pb[1]) pb[1] = pb[1] + 1 add_diagonalisierungs_gast(pb[0], pb[1]) # Hochzählen for person_next in range(pb[0] + 1, pb[1] + 1): pb[1] = pb[1] - 1 pb[0] = person_next add_diagonalisierungs_gast(pb[0], pb[1]) if len(pb_list) >= max_gaeste: return diagonalisierung(pb) def add_diagonalisierungs_gast(person, bus): pb_list.append([person, bus]) gaeste = len(pb_list) - 1 raum_gast_zuordnung_macrohard[gaeste] = [person, bus]

# Einzelbuchungen book_gast(3, "Herr Grundmann") book_gast(2, "Frau Milkel") book_gast(3, "Herr Wuischke") book_gast(7, "Herr Wuischke") # Kleinbus 815 kleinbus = baue_kleinbus(815, 8) gruppenbuchung(kleinbus) # Bus 3813 bus_3813 = baue_kleinbus(3813, 300) # Unendlich, hier begrenzt auf 300 Personen gruppenbuchung(bus_3813) # Hotelgäste umziehen raum_gast_zuordnung = move_gaeste_n_2n(raum_gast_zuordnung) # Bus 33 bus_33 = baue_kleinbus(33, 300) # Unendlich, hier begrenzt auf 300 Personen gruppenbuchung(bus_33) # Hotelgäste umziehen raum_gast_zuordnung = move_gaeste_n_2n(raum_gast_zuordnung) # Macrohard Bus raum_gast_zuordnung_macrohard = {} pb_list = [] max_gaeste = 300 # Erste Runde # pb = [person, bus] pb = [1, 1] add_diagonalisierungs_gast(pb[0], pb[1]) diagonalisierung(pb) gruppenbuchung(list(raum_gast_zuordnung_macrohard.values())) print(raum_gast_zuordnung.get(234))

ausführen

Mit Generatoren

import types max_gaeste = 500 # Baue Hotel raum_gast_zuordnung = {} # Einzelbuchung def book_gast(zimmer_nr, attribut): if zimmer_nr in raum_gast_zuordnung: print("Zimmer " + str(zimmer_nr) + " bereits gebucht!") return raum_gast_zuordnung[zimmer_nr] = attribut print(str(attribut) + " in Zimmer " + str(zimmer_nr) + " gebucht!") # Konstruktion eines Busses mit einer endlichen Anzahl an Personen def baue_kleinbus(bus_nr, anzahl_personen): kleinbus = [] for person in range(0, anzahl_personen + 1, 1): kleinbus.append([bus_nr, person]) return kleinbus # Konstruktion eines Busses mit einer unendlichen Anzahl an Personen def baue_unendlichen_bus(bus_nr): person = 0 while True: yield [bus_nr, person] person += 1 if person == max_gaeste: break # Buchung von mehreren Gästen auf einmal (z.B. Bus) def gruppenbuchung(bus): # Wenn unendlicher Bus if isinstance(bus, types.GeneratorType): for i, person in enumerate(bus): if i in raum_gast_zuordnung: buche_unendliche_gruppe_in_naechste_freie_raeume(i, raum_gast_zuordnung, person) else: raum_gast_zuordnung[i] = person # Wenn endlicher Bus else: for i in range(0, max(raum_gast_zuordnung) + len(bus) + 1, 1): if i > len(bus) - 1: break if i in raum_gast_zuordnung: buche_gruppe_in_naechste_freie_raeume(i, raum_gast_zuordnung, bus, i) else: raum_gast_zuordnung[i] = bus[i] # Gehe durch Raum-Gast Zuordnungstabelle und buche Gäste aufsteigend in freie Räume def buche_gruppe_in_naechste_freie_raeume(i, raum_gast_zuordnung, bus, bus_i): if i in raum_gast_zuordnung: i += 1 buche_gruppe_in_naechste_freie_raeume(i, raum_gast_zuordnung, bus, bus_i) else: raum_gast_zuordnung[i] = bus[bus_i] def buche_unendliche_gruppe_in_naechste_freie_raeume(i, raum_gast_zuordnung, person): if i in raum_gast_zuordnung: i += 1 buche_unendliche_gruppe_in_naechste_freie_raeume(i, raum_gast_zuordnung, person) else: raum_gast_zuordnung[i] = person # Alle Gäste des Hotels umziehen in Raum 2*n def move_gaeste_n_2n(raum_gast_zuordnung): zwei_n_raum_gast_zuordnung = {} for raum in raum_gast_zuordnung: zwei_n_raum_gast_zuordnung[2*raum] = raum_gast_zuordnung.get(raum) return zwei_n_raum_gast_zuordnung # Cantor Diagonalisierung def diagonalisierung(pb): while True: # Person + 1 pb[0] = pb[0] + 1 yield [pb[0], pb[1]] # Herunterzählen der Person bis 1 for person_next in range(pb[0] - 1, 0, -1): pb[1] = pb[1] + 1 pb[0] = person_next yield [pb[0], pb[1]] pb[1] = pb[1] + 1 yield [pb[0], pb[1]] # Hochzählen for person_next in range(pb[0] + 1, pb[1] + 1): pb[1] = pb[1] - 1 pb[0] = person_next yield [pb[0], pb[1]] def add_diagonalisierungs_gast(person, bus): pb_list.append([person, bus]) gaeste = len(pb_list) - 1 raum_gast_zuordnung_macrohard[gaeste] = [person, bus]

# Einzelbuchungen book_gast(3, "Herr Grundmann") book_gast(2, "Frau Milkel") book_gast(3, "Herr Wuischke") book_gast(7, "Herr Wuischke") # Kleinbus 815 kleinbus = baue_kleinbus(815, 8) gruppenbuchung(kleinbus) # Bus 3813 bus_3813 = baue_unendlichen_bus(3813) gruppenbuchung(bus_3813) # Hotelgäste umziehen raum_gast_zuordnung = move_gaeste_n_2n(raum_gast_zuordnung) # Bus 33 bus_33 = baue_unendlichen_bus(33) gruppenbuchung(bus_33) # Hotelgäste umziehen raum_gast_zuordnung = move_gaeste_n_2n(raum_gast_zuordnung) # Macrohard Bus raum_gast_zuordnung_macrohard = {} pb_list = [] pb = [1, 1] add_diagonalisierungs_gast(pb[0], pb[1]) count = 0 for d in diagonalisierung(pb): count += 1 add_diagonalisierungs_gast(d[0], d[1]) if count > max_gaeste: break gruppenbuchung(list(raum_gast_zuordnung_macrohard.values())) print(raum_gast_zuordnung.get(234))

ausführen