3. Množiny v Pythonu¶

3.1. Konečné a nekonečné množiny¶

S konečnými množinami můžeme v Pythonu pracovat snadno:

Co ale když chceme pracovat s nekonečnými množinami, např. množinou všech prvočísel? Existují tři základní přístupy, jak pracovat s nekonečnými množinami. První možností je rozhodující funkce, která rozhoduje příslušnost do množiny (tj. funkce, která pro zadaný prvek rozhodne, zda do množiny patří, nebo nepatří). Druhou možností je numerující funkce, která vrací prvky dané množiny (a její obor hodnot je celá množina). Třetí možností je generátor množiny (něco jako funkce, která postupně generuje tolik prvků množiny, o kolik si jich řekneme).

3.2. Charakteristická funkce množiny¶

Pokud je množina rekurzivní, můžeme naprogramovat její charakteristickou funkci. Charakteristická funkce rozhoduje příslušnost do množiny, tj. vrací True (příp. 1), pokud prvek na vstupu do množiny patří, a False (příp. 0), pokud prvek do množiny nepatří. Příkladem může být následující charakteristická funkce množiny všech sudých čísel.

Pro nerekurzivní RE množiny není jejich charakteristická funkce totálně vyčíslitelná. Můžeme však naprogramovat funkci pro částečné rozhodování příslušnosti do množiny, která např. vrací True vždy, pokud prvek do množiny patří a pokud prvek do množiny nepatří, tak buď vrátí False nebo cyklí. (Jinou možností by bylo, že zastaví právě tehdy, když prvek do množiny patří, tj. definiční obor této funkce by byla příslušná množina).

3.3. Numerující funkce¶

Pro všechny rekurzivně spočetné množiny (kromě prázdné množiny) můžeme napsat jejich numerující funkci, tedy TVF, jejímž oborem hodnot je příslušná množina. Například numerující funkce pro množinu všech Fibonacciho čísel může vypadat takto:

3.4. Generátory množin¶

Generátor množiny je podobný funkci, liší se však tím, že nevrací jednu hodnotu pomocí return, ale postupně libovolné (klidně nekonečné) množství hodnot příkazem yield (podobně jako příkaz output z přednášky).

Generátor můžeme napsat pro libovolnou RE množinu, pro nerekurzivní se nám však nepodaří, aby generoval čísla v rostoucím pořádku. Pokud máme generátor nějaké množiny, můžeme jednoduše napsat numerující funkci množiny (pro vstup n budeme vracet n-tý prvek generované posloupnosti).