Constraintprogrammierung - Versionsgeschichte

Okoska-törp: /* growthexperiments-addlink-summary-summary:2|0|0 */

2025-02-21T21:05:16Z

Linkvorschlag-Funktion: 2 Links hinzugefügt.

← Nächstältere Version		Version vom 21. Februar 2025, 23:05 Uhr
Zeile 62:		Zeile 62:
	Die Constraint-imperative Programmierung vereinigt die beiden Paradigmen Constraintprogrammierung und [[imperative Programmierung]]. In imperativen Sprachen beschreibt der Programmierer, ''wie'' ein gegebenes Problem durch eine Sequenz von Anweisungen gelöst wird. Sie eignet sich besonders zur Modellierung von zeitlichen Abläufen. Dagegen konzentriert sich der Programmierer in der Constraintprogrammierung auf das ''Was'', d. h., er beschreibt das Problem durch deren Eigenschaften in Form von Constraints. Die Kombination der imperativen Programmierung mit deklarativen Constraints stellt somit eine besondere Herausforderung dar.<ref>Hofstedt, Wolf: ''Einführung in die Constraint-Programmierung.'' 2007, S. 185.</ref>		Die Constraint-imperative Programmierung vereinigt die beiden Paradigmen Constraintprogrammierung und [[imperative Programmierung]]. In imperativen Sprachen beschreibt der Programmierer, ''wie'' ein gegebenes Problem durch eine Sequenz von Anweisungen gelöst wird. Sie eignet sich besonders zur Modellierung von zeitlichen Abläufen. Dagegen konzentriert sich der Programmierer in der Constraintprogrammierung auf das ''Was'', d. h., er beschreibt das Problem durch deren Eigenschaften in Form von Constraints. Die Kombination der imperativen Programmierung mit deklarativen Constraints stellt somit eine besondere Herausforderung dar.<ref>Hofstedt, Wolf: ''Einführung in die Constraint-Programmierung.'' 2007, S. 185.</ref>

	Ein Beispiel für eine Constraint-imperative Programmiersprache ist Turtle.<ref>catamorph.de: {{Webarchiv \|url=http://catamorph.de/turtle/turtle.de.html \|text=Turtle – eine constraint-imperative Programmiersprache \|wayback=20160408134625 \|archiv-bot=}}</ref> Diese entstand als eine einfache imperative Basissprache und wurde zunächst um [[Funktionale Programmierung\|funktionale Konzepte]] wie Funktionen höherer Ordnung erweitert. Danach wurde sie mit vier wesentlichen Konzepten zur Constraint-Programmierung angereichert<ref>Hofstedt, Wolf: ''Einführung in die Constraint-Programmierung.'' 2007, S. 185–192.</ref>:		Ein Beispiel für eine Constraint-imperative Programmiersprache ist Turtle.<ref>catamorph.de: {{Webarchiv \|url=http://catamorph.de/turtle/turtle.de.html \|text=Turtle – eine constraint-imperative Programmiersprache \|wayback=20160408134625 \|archiv-bot=}}</ref> Diese entstand als eine einfache imperative Basissprache und wurde zunächst um [[Funktionale Programmierung\|funktionale Konzepte]] wie [[Funktion höherer Ordnung\|Funktionen höherer Ordnung]] erweitert. Danach wurde sie mit vier wesentlichen Konzepten zur Constraint-Programmierung angereichert<ref>Hofstedt, Wolf: ''Einführung in die Constraint-Programmierung.'' 2007, S. 185–192.</ref>:

	* Constraint-Variablen: Diese unterscheiden sich von „normalen“ imperativen Variablen, deren Werte durch Zuweisungen festgelegt werden, dadurch, dass ihre Werte durch Constraints festgelegt bzw. eingeschränkt werden. Constraint-Variablen werden auch als deklarative Variablen bezeichnet.		* Constraint-Variablen: Diese unterscheiden sich von „normalen“ imperativen Variablen, deren Werte durch Zuweisungen festgelegt werden, dadurch, dass ihre Werte durch Constraints festgelegt bzw. eingeschränkt werden. Constraint-Variablen werden auch als deklarative Variablen bezeichnet.
Zeile 84:		Zeile 84:

	== Anwendungen ==		== Anwendungen ==
	Im wissenschaftlichen Bereich findet die Constraint-basierte Programmierung beispielsweise bei der Verarbeitung natürlicher Sprache, im [[Maschinengestütztes Beweisen\|maschinengestützten Beweisen]], in der Analyse von Programmen und in der [[Molekularbiologie]] Anwendung. In der industriellen Praxis sind typische Anwendungen Optimierungsprobleme und [[Scheduling]]-Aufgaben, [[Integrierter Schaltkreis\|Schaltkreis]]-Design und -Verifikation, graphische Systeme und [[Benutzerschnittstelle]]n.<ref>Petra Hofstedt: Kapitel ''Constraints.'' In: Günther Görz, Josef Schneeberger, Ute Schmid (Hrsg.): ''Handbuch der Künstlichen Intelligenz.'' 5. überarbeitete und aktualisierte Auflage. Oldenbourg Verlag: München, 2014, S. 206.</ref>		Im wissenschaftlichen Bereich findet die Constraint-basierte Programmierung beispielsweise bei der Verarbeitung [[Natürliche Sprache\|natürlicher Sprache]], im [[Maschinengestütztes Beweisen\|maschinengestützten Beweisen]], in der Analyse von Programmen und in der [[Molekularbiologie]] Anwendung. In der industriellen Praxis sind typische Anwendungen Optimierungsprobleme und [[Scheduling]]-Aufgaben, [[Integrierter Schaltkreis\|Schaltkreis]]-Design und -Verifikation, graphische Systeme und [[Benutzerschnittstelle]]n.<ref>Petra Hofstedt: Kapitel ''Constraints.'' In: Günther Görz, Josef Schneeberger, Ute Schmid (Hrsg.): ''Handbuch der Künstlichen Intelligenz.'' 5. überarbeitete und aktualisierte Auflage. Oldenbourg Verlag: München, 2014, S. 206.</ref>

	== Literatur ==		== Literatur ==

Aka: /* Literatur */ Tippfehler entfernt

2024-05-14T15:44:44Z

Literatur: Tippfehler entfernt

← Nächstältere Version		Version vom 14. Mai 2024, 17:44 Uhr
Zeile 87:		Zeile 87:

	== Literatur ==		== Literatur ==
	* Frédéric Benhamou, Narendra Jussien, Barry ~~O'Sullivan~~: ''Trends in constraint programming.'' John Wiley and Sons: London/Newport Beach, 2007.		* Frédéric Benhamou, Narendra Jussien, Barry O’Sullivan: ''Trends in constraint programming.'' John Wiley and Sons: London/Newport Beach, 2007.
	* Thom Frühwirth, Slim Abdennadher: ''Constraint-Programmierung: Grundlagen und Anwendungen.'' Springer-Verlag: Berlin/Heidelberg, 1997, ISBN 3-540-60670-X		* Thom Frühwirth, Slim Abdennadher: ''Constraint-Programmierung: Grundlagen und Anwendungen.'' Springer-Verlag: Berlin/Heidelberg, 1997, ISBN 3-540-60670-X
	* Petra Hofstedt, Armin Wolf: ''Einführung in die Constraint-Programmierung.'' (Springer eXamen-press) Springer-Verlag: Berlin/Heidelberg, 2007, ISBN 978-3-540-23184-4		* Petra Hofstedt, Armin Wolf: ''Einführung in die Constraint-Programmierung.'' (Springer eXamen-press) Springer-Verlag: Berlin/Heidelberg, 2007, ISBN 978-3-540-23184-4

KlartextJan: /* Einzelnachweise Link archiviert */

2024-03-07T14:38:29Z

Einzelnachweise Link archiviert

← Nächstältere Version		Version vom 7. März 2024, 16:38 Uhr
Zeile 62:		Zeile 62:
	Die Constraint-imperative Programmierung vereinigt die beiden Paradigmen Constraintprogrammierung und [[imperative Programmierung]]. In imperativen Sprachen beschreibt der Programmierer, ''wie'' ein gegebenes Problem durch eine Sequenz von Anweisungen gelöst wird. Sie eignet sich besonders zur Modellierung von zeitlichen Abläufen. Dagegen konzentriert sich der Programmierer in der Constraintprogrammierung auf das ''Was'', d. h., er beschreibt das Problem durch deren Eigenschaften in Form von Constraints. Die Kombination der imperativen Programmierung mit deklarativen Constraints stellt somit eine besondere Herausforderung dar.<ref>Hofstedt, Wolf: ''Einführung in die Constraint-Programmierung.'' 2007, S. 185.</ref>		Die Constraint-imperative Programmierung vereinigt die beiden Paradigmen Constraintprogrammierung und [[imperative Programmierung]]. In imperativen Sprachen beschreibt der Programmierer, ''wie'' ein gegebenes Problem durch eine Sequenz von Anweisungen gelöst wird. Sie eignet sich besonders zur Modellierung von zeitlichen Abläufen. Dagegen konzentriert sich der Programmierer in der Constraintprogrammierung auf das ''Was'', d. h., er beschreibt das Problem durch deren Eigenschaften in Form von Constraints. Die Kombination der imperativen Programmierung mit deklarativen Constraints stellt somit eine besondere Herausforderung dar.<ref>Hofstedt, Wolf: ''Einführung in die Constraint-Programmierung.'' 2007, S. 185.</ref>

	Ein Beispiel für eine Constraint-imperative Programmiersprache ist Turtle.<ref>catamorph.de: {{Webarchiv\|url=http://catamorph.de/turtle/turtle.de.html ~~\|wayback=20160408134625~~ \|text=Turtle – eine constraint-imperative Programmiersprache \|archiv-bot=~~2019-03-11 01:55:55 InternetArchiveBot~~ }}</ref> Diese entstand als eine einfache imperative Basissprache und wurde zunächst um [[Funktionale Programmierung\|funktionale Konzepte]] wie Funktionen höherer Ordnung erweitert. Danach wurde sie mit vier wesentlichen Konzepten zur Constraint-Programmierung angereichert<ref>Hofstedt, Wolf: ''Einführung in die Constraint-Programmierung.'' 2007, S. 185–192.</ref>:		Ein Beispiel für eine Constraint-imperative Programmiersprache ist Turtle.<ref>catamorph.de: {{Webarchiv \|url=http://catamorph.de/turtle/turtle.de.html \|text=Turtle – eine constraint-imperative Programmiersprache \|wayback=20160408134625 \|archiv-bot=}}</ref> Diese entstand als eine einfache imperative Basissprache und wurde zunächst um [[Funktionale Programmierung\|funktionale Konzepte]] wie Funktionen höherer Ordnung erweitert. Danach wurde sie mit vier wesentlichen Konzepten zur Constraint-Programmierung angereichert<ref>Hofstedt, Wolf: ''Einführung in die Constraint-Programmierung.'' 2007, S. 185–192.</ref>:

	* Constraint-Variablen: Diese unterscheiden sich von „normalen“ imperativen Variablen, deren Werte durch Zuweisungen festgelegt werden, dadurch, dass ihre Werte durch Constraints festgelegt bzw. eingeschränkt werden. Constraint-Variablen werden auch als deklarative Variablen bezeichnet.		* Constraint-Variablen: Diese unterscheiden sich von „normalen“ imperativen Variablen, deren Werte durch Zuweisungen festgelegt werden, dadurch, dass ihre Werte durch Constraints festgelegt bzw. eingeschränkt werden. Constraint-Variablen werden auch als deklarative Variablen bezeichnet.

Wsfm: /* Constraint-Systeme */

2024-03-02T23:43:12Z

Constraint-Systeme

← Nächstältere Version		Version vom 3. März 2024, 01:43 Uhr
Zeile 36:		Zeile 36:
	* [[Lineare Optimierung]]: die [[Optimierung (Mathematik)\|Optimierung]] [[Lineare Abbildung\|linearer Zielfunktionen]] über einer Menge, die durch lineare [[Gleichung]]en und [[Ungleichung]]en eingeschränkt ist. Ein Algorithmus, der in der Praxis häufig zur Lösung solcher Probleme Anwendung findet, ist das [[Simplex-Verfahren]].		* [[Lineare Optimierung]]: die [[Optimierung (Mathematik)\|Optimierung]] [[Lineare Abbildung\|linearer Zielfunktionen]] über einer Menge, die durch lineare [[Gleichung]]en und [[Ungleichung]]en eingeschränkt ist. Ein Algorithmus, der in der Praxis häufig zur Lösung solcher Probleme Anwendung findet, ist das [[Simplex-Verfahren]].

	* [[Boolesche Variable\|Boolesche Constraints]]: ~~boolesche~~ Gleichungen, deren Variable entweder die Gültigkeit einer Aussage (true) oder deren Ungültigkeit (false) repräsentieren. Ein Löser für Boolesche Constraints ist grundlegend für alle Probleme, die als [[Aussagenlogik\|aussagenlogische]] Erfüllbarkeitsprobleme formuliert sind. Normalerweise unterstützt ein ~~boolescher~~ Constraint-Löser logische Operationen wie [[Negation]], [[Konjunktion (Logik)\|Konjunktion]], [[Disjunktion]], [[Implikation]] und [[Logische Äquivalenz\|Äquivalenz]].<ref>Hofstedt, Wolf: ''Einführung in die Constraint-Programmierung.'' 2007, S. 177.</ref>		* [[Boolesche Variable\|Boolesche Constraints]]: Boolesche Gleichungen, deren Variable entweder die Gültigkeit einer Aussage (true) oder deren Ungültigkeit (false) repräsentieren. Ein Löser für Boolesche Constraints ist grundlegend für alle Probleme, die als [[Aussagenlogik\|aussagenlogische]] Erfüllbarkeitsprobleme formuliert sind. Normalerweise unterstützt ein Boolescher Constraint-Löser logische Operationen wie [[Negation]], [[Konjunktion (Logik)\|Konjunktion]], [[Disjunktion]], [[Implikation]] und [[Logische Äquivalenz\|Äquivalenz]].<ref>Hofstedt, Wolf: ''Einführung in die Constraint-Programmierung.'' 2007, S. 177.</ref>

	* Finite-Domain-Constraints: Diese haben die Eigenschaft, dass den beteiligten Variablen von vornherein endliche Wertebereiche (engl. ''finite domains'') zugeordnet sind. Dieses Constraint-System wurde in der Forschung eingehend untersucht. Es hat in der Praxis große Bedeutung bei der Lösung [[Kombinatorik\|kombinatorischer]] Probleme, z. B. zur Behandlung von Planungs-, Diagnose- und Konfigurationsproblemen.<ref>Hofstedt, Wolf: ''Einführung in die Constraint-Programmierung.'' 2007, S. 57, 71.</ref>		* Finite-Domain-Constraints: Diese haben die Eigenschaft, dass den beteiligten Variablen von vornherein endliche Wertebereiche (engl. ''finite domains'') zugeordnet sind. Dieses Constraint-System wurde in der Forschung eingehend untersucht. Es hat in der Praxis große Bedeutung bei der Lösung [[Kombinatorik\|kombinatorischer]] Probleme, z. B. zur Behandlung von Planungs-, Diagnose- und Konfigurationsproblemen.<ref>Hofstedt, Wolf: ''Einführung in die Constraint-Programmierung.'' 2007, S. 57, 71.</ref>

Wsfm: /* Constraint-Systeme */

2024-03-02T23:40:17Z

Constraint-Systeme

← Nächstältere Version		Version vom 3. März 2024, 01:40 Uhr
Zeile 26:		Zeile 26:

	== Constraint-Systeme ==		== Constraint-Systeme ==
	Aus formaler Sicht stellen Constraints spezielle prädikatenlogische Formeln dar, mit deren Hilfe man Eigenschaften von Problemen und deren Lösung beschreibt.<ref>Für eine formale Definition von Constraints siehe Hofstedt, Wolf: ''Einführung in die Constraint-Programmierung.'' 2007, S. 54–55.</ref> Dazu gehören Gleichungen und Ungleichungen über Zahlen, aber auch andere Ausdrücke über Zahlen, [[Boolesche Algebra\|boolesche ~~Werten~~]] oder ~~beliebigen~~ ~~anderen~~ Mengen wie Buchstaben oder ~~Wörtern~~.		Aus formaler Sicht stellen Constraints spezielle prädikatenlogische Formeln dar, mit deren Hilfe man Eigenschaften von Problemen und deren Lösung beschreibt.<ref>Für eine formale Definition von Constraints siehe Hofstedt, Wolf: ''Einführung in die Constraint-Programmierung.'' 2007, S. 54–55.</ref> Dazu gehören Gleichungen und Ungleichungen über Zahlen, aber auch andere Ausdrücke über Zahlen, [[Boolesche Algebra\|boolesche Werte]] oder beliebige andere Mengen wie Buchstaben oder Wörter.

	Constraint-Löser funktionieren in der Regel nur auf einer speziellen Klasse von Constraints. Diese werden durch Constraint-Systeme klassifiziert. Dadurch lassen sich den Constraint-Systemen passende Lösungsmechanismen zuordnen.<ref>Hofstedt, Wolf: ''Einführung in die Constraint-Programmierung.'' 2007, S. 53–55.</ref>		Constraint-Löser funktionieren in der Regel nur auf einer speziellen Klasse von Constraints. Diese werden durch Constraint-Systeme klassifiziert. Dadurch lassen sich den Constraint-Systemen passende Lösungsmechanismen zuordnen.<ref>Hofstedt, Wolf: ''Einführung in die Constraint-Programmierung.'' 2007, S. 53–55.</ref>
Zeile 36:		Zeile 36:
	* [[Lineare Optimierung]]: die [[Optimierung (Mathematik)\|Optimierung]] [[Lineare Abbildung\|linearer Zielfunktionen]] über einer Menge, die durch lineare [[Gleichung]]en und [[Ungleichung]]en eingeschränkt ist. Ein Algorithmus, der in der Praxis häufig zur Lösung solcher Probleme Anwendung findet, ist das [[Simplex-Verfahren]].		* [[Lineare Optimierung]]: die [[Optimierung (Mathematik)\|Optimierung]] [[Lineare Abbildung\|linearer Zielfunktionen]] über einer Menge, die durch lineare [[Gleichung]]en und [[Ungleichung]]en eingeschränkt ist. Ein Algorithmus, der in der Praxis häufig zur Lösung solcher Probleme Anwendung findet, ist das [[Simplex-Verfahren]].

	* [[Boolesche Variable\|Boolesche Constraints]]: boolesche Gleichungen, deren ~~Variablen~~ entweder die Gültigkeit einer Aussage (true) oder deren Ungültigkeit (false) repräsentieren. Ein Löser für Boolesche Constraints ist grundlegend für alle Probleme, die als [[Aussagenlogik\|aussagenlogische]] Erfüllbarkeitsprobleme formuliert sind. Normalerweise unterstützt ein boolescher Constraint-Löser logische Operationen wie [[Negation]], [[Konjunktion (Logik)\|Konjunktion]], [[Disjunktion]], [[Implikation]] und [[Logische Äquivalenz\|Äquivalenz]].<ref>Hofstedt, Wolf: ''Einführung in die Constraint-Programmierung.'' 2007, S. 177.</ref>		* [[Boolesche Variable\|Boolesche Constraints]]: boolesche Gleichungen, deren Variable entweder die Gültigkeit einer Aussage (true) oder deren Ungültigkeit (false) repräsentieren. Ein Löser für Boolesche Constraints ist grundlegend für alle Probleme, die als [[Aussagenlogik\|aussagenlogische]] Erfüllbarkeitsprobleme formuliert sind. Normalerweise unterstützt ein boolescher Constraint-Löser logische Operationen wie [[Negation]], [[Konjunktion (Logik)\|Konjunktion]], [[Disjunktion]], [[Implikation]] und [[Logische Äquivalenz\|Äquivalenz]].<ref>Hofstedt, Wolf: ''Einführung in die Constraint-Programmierung.'' 2007, S. 177.</ref>

	* Finite-Domain-Constraints: Diese haben die Eigenschaft, dass den beteiligten Variablen von vornherein endliche Wertebereiche (engl. ''finite domains'') zugeordnet sind. Dieses Constraint-System wurde in der Forschung eingehend untersucht. Es hat in der Praxis große Bedeutung bei der Lösung [[Kombinatorik\|kombinatorischer]] Probleme, z. B. zur Behandlung von Planungs-, Diagnose- und Konfigurationsproblemen.<ref>Hofstedt, Wolf: ''Einführung in die Constraint-Programmierung.'' 2007, S. 57, 71.</ref>		* Finite-Domain-Constraints: Diese haben die Eigenschaft, dass den beteiligten Variablen von vornherein endliche Wertebereiche (engl. ''finite domains'') zugeordnet sind. Dieses Constraint-System wurde in der Forschung eingehend untersucht. Es hat in der Praxis große Bedeutung bei der Lösung [[Kombinatorik\|kombinatorischer]] Probleme, z. B. zur Behandlung von Planungs-, Diagnose- und Konfigurationsproblemen.<ref>Hofstedt, Wolf: ''Einführung in die Constraint-Programmierung.'' 2007, S. 57, 71.</ref>

Saure: /* Anwendungen */

2022-11-29T17:13:58Z

Anwendungen

← Nächstältere Version		Version vom 29. November 2022, 19:13 Uhr
Zeile 84:		Zeile 84:

	== Anwendungen ==		== Anwendungen ==
	Im wissenschaftlichen Bereich findet die Constraint-basierte Programmierung beispielsweise bei der Verarbeitung natürlicher Sprache, im [[Maschinengestütztes Beweisen\|maschinengestützten Beweisen]], in der Analyse von Programmen und in der [[Molekularbiologie]] Anwendung. In der industriellen Praxis sind typische Anwendungen Optimierungsprobleme und [[Scheduling]]-Aufgaben, [[Schaltkreis]]-Design und -Verifikation, graphische Systeme und [[Benutzerschnittstelle]]n.<ref>Petra Hofstedt: Kapitel ''Constraints.'' In: Günther Görz, Josef Schneeberger, Ute Schmid (Hrsg.): ''Handbuch der Künstlichen Intelligenz.'' 5. überarbeitete und aktualisierte Auflage. Oldenbourg Verlag: München, 2014, S. 206.</ref>		Im wissenschaftlichen Bereich findet die Constraint-basierte Programmierung beispielsweise bei der Verarbeitung natürlicher Sprache, im [[Maschinengestütztes Beweisen\|maschinengestützten Beweisen]], in der Analyse von Programmen und in der [[Molekularbiologie]] Anwendung. In der industriellen Praxis sind typische Anwendungen Optimierungsprobleme und [[Scheduling]]-Aufgaben, [[Integrierter Schaltkreis\|Schaltkreis]]-Design und -Verifikation, graphische Systeme und [[Benutzerschnittstelle]]n.<ref>Petra Hofstedt: Kapitel ''Constraints.'' In: Günther Görz, Josef Schneeberger, Ute Schmid (Hrsg.): ''Handbuch der Künstlichen Intelligenz.'' 5. überarbeitete und aktualisierte Auflage. Oldenbourg Verlag: München, 2014, S. 206.</ref>

	== Literatur ==		== Literatur ==

78.94.29.46: /* Constraints */

2022-06-30T12:14:16Z

Constraints

← Nächstältere Version		Version vom 30. Juni 2022, 14:14 Uhr
Zeile 10:		Zeile 10:
	Man kann zum Beispiel die Umrechnungsformel von [[Grad Celsius]] in [[Grad Fahrenheit]] als ein Constraint auffassen: <math>F = 1{,}8 \times C + 32</math>. Durch die Belegung der Variablen mit Werten wird das Constraint entweder erfüllt (true) oder nicht erfüllt (false). Die Umrechnung ist beispielsweise mit <math>F=68</math> und <math>C=20</math> erfüllt, während <math>F=1</math> und <math>C=1</math> das Constraint offensichtlich verletzt.		Man kann zum Beispiel die Umrechnungsformel von [[Grad Celsius]] in [[Grad Fahrenheit]] als ein Constraint auffassen: <math>F = 1{,}8 \times C + 32</math>. Durch die Belegung der Variablen mit Werten wird das Constraint entweder erfüllt (true) oder nicht erfüllt (false). Die Umrechnung ist beispielsweise mit <math>F=68</math> und <math>C=20</math> erfüllt, während <math>F=1</math> und <math>C=1</math> das Constraint offensichtlich verletzt.

	Das Constraint <math>X^2 \geq 0 \land X \in \mathbb{R}</math> ist unabhängig von einer Wertebelegung immer erfüllt, das Constraint <math>X^2 < 0</math> dagegen nie.<ref>Hofstedt, Wolf: ''Einführung in die Constraint-Programmierung.'' 2007, S. 51–52.</ref>		Das Constraint <math>X^2 \geq 0 \land X \in \mathbb{R}</math> ist unabhängig von einer Wertebelegung immer erfüllt, das Constraint <math>X^2 < 0 \land X \in \mathbb{R}</math> dagegen nie.<ref>Hofstedt, Wolf: ''Einführung in die Constraint-Programmierung.'' 2007, S. 51–52.</ref>

	Ein weiteres Beispiel ist ein [[pythagoreisches Tripel]], das von drei natürlichen Zahlen <math>x</math>, <math>y</math> und <math>z</math> gebildet wird, welche die Seitenlänge eines rechtwinkligen Dreiecks angeben. Eine Constraint-basierte Modellierung solcher Tripel über dem [[Definitionsbereich]] <math>\{ 1,\dots,100 \}</math> kann durch folgende Constraint-Konjunktion dargestellt werden:		Ein weiteres Beispiel ist ein [[pythagoreisches Tripel]], das von drei natürlichen Zahlen <math>x</math>, <math>y</math> und <math>z</math> gebildet wird, welche die Seitenlänge eines rechtwinkligen Dreiecks angeben. Eine Constraint-basierte Modellierung solcher Tripel über dem [[Definitionsbereich]] <math>\{ 1,\dots,100 \}</math> kann durch folgende Constraint-Konjunktion dargestellt werden:

78.94.29.46: /* Constraints */

2022-06-30T12:13:32Z

Constraints

← Nächstältere Version		Version vom 30. Juni 2022, 14:13 Uhr
Zeile 10:		Zeile 10:
	Man kann zum Beispiel die Umrechnungsformel von [[Grad Celsius]] in [[Grad Fahrenheit]] als ein Constraint auffassen: <math>F = 1{,}8 \times C + 32</math>. Durch die Belegung der Variablen mit Werten wird das Constraint entweder erfüllt (true) oder nicht erfüllt (false). Die Umrechnung ist beispielsweise mit <math>F=68</math> und <math>C=20</math> erfüllt, während <math>F=1</math> und <math>C=1</math> das Constraint offensichtlich verletzt.		Man kann zum Beispiel die Umrechnungsformel von [[Grad Celsius]] in [[Grad Fahrenheit]] als ein Constraint auffassen: <math>F = 1{,}8 \times C + 32</math>. Durch die Belegung der Variablen mit Werten wird das Constraint entweder erfüllt (true) oder nicht erfüllt (false). Die Umrechnung ist beispielsweise mit <math>F=68</math> und <math>C=20</math> erfüllt, während <math>F=1</math> und <math>C=1</math> das Constraint offensichtlich verletzt.

	Das Constraint <math>X^2 \geq 0, X \in \mathbb{R}</math> ist unabhängig von einer Wertebelegung immer erfüllt, das Constraint <math>X^2 < 0</math> dagegen nie.<ref>Hofstedt, Wolf: ''Einführung in die Constraint-Programmierung.'' 2007, S. 51–52.</ref>		Das Constraint <math>X^2 \geq 0 \land X \in \mathbb{R}</math> ist unabhängig von einer Wertebelegung immer erfüllt, das Constraint <math>X^2 < 0</math> dagegen nie.<ref>Hofstedt, Wolf: ''Einführung in die Constraint-Programmierung.'' 2007, S. 51–52.</ref>

	Ein weiteres Beispiel ist ein [[pythagoreisches Tripel]], das von drei natürlichen Zahlen <math>x</math>, <math>y</math> und <math>z</math> gebildet wird, welche die Seitenlänge eines rechtwinkligen Dreiecks angeben. Eine Constraint-basierte Modellierung solcher Tripel über dem [[Definitionsbereich]] <math>\{ 1,\dots,100 \}</math> kann durch folgende Constraint-Konjunktion dargestellt werden:		Ein weiteres Beispiel ist ein [[pythagoreisches Tripel]], das von drei natürlichen Zahlen <math>x</math>, <math>y</math> und <math>z</math> gebildet wird, welche die Seitenlänge eines rechtwinkligen Dreiecks angeben. Eine Constraint-basierte Modellierung solcher Tripel über dem [[Definitionsbereich]] <math>\{ 1,\dots,100 \}</math> kann durch folgende Constraint-Konjunktion dargestellt werden:

78.94.29.46: /* Constraints */

2022-06-30T12:12:14Z

Constraints

← Nächstältere Version		Version vom 30. Juni 2022, 14:12 Uhr
Zeile 10:		Zeile 10:
	Man kann zum Beispiel die Umrechnungsformel von [[Grad Celsius]] in [[Grad Fahrenheit]] als ein Constraint auffassen: <math>F = 1{,}8 \times C + 32</math>. Durch die Belegung der Variablen mit Werten wird das Constraint entweder erfüllt (true) oder nicht erfüllt (false). Die Umrechnung ist beispielsweise mit <math>F=68</math> und <math>C=20</math> erfüllt, während <math>F=1</math> und <math>C=1</math> das Constraint offensichtlich verletzt.		Man kann zum Beispiel die Umrechnungsformel von [[Grad Celsius]] in [[Grad Fahrenheit]] als ein Constraint auffassen: <math>F = 1{,}8 \times C + 32</math>. Durch die Belegung der Variablen mit Werten wird das Constraint entweder erfüllt (true) oder nicht erfüllt (false). Die Umrechnung ist beispielsweise mit <math>F=68</math> und <math>C=20</math> erfüllt, während <math>F=1</math> und <math>C=1</math> das Constraint offensichtlich verletzt.

	Das Constraint <math>X^2 \geq 0</math> ist unabhängig von einer Wertebelegung immer erfüllt, das Constraint <math>X^2 < 0</math> dagegen nie.<ref>Hofstedt, Wolf: ''Einführung in die Constraint-Programmierung.'' 2007, S. 51–52.</ref>		Das Constraint <math>X^2 \geq 0, X \in \mathbb{R}</math> ist unabhängig von einer Wertebelegung immer erfüllt, das Constraint <math>X^2 < 0</math> dagegen nie.<ref>Hofstedt, Wolf: ''Einführung in die Constraint-Programmierung.'' 2007, S. 51–52.</ref>

	Ein weiteres Beispiel ist ein [[pythagoreisches Tripel]], das von drei natürlichen Zahlen <math>x</math>, <math>y</math> und <math>z</math> gebildet wird, welche die Seitenlänge eines rechtwinkligen Dreiecks angeben. Eine Constraint-basierte Modellierung solcher Tripel über dem [[Definitionsbereich]] <math>\{ 1,\dots,100 \}</math> kann durch folgende Constraint-Konjunktion dargestellt werden:		Ein weiteres Beispiel ist ein [[pythagoreisches Tripel]], das von drei natürlichen Zahlen <math>x</math>, <math>y</math> und <math>z</math> gebildet wird, welche die Seitenlänge eines rechtwinkligen Dreiecks angeben. Eine Constraint-basierte Modellierung solcher Tripel über dem [[Definitionsbereich]] <math>\{ 1,\dots,100 \}</math> kann durch folgende Constraint-Konjunktion dargestellt werden:

Boehm: fix, typog

2022-04-20T09:23:00Z

fix, typog

← Nächstältere Version		Version vom 3. März 2024, 01:43 Uhr
Zeile 36:		Zeile 36:
	* [[Lineare Optimierung]]: die [[Optimierung (Mathematik)\|Optimierung]] [[Lineare Abbildung\|linearer Zielfunktionen]] über einer Menge, die durch lineare [[Gleichung]]en und [[Ungleichung]]en eingeschränkt ist. Ein Algorithmus, der in der Praxis häufig zur Lösung solcher Probleme Anwendung findet, ist das [[Simplex-Verfahren]].		* [[Lineare Optimierung]]: die [[Optimierung (Mathematik)\|Optimierung]] [[Lineare Abbildung\|linearer Zielfunktionen]] über einer Menge, die durch lineare [[Gleichung]]en und [[Ungleichung]]en eingeschränkt ist. Ein Algorithmus, der in der Praxis häufig zur Lösung solcher Probleme Anwendung findet, ist das [[Simplex-Verfahren]].

	* [[Boolesche Variable\|Boolesche Constraints]]: ~~boolesche~~ Gleichungen, deren Variable entweder die Gültigkeit einer Aussage (true) oder deren Ungültigkeit (false) repräsentieren. Ein Löser für Boolesche Constraints ist grundlegend für alle Probleme, die als [[Aussagenlogik\|aussagenlogische]] Erfüllbarkeitsprobleme formuliert sind. Normalerweise unterstützt ein ~~boolescher~~ Constraint-Löser logische Operationen wie [[Negation]], [[Konjunktion (Logik)\|Konjunktion]], [[Disjunktion]], [[Implikation]] und [[Logische Äquivalenz\|Äquivalenz]].<ref>Hofstedt, Wolf: ''Einführung in die Constraint-Programmierung.'' 2007, S. 177.</ref>		* [[Boolesche Variable\|Boolesche Constraints]]: Boolesche Gleichungen, deren Variable entweder die Gültigkeit einer Aussage (true) oder deren Ungültigkeit (false) repräsentieren. Ein Löser für Boolesche Constraints ist grundlegend für alle Probleme, die als [[Aussagenlogik\|aussagenlogische]] Erfüllbarkeitsprobleme formuliert sind. Normalerweise unterstützt ein Boolescher Constraint-Löser logische Operationen wie [[Negation]], [[Konjunktion (Logik)\|Konjunktion]], [[Disjunktion]], [[Implikation]] und [[Logische Äquivalenz\|Äquivalenz]].<ref>Hofstedt, Wolf: ''Einführung in die Constraint-Programmierung.'' 2007, S. 177.</ref>

	* Finite-Domain-Constraints: Diese haben die Eigenschaft, dass den beteiligten Variablen von vornherein endliche Wertebereiche (engl. ''finite domains'') zugeordnet sind. Dieses Constraint-System wurde in der Forschung eingehend untersucht. Es hat in der Praxis große Bedeutung bei der Lösung [[Kombinatorik\|kombinatorischer]] Probleme, z. B. zur Behandlung von Planungs-, Diagnose- und Konfigurationsproblemen.<ref>Hofstedt, Wolf: ''Einführung in die Constraint-Programmierung.'' 2007, S. 57, 71.</ref>		* Finite-Domain-Constraints: Diese haben die Eigenschaft, dass den beteiligten Variablen von vornherein endliche Wertebereiche (engl. ''finite domains'') zugeordnet sind. Dieses Constraint-System wurde in der Forschung eingehend untersucht. Es hat in der Praxis große Bedeutung bei der Lösung [[Kombinatorik\|kombinatorischer]] Probleme, z. B. zur Behandlung von Planungs-, Diagnose- und Konfigurationsproblemen.<ref>Hofstedt, Wolf: ''Einführung in die Constraint-Programmierung.'' 2007, S. 57, 71.</ref>

← Nächstältere Version		Version vom 20. April 2022, 11:23 Uhr
Zeile 8:		Zeile 8:
	Der Begriff [[Constraint]] bedeutet in etwa Zwang oder Nebenbedingung. Es handelt sich um spezielle [[Prädikatenlogik\|prädikatenlogische Formeln]], die Bedingungen oder Einschränkungen beschreiben. Im mathematischen Sinn sind damit auch [[Nebenbedingung]]en gemeint, wie sie beispielsweise bei der Lösung mathematischer [[Optimierung (Mathematik)\|Optimierungsprobleme]] Anwendung finden.		Der Begriff [[Constraint]] bedeutet in etwa Zwang oder Nebenbedingung. Es handelt sich um spezielle [[Prädikatenlogik\|prädikatenlogische Formeln]], die Bedingungen oder Einschränkungen beschreiben. Im mathematischen Sinn sind damit auch [[Nebenbedingung]]en gemeint, wie sie beispielsweise bei der Lösung mathematischer [[Optimierung (Mathematik)\|Optimierungsprobleme]] Anwendung finden.

	Man kann zum Beispiel die Umrechnungsformel von [[Grad Celsius]] in [[Grad Fahrenheit]] als ein Constraint auffassen: <math>F = 1,8 \times C + 32</math>. Durch die Belegung der Variablen mit Werten wird das Constraint entweder erfüllt (true) oder nicht erfüllt (false). Die Umrechnung ist beispielsweise mit <math>F=68</math> und <math>C=20</math> erfüllt, während <math>F=1</math> und <math>C=1</math> das Constraint offensichtlich verletzt.		Man kann zum Beispiel die Umrechnungsformel von [[Grad Celsius]] in [[Grad Fahrenheit]] als ein Constraint auffassen: <math>F = 1{,}8 \times C + 32</math>. Durch die Belegung der Variablen mit Werten wird das Constraint entweder erfüllt (true) oder nicht erfüllt (false). Die Umrechnung ist beispielsweise mit <math>F=68</math> und <math>C=20</math> erfüllt, während <math>F=1</math> und <math>C=1</math> das Constraint offensichtlich verletzt.

	Das Constraint <math>X^2 \geq 0</math> ist unabhängig von einer Wertebelegung immer erfüllt, das Constraint <math>X^2 < 0</math> dagegen nie.<ref>Hofstedt, Wolf: ''Einführung in die Constraint-Programmierung.'' 2007, S. 51–52.</ref>		Das Constraint <math>X^2 \geq 0</math> ist unabhängig von einer Wertebelegung immer erfüllt, das Constraint <math>X^2 < 0</math> dagegen nie.<ref>Hofstedt, Wolf: ''Einführung in die Constraint-Programmierung.'' 2007, S. 51–52.</ref>

	Ein weiteres Beispiel ist ein [[pythagoreisches Tripel]], das von drei natürlichen Zahlen <math>x</math>, <math>y</math> und <math>z</math> gebildet wird, welche die Seitenlänge eines rechtwinkligen Dreiecks angeben. Eine Constraint-basierte Modellierung solcher Tripel über dem [[Definitionsbereich]] <math>\{ 1,~~...~~,100 \}</math> kann durch folgende Constraint-Konjunktion dargestellt werden:		Ein weiteres Beispiel ist ein [[pythagoreisches Tripel]], das von drei natürlichen Zahlen <math>x</math>, <math>y</math> und <math>z</math> gebildet wird, welche die Seitenlänge eines rechtwinkligen Dreiecks angeben. Eine Constraint-basierte Modellierung solcher Tripel über dem [[Definitionsbereich]] <math>\{ 1,\dots,100 \}</math> kann durch folgende Constraint-Konjunktion dargestellt werden:

	:<math>x^2 + y^2 = z^2 \land x,y,z \in \{ 1,~~...~~,100\}</math>		:<math>x^2 + y^2 = z^2 \land x,y,z \in \{ 1, \dots,100\}</math>

	Eine mögliche Lösung ist das Tripel <math>(x,y,z) = (3,4,5)</math>.<ref>Petra Hofstedt: Kapitel ''Constraints.'' In: Günther Görz, Josef Schneeberger, Ute Schmid (Hrsg.): ''Handbuch der Künstlichen Intelligenz.'' 5. überarbeitete und aktualisierte Auflage. Oldenbourg Verlag: München, 2014, S. 205.</ref>		Eine mögliche Lösung ist das Tripel <math>(x,y,z) = (3,4,5)</math>.<ref>Petra Hofstedt: Kapitel ''Constraints.'' In: Günther Görz, Josef Schneeberger, Ute Schmid (Hrsg.): ''Handbuch der Künstlichen Intelligenz.'' 5. überarbeitete und aktualisierte Auflage. Oldenbourg Verlag: München, 2014, S. 205.</ref>
Zeile 46:		Zeile 46:

	=== Constraint-logische Programmierung ===		=== Constraint-logische Programmierung ===
	Die [[logische Programmierung]] arbeitet auf Basis einer [[Wissensdatenbank]], aus der die Lösung von Anfragen [[Deduktion\|hergeleitet]] wird. Bei der Auswertung von Anfragen werden die [[Prädikat (Logik)\|Prädikate]] mit Hilfe der [[Resolution (Logik)\|Resolution]] abgeleitet. Constraint-logische Programme unterscheiden sich von logischen Programmen nur insofern, als sie in den rechten Seiten der Klauseln und in Anfragen neben logischen Prädikaten auch Constraints zulassen, die mit Hilfe von Constraint-Lösern auf Erfüllbarkeit überprüft werden.<ref>Hofstedt, Wolf: ''Einführung in die Constraint-Programmierung.'' 2007, S. S. 127–133.</ref>		Die [[logische Programmierung]] arbeitet auf Basis einer [[Wissensdatenbank]], aus der die Lösung von Anfragen [[Deduktion\|hergeleitet]] wird. Bei der Auswertung von Anfragen werden die [[Prädikat (Logik)\|Prädikate]] mit Hilfe der [[Resolution (Logik)\|Resolution]] abgeleitet. Constraint-logische Programme unterscheiden sich von logischen Programmen nur insofern, als sie in den rechten Seiten der Klauseln und in Anfragen neben logischen Prädikaten auch Constraints zulassen, die mit Hilfe von Constraint-Lösern auf Erfüllbarkeit überprüft werden.<ref>Hofstedt, Wolf: ''Einführung in die Constraint-Programmierung.'' 2007, S. 127–133.</ref>

	Die [[Syntax]] Constraint-logischer Programme unterscheidet sich nicht wesentlich von logischen Programmen. Es sind lediglich auch Constraints in den rechten Seiten der Regeln und in den Anfragen zulässig. Während logische Prädikate weiterhin durch Unifikation behandelt werden, werden die zusätzlichen Constraints gesammelt, in den Constraint-Speicher übertragen und von einem Constraint-Löser behandelt. Constraint-logische Programme lassen oft verschiedene Constraint-Domänen (z. B. FD-Constraints, arithmetische Constraints oder boolesche Constraints) mit entsprechenden Lösungsverfahren zu, die dann beispielsweise in Form von Bibliotheken vorliegen.<ref>Petra Hofstedt: Kapitel ''Constraints.'' In: Günther Görz, Josef Schneeberger, Ute Schmid (Hrsg.): ''Handbuch der Künstlichen Intelligenz.'' 5. überarbeitete und aktualisierte Auflage. Oldenbourg Verlag: München, 2014, S. 221.</ref>		Die [[Syntax]] Constraint-logischer Programme unterscheidet sich nicht wesentlich von logischen Programmen. Es sind lediglich auch Constraints in den rechten Seiten der Regeln und in den Anfragen zulässig. Während logische Prädikate weiterhin durch Unifikation behandelt werden, werden die zusätzlichen Constraints gesammelt, in den Constraint-Speicher übertragen und von einem Constraint-Löser behandelt. Constraint-logische Programme lassen oft verschiedene Constraint-Domänen (z. B. FD-Constraints, arithmetische Constraints oder boolesche Constraints) mit entsprechenden Lösungsverfahren zu, die dann beispielsweise in Form von Bibliotheken vorliegen.<ref>Petra Hofstedt: Kapitel ''Constraints.'' In: Günther Görz, Josef Schneeberger, Ute Schmid (Hrsg.): ''Handbuch der Künstlichen Intelligenz.'' 5. überarbeitete und aktualisierte Auflage. Oldenbourg Verlag: München, 2014, S. 221.</ref>
Zeile 55:		Zeile 55:
	Die nebenläufige Constraint-logische Programmierung (engl. ''Concurrent Constraint Logic Programming'', CCLP) integriert das Konzept der [[Nebenläufigkeit]] in die Constraint-logische Programmierung. Nebenläufigkeit ist die Eigenschaft eines Systems, mehrere Berechnungen, [[Anweisung (Programmierung)\|Anweisungen]] oder [[Maschinenbefehl\|Befehle]] gleichzeitig ausführen zu können. Das System verzichtet dadurch auf [[Sequentialisierung]]. Dies ist dann möglich, wenn die betreffenden Aktionen voneinander kausal unabhängig sind, d. h. keine Aktion das Resultat einer anderen benötigt. Unabhängige Aktionen können entweder in beliebiger Reihenfolge sequentiell abgearbeitet werden oder echt [[Parallele Programmierung\|parallel]] auf mehreren Rechnern gleichzeitig ausgeführt werden.		Die nebenläufige Constraint-logische Programmierung (engl. ''Concurrent Constraint Logic Programming'', CCLP) integriert das Konzept der [[Nebenläufigkeit]] in die Constraint-logische Programmierung. Nebenläufigkeit ist die Eigenschaft eines Systems, mehrere Berechnungen, [[Anweisung (Programmierung)\|Anweisungen]] oder [[Maschinenbefehl\|Befehle]] gleichzeitig ausführen zu können. Das System verzichtet dadurch auf [[Sequentialisierung]]. Dies ist dann möglich, wenn die betreffenden Aktionen voneinander kausal unabhängig sind, d. h. keine Aktion das Resultat einer anderen benötigt. Unabhängige Aktionen können entweder in beliebiger Reihenfolge sequentiell abgearbeitet werden oder echt [[Parallele Programmierung\|parallel]] auf mehreren Rechnern gleichzeitig ausgeführt werden.

	Das Modell der nebenläufigen Constraint-Programmierung kann auch mit partiellen Informationen über Variablenbelegungen arbeiten. Statt konkreter Daten für Variablen können auch Bedingungen auf diesen festgelegt werden.<ref>Hofstedt, Wolf: ''Einführung in die Constraint-Programmierung.'' 2007, S. S. 141–162.</ref>		Das Modell der nebenläufigen Constraint-Programmierung kann auch mit partiellen Informationen über Variablenbelegungen arbeiten. Statt konkreter Daten für Variablen können auch Bedingungen auf diesen festgelegt werden.<ref>Hofstedt, Wolf: ''Einführung in die Constraint-Programmierung.'' 2007, S. 141–162.</ref>

	Eine multiparadigmatische Programmiersprache, die unter anderem deklarative, parallele und Constraint-basierte Ansätze vereint, ist beispielsweise [[Oz (Programmiersprache)\|Oz]].		Eine multiparadigmatische Programmiersprache, die unter anderem deklarative, parallele und Constraint-basierte Ansätze vereint, ist beispielsweise [[Oz (Programmiersprache)\|Oz]].