BuK/IIm20/Vorlesung 3 Nerlich

Wiki-Quelltext dieser Seite.

<language>Python</language>
=== S.9 ===

<code id="6073186d90b37">
#/usr/bin/env python3

from random import Random


class WordGenerator:
	"""docstring for WordGenerator"""
	def __init__(self, alphabet: set):
		if not alphabet.isdisjoint({None}):
			raise ValueError("The alphabet cannot contain None")
		
		self._alphabet = frozenset(alphabet)
		self._generator = Random()
		self._word = ""
		self._ended = False
		
	def __iter__(self):
		return self
		
	def __next__(self):
		result = self._generator.choice(tuple(self._alphabet.union({None})))
		if result is None or self._ended:
			self._ended = True
			raise StopIteration()
		else:
			self._word = self._word + result
			return result
		
	@property
	def alphabet(self) -> frozenset:
		return self._alphabet
	
	@property
	def word(self):
		while not self._ended:
			try:
				next(self)
			except StopIteration:
				pass
		return self._word
		
	def next(self):
		return self.__next__()
		
	def reset(self):
		self._word = ""
		self._ended = False


def chi_length_3(w: WordGenerator):  # requires at most 4 checks
	for n in range(1,4):
		try:
			
			print("Letter #{} is '{}'".format(n, next(w)))  # up to 3 checks, determining lengths 0 to 2
			
		except StopIteration:
			print("Word '{}' is of length shorter than 3!".format(w.word))
			return False
	try:
		
		print("Letter #4 is '{}'".format(next(w)))  # fourth check shows whether of length 3
		
		print("Word '{}' is of length longer than 3!".format(w.word))
		return False
	except StopIteration:
		print("Word '{}' is of length 3.".format(w.word))
		return True

def chi_starts_with_letter(w: WordGenerator, letter):  # always requires only one check
	try:
		
		result = next(w)  # one check
		
		print("Letter #1 is '{}'".format(result))
		if result == letter:
			print("Word '{}' starts with '{}'!".format(w.word, letter))
			return True
		else:
			print("Word '{}' does not start with '{}'.".format(w.word, letter))
			return False
	except StopIteration:
		print("Word '{}' does not start at all.".format(w.word))
		return False


A = {'a', 'b'}
</code>
<run id="6073186d90bc4">chi_length_3(WordGenerator(A))</run>
<run id="6073186d90c2b">chi_starts_with_letter(WordGenerator(A), 'a')</run>



=== S.10 ===

Berechenbarkeit $:= \exists$ Algorithmus, der für jedes $x \in D_f$ den Funktionswert $f$ effektiv ermittelt (effektiv = es muss ein entsprechendes Verfahren geben)

{| border="1" cellpadding="5" cellspacing="0"
|- 
| $A$					|| endlich
|-
| $A^\ast$				|| abzählbar unendlich
|-
| $\mathcal{P}(A^\ast)$			|| überabzählbar unendlich
|-
| $\chi_M$			|| überabzählbar unendlich
|-
| $\chi_M$ berechenbar		|| ?????
|-
| $\chi_M$ implementierbar	|| abzählbar unendlich
|-
|}




=== S.15–16 (Aufzählbarkeit) ===

==== $G$ (gerade Zahlen) ====

	$G \subset \mathbb{N}$

	kann $\mathbb{N}$ auf $G$ abbilden: 0→0, 1→2, 2→4, etc.

==== $P$ (Primzahlen) ====

	$P \subset \mathbb{N}$, $\exists$ berechenbare Methode für Entscheidung $n \in P \hspace{4mm} \longrightarrow \hspace{4mm} f:$ durchprobieren

==== $A^\ast$ ====

	trivial: längenlexikografisch aufzählen


==== $\forall$ endliche Menge ====

	nehme beliebiges Element $e$ aus Menge $M$ und bilde damit eine neue Menge $M'$ (beim ersten Mal also: $M' = \{e\}$)

	wiederhole für Restmenge $M \backslash M'$, bis $M \backslash M' = \empty$

==== $G = \{(0,0), (0,1), \ldots\}$ ====

	[1] $f: \mathbb{N} \mapsto G$ bijektiv

		Diagonalisierung: $\mathbb{Z} \times \mathbb{Z}$

	[2] Ordnungsrelation $p_<$

		$p_<(g_1, g_2) :\ <\!(f^{-1}(g_1), f^{-1}(g_2))$

	[3] $k$: Platznummern

		trivial: $k := f^{-1}$

	[4] Aufzählprozedur${}_G$, Berechenbarkeit?

		$f$ implementieren:

<code id="6073577774944">
def grid():
	yield (0, 0)
	x = 0
	y = 1
	phase = 0
	while True:
		if phase % 4 == 0:
			x = x+1
			y = y-1
			if y == 0:
				phase = phase+1
		elif phase % 4 == 1:
			x = x-1
			y = y-1
			if x == 0:
				phase = phase+1
		elif phase % 4 == 2:
			x = x-1
			y = y+1
			if y == 0:
				phase = phase+1
		elif phase % 4 == 3:
			x = x+1
			y = y+1
			if x == 0:
				phase = phase+1
		yield (x, y)
		if phase % 4 == 0 and x == 0:
			y = y+1

g = grid()
</code>
<run id="60735777749b8">
for i in range(0, 20):
	print(next(g))
</run>

	Berechenbarkeit: trivial



=== S.20 ===

==== Halteproblem semi-entscheidbar ====

	Immer, wenn das Programm terminiert, kann in endlicher Zeit eine Antwort gegeben werden.

==== $FIBS$ ====

	Aufzählfunktion $f$: (nach Berechnungsvorschrift)

		siehe Definition Berechenbarkeit, Aufzählfunktion ermittelt effektiv Funktionswert

	semi-entscheidbar: $\chi'_M : \begin{cases} \text{True}, & f\ \text{liefert Wert;}\\ \perp, & \text{else.}\end{cases}$

	entscheidbar: $f(x) < f(x+1)\ \forall x \in \mathbb{N} \Longrightarrow f(x) < g < f(x+1) \rightarrow g \not\in FIBS$ für gesuchtes $g$

==== $QZ$ ====

	Aufzählfunktion $q$: nach Berechnungsvorschrift

		siehe Definition Berechenbarkeit, Aufzählfunktion ermittelt effektiv Funktionswert

		semi-entscheidbar: $\chi'_{QZ} : \begin{cases} \text{True}, & q\ \text{liefert Wert;}\\ \perp, & \text{else.}\end{cases}$

		$q(x) < q(x+1)\ \forall x \in \mathbb{N} \Longrightarrow q(x) < g < q(x+1) \rightarrow g \not\in QZ$ für gesuchtes $g$

==== $M = \{a, b\}^\ast | w = a \cdot w'\ \forall w \in M$ ====

	siehe oben, entscheidbar $\Rightarrow$ semi-entscheidbar


=== S.23 ===

<code id="607363bc9af9e">
def even():
	x = 0
	while True:
		yield(x)
		x = x+2

def odd():
	x = 1
	while True:
		yield(x)
		x = x+2

def both():
	e = even()
	o = odd()
	while True:
		yield(next(e))
		yield(next(o))

b = both()
</code>
<run id="607363bc9b077">
for i in range(0, 30):
	print(next(b))
</run>