Select your language

Suggested languages for you:
Log In Anmelden

Lernmaterialien für FGI an der Universität Potsdam

Greife auf kostenlose Karteikarten, Zusammenfassungen, Übungsaufgaben und Altklausuren für deinen FGI Kurs an der Universität Potsdam zu.

TESTE DEIN WISSEN

Merkmale von guten Beweisen

Lösung anzeigen
TESTE DEIN WISSEN

– Klar erkennbarer roter Faden in der Argumentation
– Knapp genug, um verständlich zu sein
– Genau genug, um fehlende Details rekonstruieren zu können
Keine Gedankensprünge, außer wenn sie leicht nachvollziehbar sind


Weiteres:

- Anschauung alleine ist kein Beweis

- Umgangssprache ist oft mißverständlich

- Formale Notation ist nur eine Notationshilfe

- Sie sind das Handwerkzeug, daß jeder kennen muß

- In der Informatik dreht sich alles um Formales

Lösung ausblenden
TESTE DEIN WISSEN

Deduktiver Beweis

Lösung anzeigen
TESTE DEIN WISSEN

Verkettung von Aussagen

– Zwischenaussagen Ai müssen schlüssig aus dem Vorhergehenden folgen
– Dabei dürfen nur Annahmen aus A, Definitionen, bewiesene Aussagen,
mathematische Gesetze, logische Schlußfolgerungen verwendet werden
– Einfachste Form der Beweisführung, auch Deduktiver Beweis genannt

Lösung ausblenden
TESTE DEIN WISSEN

Arten von Negationsbeweisen

Lösung anzeigen
TESTE DEIN WISSEN

1. Kontraposition

2. Widerspruchsbeweise

3. Gegenbeispiele

Lösung ausblenden
TESTE DEIN WISSEN

Kontraposition

Lösung anzeigen
TESTE DEIN WISSEN

– Anstatt zu zeigen, daß die Behauptung B aus den Annahmen A folgt,
beweise, daß nicht A aus der Annahme nicht B folgt
– Aussagenlogisch ist ¬B⇒¬A äquivalent zu A⇒B


Anwendung:

Indirekte Beweisführung

Lösung ausblenden
TESTE DEIN WISSEN

Widerspruchsbeweise

Lösung anzeigen
TESTE DEIN WISSEN

- zeigen, daß B niemals gelten kann

– Zeige, daß aus Annahme B ein Widerspruch folgt
– Beispiel: Ist S endliche Teilmenge einer unendlichen Menge U,
dann ist das Komplement von S bezüglich U unendlich
– Beweisidee: Wenn ¯S endlich wäre, dann müsste auch U endlich sein.∗

Lösung ausblenden
TESTE DEIN WISSEN

Gegenbeispiele

Lösung anzeigen
TESTE DEIN WISSEN

zeigen, daß B nicht immer wahr sein kann

– B ist nicht allgemeingültig, wenn es ein einziges Gegenbeispiel gibt
– Beispiel: “Wenn x eine Primzahl ist, dann ist x ungerade” ist falsch
– Gegenbeispiel: 2 ist eine gerade Zahl, die eine Primzahl ist

Lösung ausblenden
TESTE DEIN WISSEN

Standardinduktion

Lösung anzeigen
TESTE DEIN WISSEN

“Gilt B für i und B für n+1, wenn B für n gilt, dann gilt B für alle n≥i”


– Beispiel: Für alle x≥4 gilt 2x≥x2
Induktionsanfang x=4: Es ist 2x = 16 ≥ 16 = x2
Induktionsannahme: Es gelte 2n≥n2 für ein beliebiges n≥4
Induktionsschritt: Es ist 2n+1 = 2∗2n ≥ 2n2 (aufgrund der Induktionsannahme)
und (n+1)2 = n2+2n+1 = n(n+2+1
also gilt 2n+1 ≥ (n+1)2
n) ≤ n(n+n) = 2n2
Aufgrund des Induktionsprinzips gilt damit 2n≥n2 für alle n≥4

Lösung ausblenden
TESTE DEIN WISSEN

Vollständige Induktion

Lösung anzeigen
TESTE DEIN WISSEN

– “Folgt B für n, wenn B für alle i≤j

– Mächtiger, da man nicht den unmittelbaren Vorgänger benutzen muss

Lösung ausblenden
TESTE DEIN WISSEN

Datenstrukturen die sich induktiv repräsentieren lassen Beispiele

Lösung anzeigen
TESTE DEIN WISSEN

• N: Nat ürliche Zahlen
– 0 ∈N
(Null ist eine natürliche Zahl)
– n ∈N ⇒ n+1 ∈N (jeder Nachfolger einer natürlichen Zahl ist eine natürliche Zahl)
• List T: Listen über einem Datentyp T
– [ ] ∈ List T
– l ∈ List T ∧ x ∈T ⇒ x :: l ∈ List T
– w ∈ Σ∗ ∧ a ∈Σ ⇒ w a ∈ Σ∗
(leere Liste - ohne Elemente)
(Voranstellen eines Elements aus T)
• Σ∗: Wörter (Strings) über einem Alphabet Σ
– ǫ ∈Σ∗
• Tree T: Bäume mit Markierungen aus T
– x ∈T ⇒ x ∈ Tree T
(leeres Wort - ohne Symbole)
(Anhängen eines Symbols aus Σ an ein Wort)
(einzelner Knoten mit Markierung x)
– x ∈T ∧ t1..tn ∈ Tree T ⇒ (x, [t1, .., tn]) ∈ Tree T
(Baum mit Wurzel x und Unterbäumen t1..tn)

Lösung ausblenden
TESTE DEIN WISSEN

Was sind reguläre Sprachen?

Lösung anzeigen
TESTE DEIN WISSEN

Einfache Sprachen, die von einem DEA überprüft bzw. akzeptiert werden können.

Lösung ausblenden
TESTE DEIN WISSEN

Was sind die 5 Bestandteile eines DEA-Tupels?

Lösung anzeigen
TESTE DEIN WISSEN

5 Bestandteile:

A = (Q, Σ, δ, q0, F)


• Q nichtleere endliche Zustandsmenge

• Σ (endliches) Eingabealphabet

• δ:Q×Σ → Q Zustands Überführungsfunktion

• q0∈Q Startzustand

• F ⊆Q Menge von akzeptierenden Zustanden

Lösung ausblenden
TESTE DEIN WISSEN

Was ist ein Beweis?

Lösung anzeigen
TESTE DEIN WISSEN

- ein Argument, dass den Leser überzeugt

- eine Begründung, warum eine Behauptung gelten soll

Lösung ausblenden
  • 107328 Karteikarten
  • 2388 Studierende
  • 114 Lernmaterialien

Beispielhafte Karteikarten für deinen FGI Kurs an der Universität Potsdam - von Kommilitonen auf StudySmarter erstellt!

Q:

Merkmale von guten Beweisen

A:

– Klar erkennbarer roter Faden in der Argumentation
– Knapp genug, um verständlich zu sein
– Genau genug, um fehlende Details rekonstruieren zu können
Keine Gedankensprünge, außer wenn sie leicht nachvollziehbar sind


Weiteres:

- Anschauung alleine ist kein Beweis

- Umgangssprache ist oft mißverständlich

- Formale Notation ist nur eine Notationshilfe

- Sie sind das Handwerkzeug, daß jeder kennen muß

- In der Informatik dreht sich alles um Formales

Q:

Deduktiver Beweis

A:

Verkettung von Aussagen

– Zwischenaussagen Ai müssen schlüssig aus dem Vorhergehenden folgen
– Dabei dürfen nur Annahmen aus A, Definitionen, bewiesene Aussagen,
mathematische Gesetze, logische Schlußfolgerungen verwendet werden
– Einfachste Form der Beweisführung, auch Deduktiver Beweis genannt

Q:

Arten von Negationsbeweisen

A:

1. Kontraposition

2. Widerspruchsbeweise

3. Gegenbeispiele

Q:

Kontraposition

A:

– Anstatt zu zeigen, daß die Behauptung B aus den Annahmen A folgt,
beweise, daß nicht A aus der Annahme nicht B folgt
– Aussagenlogisch ist ¬B⇒¬A äquivalent zu A⇒B


Anwendung:

Indirekte Beweisführung

Q:

Widerspruchsbeweise

A:

- zeigen, daß B niemals gelten kann

– Zeige, daß aus Annahme B ein Widerspruch folgt
– Beispiel: Ist S endliche Teilmenge einer unendlichen Menge U,
dann ist das Komplement von S bezüglich U unendlich
– Beweisidee: Wenn ¯S endlich wäre, dann müsste auch U endlich sein.∗

Mehr Karteikarten anzeigen
Q:

Gegenbeispiele

A:

zeigen, daß B nicht immer wahr sein kann

– B ist nicht allgemeingültig, wenn es ein einziges Gegenbeispiel gibt
– Beispiel: “Wenn x eine Primzahl ist, dann ist x ungerade” ist falsch
– Gegenbeispiel: 2 ist eine gerade Zahl, die eine Primzahl ist

Q:

Standardinduktion

A:

“Gilt B für i und B für n+1, wenn B für n gilt, dann gilt B für alle n≥i”


– Beispiel: Für alle x≥4 gilt 2x≥x2
Induktionsanfang x=4: Es ist 2x = 16 ≥ 16 = x2
Induktionsannahme: Es gelte 2n≥n2 für ein beliebiges n≥4
Induktionsschritt: Es ist 2n+1 = 2∗2n ≥ 2n2 (aufgrund der Induktionsannahme)
und (n+1)2 = n2+2n+1 = n(n+2+1
also gilt 2n+1 ≥ (n+1)2
n) ≤ n(n+n) = 2n2
Aufgrund des Induktionsprinzips gilt damit 2n≥n2 für alle n≥4

Q:

Vollständige Induktion

A:

– “Folgt B für n, wenn B für alle i≤j

– Mächtiger, da man nicht den unmittelbaren Vorgänger benutzen muss

Q:

Datenstrukturen die sich induktiv repräsentieren lassen Beispiele

A:

• N: Nat ürliche Zahlen
– 0 ∈N
(Null ist eine natürliche Zahl)
– n ∈N ⇒ n+1 ∈N (jeder Nachfolger einer natürlichen Zahl ist eine natürliche Zahl)
• List T: Listen über einem Datentyp T
– [ ] ∈ List T
– l ∈ List T ∧ x ∈T ⇒ x :: l ∈ List T
– w ∈ Σ∗ ∧ a ∈Σ ⇒ w a ∈ Σ∗
(leere Liste - ohne Elemente)
(Voranstellen eines Elements aus T)
• Σ∗: Wörter (Strings) über einem Alphabet Σ
– ǫ ∈Σ∗
• Tree T: Bäume mit Markierungen aus T
– x ∈T ⇒ x ∈ Tree T
(leeres Wort - ohne Symbole)
(Anhängen eines Symbols aus Σ an ein Wort)
(einzelner Knoten mit Markierung x)
– x ∈T ∧ t1..tn ∈ Tree T ⇒ (x, [t1, .., tn]) ∈ Tree T
(Baum mit Wurzel x und Unterbäumen t1..tn)

Q:

Was sind reguläre Sprachen?

A:

Einfache Sprachen, die von einem DEA überprüft bzw. akzeptiert werden können.

Q:

Was sind die 5 Bestandteile eines DEA-Tupels?

A:

5 Bestandteile:

A = (Q, Σ, δ, q0, F)


• Q nichtleere endliche Zustandsmenge

• Σ (endliches) Eingabealphabet

• δ:Q×Σ → Q Zustands Überführungsfunktion

• q0∈Q Startzustand

• F ⊆Q Menge von akzeptierenden Zustanden

Q:

Was ist ein Beweis?

A:

- ein Argument, dass den Leser überzeugt

- eine Begründung, warum eine Behauptung gelten soll

FGI

Erstelle und finde Lernmaterialien auf StudySmarter.

Greife kostenlos auf tausende geteilte Karteikarten, Zusammenfassungen, Altklausuren und mehr zu.

Jetzt loslegen

Das sind die beliebtesten StudySmarter Kurse für deinen Studiengang FGI an der Universität Potsdam

Für deinen Studiengang FGI an der Universität Potsdam gibt es bereits viele Kurse, die von deinen Kommilitonen auf StudySmarter erstellt wurden. Karteikarten, Zusammenfassungen, Altklausuren, Übungsaufgaben und mehr warten auf dich!

Das sind die beliebtesten FGI Kurse im gesamten StudySmarter Universum

F1

Leibniz Universität Hannover

Zum Kurs
FG I

Hochschule der Polizei Rheinland-Pfalz (HdP)

Zum Kurs

Die all-in-one Lernapp für Studierende

Greife auf Millionen geteilter Lernmaterialien der StudySmarter Community zu
Kostenlos anmelden FGI
Erstelle Karteikarten und Zusammenfassungen mit den StudySmarter Tools
Kostenlos loslegen FGI