Jede endrekursive Funktion ist O(n).
FALSCH
Wurzel(n) Element O(n zum Quadrat)
WAHR
Es gibt nicht mehr Algorithmen als berechenbare Funktionen.
Die Fibonacci-Zahlen wachsen wie O(c hoch n) für eine Konstante c element Rellen Zahlen.
Nach Ausführung von c=b; a=b++; in Java gilt b==c+1 && a==b (für int a,b,c).
Für eine sortierte Folge ist die Ausführungszeit einer bin ren Suche immer geringer als die
einer sequentiellen Suche.
Die Menge aller rationalen Zahlen (Brüche) ist abzählbar.
Die Menge aller reelen Zahlen ist abzählbar.
Das Problem der Türme von Hanoi lässt sich für n Scheiben mit Aufwand O(n hoch 2) lösen.
Bei vorgegebener Eingabe (ist) kann Ausgabe eines nichtdeterministischen Algorithmus sowohl determiniert als auch nichtdeterminiert sein.
Die rekursive Funktion zur Berechnung des größten gemeinsamen Teilers (Algorithmus
von Euklid) ist endrekursiv.
Die rekursive binäre Suche ist eine endrekursive Funktion.
log2n Element O(logn)
„Menge M enthält unendlich viele Elemente.“ => „M ist überabzählbar.“
Quicksort eignet sich als externes Sortierverfahren.
Die modus ponens Regel lässt sich beschreiben als (B^(A=>B)=>A
Die Menge aller Funktionen ist überabzählbar.
Es gibt doppelt so viele positive rationale Zahlen (Brüche) wie natürliche Zahlen.
Es gibt genau so viele positive rationale Zahlen (Brüche) wie natürliche Zahlen.
Mergesort ist stabil.
Quicksort ist stabil.
Es gibt genau so viele positive rationale Zahlen wie natürliche Zahlen.
Reelle Zahlen sind überabzählbar
3, 5, 8, 14,22 ist Teil der Fibonacci Folge.
”Menge M ist überabzählbar.” <=> ”M enthält unendlich viele Elemente.”
In Java beschreibt (a>b ? a : b) das Maximum aus a und b (für int a,b).
Die modus ponens Regel lässt sich beschreiben als (A^(A=>B)=>B
„Menge M ist überabzählbar.“ => „M enthält unendlich viele Elemente.“
In Java verhalten sich die Anweisungen b=a+2; und b=++a; ++b; gleich (für int a,b).
Die Fibonacci-Zahlen wachsen wachsen wie O(cn) für eine Konstante c Element R.
Die Fibonacci-Zahlen wachsen wachsen wie O(n hoch q) für eine Konstante q element Rellen Zahlen.--> MUSS O(n hoch q sein)
Mergesort eignet sich als externes Sortierverfahren
Die Menge aller Algorithmen ist überabzählbar.
In Java gilt(p ? q : false) == true genau dann wenn (p && q)== true (für boolean p,q)
Eine Funktion f heißt O(g), genau dann wenn es Konstanten c>0 und no≥1 gibt, so dass f(n)≤c⋅g(n) für alle n≥n0 Einfach gesprochen bedeutet das,f wächst nicht wesentlich schneller als g
Es gibt mehr ganze als rationale Zahlen.
Es gibt mehr reelle als rationale Zahlen.
Eine Menge ist abzählbar genau dann wenn es eine bijektive Abbildung auf die natürlichen Zahlen gibt. Also injektiv und surjektiv.
Es gibt nichtberechenbare Funktionen, denn die Menge der berechenbaren Funktionen ist abzählbar und die aller Funktionen ist überabzählbar.
Last changed2 years ago