Search Ctrl + K

Search Ctrl + K

05 Extras

Digital Garden Homepage

07 Spaces

Life

2 Areas

take notes

Studium Workflow – SoSe 2026

work & education

2 Areas

Informatik Bachelor

25-26 WiSe

Berechenbarkeit und Komplexität

Definitionen

Ackermannfunktion

Akzeptieren & Sprache T(M)

Allgemeines Halteproblem (H)

Berechenbarkeitsbegriff

Church'sche These

Deterministische Turing-Maschine

Deterministischer Endlicher Automat

Diagonalisierungsbeweis (LOOP)

Erweiterte Überführungsfunktion

Folgekonfiguration (⊢M1)

Halten vs. Akzeptieren

Halteproblem auf leerem Band (H0)

Klasse NP (Guess and Check)

LOOP-Berechenbarkeit

Nichtdeterministische Turingmaschine (NTM)

NTIME (Komplexitätsklasse)

O-Notation (Landau-Symbole)

Pairing-Funktion

Partielle Rekursion

Polynomzeitreduktion

Primitive Rekursion

Reduzierbarkeit (Turing)

Registermaschine (RAM)

rekursiv aufzählbar

SAT (Erfüllbarkeitsproblem)

Satz von Cook und Levin

semi-entscheidbar

Speicherüberführungsfunktion

Spezielles Halteproblem (K)

Startkonfiguration TM

Totale Funktion

Turing-Berechenbarkeit

Universelle Turing-Maschine

WHILE-Berechenbarkeit

WHILE-LOOP-GOTO-Berechenbarkeit

Zeithierarchiesatz (Deterministisch)

Zeitkomplexitätsklasse DTIME

Zeitkomplexitätsklasse NTIME

Zeitkonstruierbare Funktion

Überführungsfunktion DTM

Berechenbarkeit und Komplexität

Logik

Definitionen

Ableitungsbaum (Logik)

Algorithmische Probleme der Logik

Alphabet der Aussagenlogik

Aussagenvariablen

Auswertungsproblem (Prädikatenlogik)

Auswertungsspiel (Prädikatenlogik)

Bereinigte Formel

Definierbarkeit (Logik)

Definitionen_Glossary

Definitionen_Index

Determiniertheit

Disjunktive Normalform

Distributivität

Ehrenfeucht-Fraïssé-Spiel

Elementare Äquivalenz

Elemente einer Logik

Elimination von Variablen

Entscheidungsproblem (Prädikatenlogik)

Erfüllbarkeit, Unerfüllbarkeit und Allgemeingültigkeit

Ersetzungslemma

Exklusives Oder

Formel (Prädikatenlogik)

Freie und gebundene Variablen

Generierte Substruktur

Gewinnstrategie

Große Disjunktion und Konjunktion

Herleitbarkeit (Sequenzenkalkül)

Hintikka-Formel

Homomorphieproblem

Homomorphismus (Logik)

Induktive Definition der Aussagenlogik

Induktive Menge

Interpretation (Prädikatenlogik)

Isomorphieinvarianz

Isomorphismus (Logik)

Koinzidenzlemma

Kompaktheitssatz (Prädikatenlogik)

Komplexität einer Sequenz

Komplexitätsklasse

Konjunktive Normalform

Konsistenz (Logik)

Korrektheit des Resolutionskalküls

Modellbeziehung (Prädikatenlogik)

Morgansche Regel

Negationsnormalform (Prädikatenlogik)

Negationsnormalform

Nicht-definierbare Eigenschaften

NP-Vollständig

Ordnungsrelation

Partieller Isomorphismus

Positionale Strategie

Prädikatenlogik (Idee)

Präferenzregeln

Pränexnormalform

Relation (Mathematik)

Resolutionsableitung

Resolutionsschritt

Resolutionswiderlegung

Satz von Ehrenfeucht

Sequenz (Logik)

Sequenzenkalkül (Aussagenlogik)

Sequenzenkalkül (Prädikatenlogik)

Signatur (Logik)

Struktur (Logik)

Substitution (Prädikatenlogik)

Substitutionslemma (Prädikatenlogik)

Substitutionslemma

Tau-abgeschlossene Menge

Term (Prädikatenlogik)

tertium non datur

Variablen für 3-Färbbarkeit

Variablen für Sudoku

Vertex Cover (Logik)

Vollständigkeit des Resolutionskalküls

Wahrheitsbelegung

Wahrheitswertfunktion

Wohl-fundiertes Spiel

Wortproblem endlicher Automaten

Äquivalenzrelation

Rechnernetze und verteilte Systeme

Definitionen

Access Network (Zugangsnetzwerk) bei Mobilfunktnetzen

Active Queue Management (AQM)

AIMD (Additive Increase Multiplicative Decrease)

Application Layer

Asynchronous Interaction

Bandwidth-Delay Product

Bellman-Ford-Algorithmus

Berkeley Algorithm

Best Effort Service

circuit switching

Client-Server-Modell

Client-Server-Paradigma

Client-Server-Varianten

Communication Links

Congestion Control

Congestion Window (cwnd)

Connection Migration

Consistent Hashing

Conventional Procedure Call

Coordinated Universal Time

Core Network (Kernnetzwerk) bei Mobilfunktnetzen

Count-to-Infinity-Problem

Cristian's Algorithm

Cut-through Packet Switching

Datagram Packet Switching

DHCP State Machine

Dijkstra-Algorithmus (Routing)

Distributed Hash Table

DNS-based Redirection

End-to-End Kommunikation

EUI-64 Verfahren

Fast Retransmit & Fast Recovery

Happens-Before Relation

Header Compression

Idempotente Aktionen

International Atomic Time

Internet Service Provider

Internet-Referenzmodell

IPv4 vs. IPv6 Header

Jitter & Buffering

Logische Topologie

Long Fat Networks (LFNs)

Longest Prefix Match

Max-Min Fairness

Message Receipt vs. Message Delivery

message switching

Mobilfunknetzwerk

Name–Adresse–Port

Narrow Interface

Network Time Protocol

OSI-Referenzmodell

Packet Switching

Physische Topologie

Propagationsverzögerung

Protocol Stack Overview

Protokoll (horizontal)

Real-Time Protocol (RTP)

Real-Time Transport Protocol (RTP)

Round-Trip Time

RTCP (Real-time Transport Control Protocol)

Schichtenmodell

Secure Sockets Layer (SSL)

Service (vertikal)

set- or getsockopt()

Silly Window Syndrome

Simple Object Access Protocol

Sliding Window Protocol

statistisches Multiplexing

store-and-forward

Synchronous Interaction

TCP Überlast-Algorithmen (Tahoe - Reno)

TCP-Drei-Wege-Handshake

TCP-Header-Struktur

TCP-Timer-Management

Three-Way-Handshake

Transaktions-Identifier

Transmission Control Protocol (TCP)

Transmission Rate

Transport Layer Security (TLS)

Transport Layer Services

TSAP (Transport Service Access Point)

UDP-Header (Überblick)

Unified Status Codes

User Datagram Protocol (UDP)

Verteilte Systeme (Bal – Colouris)

Verteilte Systeme (Tanenbaum)

Virtual Circuit Packet Switching

Web Service Description Language

wired connection

wireless connection

Wireless Sensor Networks

Übertragungszeit

Rechnernetze und Verteilte Systeme

Rechnerorganisation

Definitionen

1-aus-n-Decoder

ALU-Erweiterung (slt & beq)

ALU-Steuersignal

Antwortzeit vs. Durchsatz

Arithmetic Logic Unit

Average Memory Access Time (AMAT)

Boolesche Funktion

Branch Delay Slot

Branch Target Buffer (BTB)

Cache-Adressierung

Carry-Lookahead-Addierer

Carry-Propagate

CPU-Leistungsgleichung

Cycles per Instruction (CPI)

Datenkonflikt (Data Hazard)

Datenpfad (Datapath)

Datentransfer-Befehle

DIrekt abgebildeter Cache

Don't-Care-Bedingung

Dynamische Sprungvorhersage

Einer-Komplement

Forwarding (Bypassing)

Geometrisches Mittel (Performance)

Hexadezimalsystem

IEEE 754 Standard

Interleaved Memory

Karnaugh-Veitch-Diagramm

Kritischer Pfad (Critical Path)

Least Recently Used (LRU)

Least Significant Bit

Logikminimierung

Logische MIPS-Befehle

Lokalitätsprinzip

MIPS-Adressierungsarten

MIPS-Arithmetikbefehle

MIPS-Befehlsformate

MIPS-Registerkonventionen

MIPS-Speicheradressierung & Alignment

MIPS-Steuersignale

Most Significant Bit

Multilevel Cache

Negation im Zweierkomplement

PC-relative Adressierung

Pipeline Stall (Bubble)

Pipeline-Konflikt (Hazard)

Prozedurbefehle (jal, jr)

Pseudo-direkte Adressierung

Ripple-Carry-Addierer

Satz-assoziativer Cache

Schaltnetz vs. Schaltwerk

SPEC (Benchmark)

Speicherhierarchie

Speicherstillstands-Zyklen

Steuerkonflikt (Control Hazard)

Steuerwerk (Control Unit)

Voll-assoziativer Cache

Vorzeichen-Betrags-Darstellung

Vorzeichenerweiterung

Zweier-Komplement

Zweierkomplement-Subtraktion

Softwaretechnik und Programmierparadigmen

Definitionen

(Alle) Primzahlen in Haskell

Aggregation (UML)

Agile Softwareentwicklung

Aktivitätsdiagramm

Anfragen in Prolog

Anonyme Funktionen

Anwendungsfalldiagramm (Use Case Diagram)

Architekturstil

Assoziation (UML)

Aufzählungstyp in Haskell

Bedingungsüberdeckung (C2, MC DC)

Builder (Pattern)

Bäume in Haskell

Closures mit Let

Command (Pattern)

Composite (Pattern)

Datentypen in Haskell

Definition of Done

Dekonstruktion in Haskell

Design by Contract (OCL)

Design Pattern (Entwurfsmuster)

Domänenspezifische Sprache (DSL)

Dreiwertige Logik (OCL)

Eager Evaluation

Entity-Control-Boundary (ECB)

Event-based Architecture

Executable UML (xUML)

Extend-Beziehung (UML)

Extreme Programming

First-Class Citizens

Funktionale vs. Nicht-Funktionale Anforderungen

Funktionen mit mehreren Parametern in Haskell

Funktionen mit Parameter in Haskell

Funktionen mit verschiedenen Typen in Haskell

Funktionen mit Verzweigung in Haskell

Funktionsaufrufe in Haskell

Funktionskomposition

Funktoren in Prolog

Generalisierung (UML)

Grundlegende Listenoperationen

Grundlegende Prozessaktivitäten

Halstead-Metriken

Hoare-Axiome (Skip & Zuweisung)

Hoare-Inferenzregeln (Sequenz, If, Konsequenz)

Include-Beziehung (UML)

Inkrementelle Entwicklung

Interaktionsdiagramm

Interrupt-based Architecture

Invariante (OCL)

Kanban (Softwareentwicklung)

Klasse extrahieren

Klassendiagramm

Komposition (UML)

Konstante Funktionen in Haskell

Kontrollflussgraph (CFG)

Kontrollflussüberdeckung (C0, C1)

Lastenheft vs. Pflichtenheft

Layer-based Architecture

Lazy Evaluation

List Comprehensions

Liste ganzer Zahlen in Haskell

Listenfunktionale

Methode extrahieren

Model Driven Development (MDD)

Model-View-Controller (MVC)

Multiplizität (UML)

Natürliche Zahlen in Haskell

Navigierbarkeit (UML)

Object Constraint Language (OCL)

Objektorientierte Metriken

Observer (Pattern)

OCL Collection-Typen

ocllsTypeOf vs oclssKindOf

Paar-Operationen

Parametrisierte Tupel in Haskell

Partielle Applikation

Partielle vs. Totale Korrektheit

Pattern Matching auf Listen

pattern matching

Pipes-and-Filter Architecture

Produkttyp mit Record-Syntax in Haskell

Produkttyp standard in Haskell

Proxy (Pattern)

Push- vs. Pull-Prinzip

Regel in Prolog

Regressionstest

Rekursion in Prolog

Rekursive Datenstrukturen in Haskell

Repository-based

Requirements Engineering Prozess

Resolution in Prolog

Schleifeninvariante & While-Regel

Selektoren in Haskell

Service Oriented Architecture (SOA)

Singleton (Pattern)

Software Engineering

Software-Qualität

Softwaremetriken

Spiralmodell (Boehm)

Stereotyp (UML)

Summentyp in Haskell

Terminierungsfunktion

Typinferenz in Haskell

UML (Unified Modeling Language)

Unendliche Listen

Variablen in Prolog

Verhaltensdiagramm

Wasserfallmodell

WHILE-Sprache Syntax

Wächterbedingung (Guard)

Wächterbedingungen

Zustandsdiagramm

Zyklomatische Komplexität (McCabe)

Äquivalenzklassen & Grenzwerte

Wissenschaftliches Rechnen

Definitionen

Abelsche Gruppe

Abgeschlossenheit

Algebraische und Geometrische Vielfachheit

Assoziativität

Ausgleichsproblem

Bisektionsverfahren

Bit-Reversal Permutation

Butterfly-Operation

Charakteristisches Polynom

Cholesky-Zerlegung

Definitionen_Index

Diagonalisierbarkeit

Diskrete Fouriertransformation (DFT)

Diskretes Signal

Diskretisierung

Distributivgesetze

Eigenschaften symmetrischer Matrizen

Eigenwert und Eigenvektor

Festkommadarstellung

Gauß-Integration

Gaußsche Eliminationsmethode

Geometrische Interpretation LGS

Gewichtete Gauß-Integration

Goldener-Schnitt-Suche

Gradientenabstieg

Hauptkomponentenanalyse

Interpolationsproblem

Inverses Element

Irrationale Zahl

Kommutativität

Konjugierte Gradienten

Kubischer Spline

Lagrange-Basispolynome

Lagrange-Multiplikator

Lineare Regression

Lineare Zeitinvarianz (LTI)

Lineares Gleichungssystem

LR mit Pivoting

Maschinengenauigkeit

Matrix-Darstellung eines LGS

Natürliche Zahlen

Neutrales Element

Newton-Cotes-Formeln

Newton-Verfahren (Optimierung)

Newton-Verfahren

Normalengleichung

Nullstellenproblem

Numerische Integration

Orthogonale Polynome

Orthogonale Regression

Positiv Definit

Positiv Semidefinit

Quadratische Konvergenz

Rang-Lösungsübersicht

Rayleigh-Quotient

Runge-Phänomen

Rückwärtseinsetzen

Singulärwertzerlegung

Stellenwertsystem

Tschebyschew-Polynome

Tschebyschew-Stützstellen

Vandermonde-Matrix

Vorwärtseinsetzen

Vorzeichendarstellung

Zyklische Faltung

Ähnlichkeit von Matrizen

Äquivalenzklassen

26 SoSe

Diskrete Strukturen

Definitions

(intern) knoten-disjunkt

Adjazenz, Inzidenz und Nachbarschaft

Alternierender Pfad

Auswählen von Elementen aus einer Menge

Berechnung Starker Zusammenhangskomponenten (SCC-Algorithmus)

Beschrifteter Graph

Bipartiter Graph

Distanz, Durchmesser und Radius

Ebene Einbettung und Planare Graphen

Einfacher und Gerichteter Graph

Erweiternder Pfad

Eulersche Graphen

Eulersche Polyederformel und Kantenbeschränkung

Finde unabhängige Menge der Größe k

Gebiete (Faces) und Kantenbegrenzung

Gerichtete Nachbarschaften und Grad-Konzepte

Gerichtete Tiefensuche (DFS) und topologische Nummerierung

Gerichteter Graph

Gerichteter Weg, Gerichteter Pfad und Erreichbarkeit

Induktionsbeweis

k-Färbbarer Graph

Klammerausdruck

Knoten-Färbung und Chromatische Zahl

Matching von einer Knotenmenge S

Mehrfachzusammenhang (k-Zusammenhang)

Perfektes Matching

Prinzip der Inklusion-Exklusion

r-degenerierte Graphen

Rekursive bzw. induktive Definition

Satz - Knotenzahl vollständiger balancierter Binärbäume

Satz - Rekursion der Stirling-Zahlen erster Art

Satz - Rekursion der Stirling-Zahlen zweiter Art

Satz - Rekursive Formel der Catalan-Zahlen

Satz - Zahl der Blätter in vollständigen balancierten Binärbäumen

Satz - Zahl korrekter Klammerausdrücke

Satz von König

Satz von Menger

Schnittknoten und Brücke

Separationen und Trenner

Stabiles Matching

Starker Zusammenhang und Zusammenhangskomponenten

Stirling-Zahlen erster Art

Stirling-Zahlen zweiter Art

Theorem von Gale und Shapley

Unabhängige Menge

Unterteilung (Subdivision) und Satz von Kuratowski

Vergrößerungs-Prinzip

Vertex Cover (Diskrete Strukturen)

Weg, Pfad und Kreis (Zyklus)

Zeichnung und Einbettung eines Graphen

Zusammenhang und Komponenten

Diskrete Strukturen

Formal-mathematische Grundlagen

Definitions

(echte) Teilmenge

Ableitungsbaum (FoG)

Algebra von Funktionen

Alpha-Konversion

Beschränkte Quantoren und Eindeutigkeit

Beweis durch Widerspruch

Beweisverpflichtung

definierende Gleichheit

Existentielle Quantifikation (Beweisregeln)

Extensionale Definition

Gleichheit (Mengen)

Größe von Mengen

Induktive Definition

Intensionale Definition

Kartesisches Produkt

konstatierende Gleichheit

Logische Äquivalenzen als Beweisregeln

MOC Logik – Grundlage

OK (Variablenfang)

Regelschema und Pattern Matching

Russell'sches Paradox

Rückwärtsbeweisschritt

Substitution (Logik)

Syntax der Aussagenlogik

Syntax der Prädikatenlogik

Terme und Prädikate

Totalität und Eindeutigkeit

Ungleich (Mengen)

Universelle Quantifikation (Beweisregeln)

Vorwärtsbeweisschritt

Formal-mathematische Grundlagen

Informationssysteme und Datenanalyse

Definitions

Aggregation, Gruppierung und Sortierung in SQL

Anomalien (Datenbanken)

Armstrong-Axiome

Attributhülle und Membership-Problem

Datenanalyse-Prozess

Datenbank-Merkmale

Datenbanksystem

Datendefinitionssprache

Datenmanagement-Prozess

Datenmanipulationssprache

Dekomposition von Relationen

Drei-Schichten-Architektur

ER-Modellierung

Funktionale Abhängigkeit (FD)

Geschachtelte Anfrage (Subquery)

Informationskapazität

Informationssystem

Integritätsbedingungen

Interpretation von Attributen

Interpretation von Entity-Typen

Interpretation von Integritätsbedingungen

Interpretation von Relationship-Typen

Kardinalität (ISDA)

Konsistenzbedingung

Konzeptionelles Schema

Mengenoperationen in SQL

n-stelliger Relationship-Typ

Nebenbedingungen

Normalformen (1NF bis BCNF)

Phasen des Datenbankentwurfs

Problem-Lösung-Zyklus

Referentielle Integrität

Relation (ISDA)

Relationale Algebra

Relationales Modell

Relationship-Typ

Relationsschema

Rollen in Relationship-Typen

Schlüsselbestimmung durch FDs

Schwacher Entity-Typ

SQL-CREATE TRIGGER

SQL-Datenbankobjekte

SQL-Grundstruktur und deklaratives Prinzip

SQL-LIKE and Wildcards

Syntaktisch korrektes ER-Diagramm

Triviale und Nicht-triviale FDs

Problemtypen

ER-Modell aus Text erstellen

Fehler im ER-Modell finden

Schlüssel bestimmen

Informationssysteme und Datenanalyse

Systemprogrammierung

Definitions

Abhängigkeitsgraph

Ablaufplanlänge

Bankier-Algorithmus (Dijkstra)

Behandlung eines Seitenfehlers (Page Fault)

Betriebsmittel (Ressource)

Betriebsmittelgraph

Beziehungen zwischen Prozessen

Call-by-Reference

Clock-Algorithmus (Second-Chance)

Erzeuger-Verbraucher-Problem

Fork, Join, Wait

Formale Verdrängungsalgorithmen

Frühester Startzeitpunkt

Geschachtelte Unterbrechungsbehandlung

Hard Real-Time System

Kernel-Level-Thread

Kritischer Abschnitt

Long-Term Scheduling

Medium-Term Scheduling

Mehrstufige Seitentabellen

Multilevel-Feedback-Scheduling

Multilevel-Scheduling

Multithreading-Modelle

Nachschub- und Auswahlstrategien (Policies)

Nebenläufigkeit

Off-line Scheduling

On-line Scheduling

Page-Fault-Frequency-Modell (PFF)

Paging-Daemon und Schwellwertsteuerung

parbegin und parend

periodischer Prozess

Physischer Adressraum

Prioritätsinvertierung

Prioritätsvererbung

Prozesshierarchie

Prozessinteraktion

Prozesskontrollblock

Prozessumschaltung

Rate Monotonic Scheduling

Reader-Writer-Problem

Schedulability Test

Segmentation Fault

Seitenadressierung (Paging)

Seitentabelle (Page Table) und Steuerbits

Sequentielle Unterbrechungsbehandlung

Shell-Variablen

Short-Term Scheduling

Soft Real-Time System

Speicherallokation und Allokationsformen

Tatsächlicher Endzeitpunkt

Tatsächlicher Startzeitpunkt

Theoretische Leistung

Unsichere Betriebsmittelsituation

Unterbrechungsanalyse

Unterbrechungsbehandlung

User-Level-Thread

Virtueller Adressraum

Vorder- und Hintergrundprozess

Zeitscheibenbetrieb

Zustandsübergänge

Zweizeiger-Clock-Algorithmus (Solaris-Paging)

Systemprogrammierung

Informatik Bachelor of Science - Technische Universität Berlin

MINTgrün

24-25-WiSe

Einführung ins Programmieren

synthesis notes

Sortieralgorithmen

Sortieralgorithmen

Bedingte Anweisung

Boolean Expressions

divide & conquer

double linked list

Dynamische Datenstrukturen

Dynamische Speicherallokation

Ein- und Ausgabekanäle

Einfache Datenstrukturen

Fehlerbehandlung

Heap (IntroProg)

Hilfe bei Computerproblem

Kommunikation mit Computern

Korrektheitsbeweis

Logarithmus dualis

Modularisierung

Programmiersprache

Quellcode kommentieren

Raumkomplexität

Speicheradresse

Stack (IntroProg)

synthesis notes_GlossaryIndex

synthesis notes_Index

Was tun Computer?

Wie beweist man die Korrektheit eines Algorithmus?

Zeitkomplexität

C

Informatik Propädeutikum

synthesis notes

Algorithmus von Hierholzer

Artificial Intelligence

Bayessche Formel

Bedingte Wahrscheinlichkeit

Euklidischer Algorithmus

Geschichte Computer

Königsberger Brückenproblem

Problemlösestrategien

synthesis notes_Index

Vertrauenswürdigkeit von Quellen

Vorhersage von Daten

25-SoSe

Analysis I und Lineare Algebra für Ingenieurwissenschaften

synthesis notes

10

11

Basis und Dimension

Lineare Unabhängigkeit

12

13

Lineare Gleichungssysteme

15

Lineare Abbildungen

16

Koordinatendarstellung

Matrixdarstellung

17

18

Berechnung von Grenzwerten

19

20

Sätze über stetige Funktionen

21

Differenzierbarkeit

23

24

Taylorpolynom und Taylorformel

01

02

Summen- und Produktzeichen

Zahlen und Zahlendarstellungen

03

Komplexe Zahlen

04

Binomialkoeffizient

Vollständige Induktion

05

Eigenschaften reeller Funktionen

06

Elementare Funktionen

Sinus und Cosinus

08

09

Partialbruchzerlegung

Rationale Funktionen

Enter your search text in the box above

Select a result to preview

Enter to select

⇅ to navigate

ESC to close

k-Partition

#Studium #Informatik #Definition #DS

Eine k-Partition einer $n$ -elementigen Menge

A = {a_{1}, \dots, a_{n}}

ist eine Zerlegung von $A$ in:

$k$ nicht-leere,
paarweise disjunkte Mengen.

Links

Stirling-Zahlen zweiter Art
DS_vollständiger_foliensatz.pdf

Connected Pages

k-Partition

Links

Pages mentioning this page

Satz - Rekursion der Stirling-Zahlen zweiter Art

Stirling-Zahlen zweiter Art