BuK/IIm20/Vorlesung 2 Seidl

Wiki-Quelltext dieser Seite.

<language>Python</language>
=== Prinzipiell Unlösbares S. 5 ===

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

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

<br/><br/>

=== Abzählbar unendliche Menge S. 6 ===
[[Bild:Fseidl_15311.jpg]]

=== S. 7 ===
[[Bild:Fseidl_15311_(copy).jpg]]

<code id="605f695e0a6c7">
def f(n):
    if n == 1:
        return 1
    
    if n % 2 == 0:
        return f(n / 2) + 1
    else:
        return 1 / (f(n - 1))
</code>
<run id="605f695e0a750">
print(f(3))
</run>

Mit memoizing:
<code id="605f70abeb6cf">
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
</code>

<run id="605f70abeb731">
max_n = 7
for n in range(1, max_n + 1):
    print(f(n))
</run>


=== R ist eine überabzählbar unendliche Menge S. 11 ===
[[Bild:Fseidl_15721.jpg]]


=== Kreativaufgabe: Der Hilbertbus S. 17 ===
<code id="606090ac3eb2a">
# 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]
</code>

<run id="606090ac3eb99">
# 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))
</run>

=== Mit Generatoren ===
<code id="60d04c32578b8">
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]
</code>
<run id="60d04c325797b">
# 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))
</run>