Programmazione a vincoli: differenze tra le versioni

Versione delle 11:21, 1 set 2008

Versione attuale delle 06:59, 14 mar 2025

(28 versioni intermedie di 19 utenti non mostrate)

Riga 1:

{{NN|informatica|febbraio 2013}}

LaIn [[informatica]] la '''programmazione a vincoli''', detta anche '''programmazione con vincoli''' o '''constraint''' è un [[paradigma di programmazione]] dove le relazioni fra variabili possono essere dichiarate in forma di vincoli. I vincoli differiscono dalle primitive normalmente definite dagli altri linguaggi di programmazione per il fatto che non specificano azioni singole da eseguire passo-passo, ma piuttosto si limitano a specificare le proprietà di cui deve essere dotata la soluzione da trovare. I vincoli usati possono essere di vari tipi: quelli basati sul cosiddetto [[problema di soddisfacimento di vincoli]] (''Constraint satisfaction problem'' o ''CSP''), quelli risolvibili mediante [[Algoritmo del simplesso|l'algoritmo del Simplesso]] (''Simplex Algorithm'') ed altri. I vincoli da applicare possono essere forniti ''embedded'' nel linguaggio di programmazione, oppure in [[Libreria software|librerie]] separate.

La programmazione a vincoli iniziò come [[programmazione logica a vincoli]], introducendo vincoli integrati in un programma di tipo logico. Questa variante della programmazione logica fu opera di Jaffar e Lassez, che, nel 1987, svilupparono una classe di vincoli specificatamente progettata per essere usata nel linguaggio [[Prolog II]]. LaLe prime implementazioni di programmazione logica a vincoli furono [[Prolog III]], [[CLP(R)]], e [[CHIP (linguaggio)|CHIP]]. Attualmente esistono molti interpreti per programmi logici a vincoli, come per esempio [[GNU Prolog]].

A differenza dalla programmazione logica, i vincoli possono essere inseriti nella [[programmazione funzionale]], nella [[riscrittura]] e nei [[programmazione imperativa|linguaggi imperativi]]. Nella programmazione funzionale i vincoli sono implementati ad esempio nel [[linguaggio di programmazione multi-paradigma]] [[Oz (linguaggio)|Oz]]. Vincoli sono ''embedded'' (integrati) nel linguaggio imperativo [[Kaleidoscope (linguaggio)|Kaleidoscope]]. Nei linguaggi imperativi, tuttavia, i vincoli sono implementati principalmente mediante i cosiddetti ''constraint solving toolkits'', che sono [[Libreria software|librerie]] separate, fornite insieme al linguaggio. [http://www.ilog.com/products/cpoptimizer ILOG CP Optimizer], è un esempio è di queste librerie per [[C++]], [[Java (linguaggio di programmazione)|Java]] e [[.NET]].

==Programmazione logica a vincoli==

La programmazione a vincoli consiste nell'integrazione di vincoli all'interno di un linguaggio che funge da ''host''. I primi linguaggi usati per fungere da host furono linguaggi di tipo [[Programmazione logica|logico]], tanto che queste applicazioni vennero inizialmente chiamate ''programmazione logica a vincoli''. I due paradigmi condividono molte importanti caratteristiche, come le variabili logiche ed il [[backtracking]]. Attualmente la maggior parte delle implementazioni di Prolog includono una o più librerie per supportare la programmazione logica a vincoli. Le differenze fra programiprogrammi logici e programmi a vincoli è sostanzialmente determinata dallo stile usato per creare modelli di simulazione del mondo reale. A seconda dei casi uno dei due stili di programmazione risulta più semplice e "naturale" da adottare.

L'approccio su cui si fonda la programmazione a vincoli è cercare uno "stato" del "mondo" in cui un grande numero di vincoli sono contemporaneamente soddisfatti. Si assume che risolvere un "problema" equivalga a trovare un "mondo possibile" descritto da un numero (inizialmente sconosciuto) di variabili. Il programma va alla ricerca dei valori che, attribuiti alle variabili, meglio definiscono il "mondo" soggetto ai vincoli imposti.

Line 13 ⟶ 14:

Lista di alcuni linguaggi di programmazione logica a vincoli:

*[http://www.probp.com/ B-Prolog] (Basato su Prolog, proprietario)

*[http://www.cosytec.com/production_scheduling/chip/optimization_product_chip.htm CHIP V5] {{Webarchive|url=https://web.archive.org/web/20080102081118/http://www.cosytec.com/production_scheduling/chip/optimization_product_chip.htm |date=2 gennaio 2008 }} (Basato su Prolog, include anche C++ e librerie C, proprietario)

*[http://clip.dia.fi.upm.es/Software/Ciao/ Ciao Prolog] (Basato su Prolog, free: GPL/LGPL)

*[[ECLiPSe]] (Basato su Prolog, open source)

*[httphttps://www.sics.se/isl/sicstuswww/site/index.html SICStus] (Basato su Prolog, proprietario)

*[[GNU Prolog]]

*[{{cita web | 1 = http://www.ncc.up.pt/~vsc/Yap/documentation.html#SEC91 | 2 = YAP Prolog] | accesso = 9 gennaio 2008 | urlarchivio = https://web.archive.org/web/20060418113348/http://www.ncc.up.pt/~vsc/Yap/documentation.html#SEC91 | dataarchivio = 18 aprile 2006 | urlmorto = sì }}

*[[SWI Prolog]] free, basato su Prolog, contiene molte librerie di risoluzione vincoli

==Domini di applicazione==

I vincoli usati nella programmazione a vincoli appartengono tipicamente ad alcuni specifici [[Dominio (matematica)|domini]], fra cui:

*Domini [[Variabile booleana|logici]], in cui si applicano soltanto vincoli che possono assumere valori vero/falso.

*Domini [[Numero intero|interi]] e domini [[Numero razionale|razionali]].

*Domini [[Algebra lineare|lineari]], dove sono analizzate e descritte soltanto [[Funzione lineare|funzioni lineari]] (sebbene esistano anche approcci a [[Funzione non lineare|funzioni non lineari]]).

*Domini [httphttps://it.wiktionary.org/wiki/:finito finiti], dove i vincoli sono definiti su [[Insieme finito|insiemi finiti]].

*Domini misti, comprendenti due o più dei precedenti.

I domini finiti sono uno dei campi in cui la programmazione a vincoli ha avuto maggiore successo. In alcune aree (come la [[ricerca operativa]]) la programmazione a vincoli è praticamente tutta basata sui domini finiti. Gli algoritmi risolutori sui domini finiti sono utili per risolvere [[Problema di soddisfacimento di vincoli|problemi di soddisfacimento di vincoli]], e si basano spesso sulla cosiddetta [[consistenza locale]], o su una delle sue approssimazioni.

La sintassi per esprimere vincoli su domini finiti dipende dal linguaggio ''host''. L'esempio che segue è un esempio di programma [[Prolog]] che risolve il classico ''puzzle'' dei programmi di programmazione a vincoli logici, noto come SEND+MORE=MONEY:

<syntaxhighlight lang=prolog>

sendmore(Digits) :-

Digits = [S,E,N,D,M,O,R,YE], % Crea le variabili

Digits '''::''' [0..9], % Associa il dominio alle variabili

S '''#\=''' 0, % Vincolo: S deve essere diverso da 0

M '''#\=''' 0,

'''alldifferent'''(Digits), % Tutti gli elementi devono assumere valori diversi

1000*S + 100*E + 10*N + D % Altri vincoli

+ 1000*M + 100*O + 10*R + E

'''#=''' 10000*M + 1000*O + 100*N + 10*E + Y,

'''labeling'''(Digits). % Inizia la ricerca della soluzione

</syntaxhighlight>

L'[[Interprete (informatica)|interprete]] crea una variabile per ciascuna lettera del puzzle. Il simbolo <code>::</code> è usato per specificare il dominio di queste variabili, in modo da consentire il range di valori {0,1,2,3, ..., 9}. I vincoli S#\=0 and M#\=0 significano che queste due variabili non possono assumere il valore zero. Quando l'interprete elabora ed applica questi vincoli, restringe i domini di queste due variabili rimuovendo da essi il valore 0. Poi viene elaborato il vincolo <code>alldifferent(Digits)</code>, che non produce la riduzione di alcun dominio, ma è semplicemente memorizzato. L'ultimo vincolo impone che i digit assegnati alle lettere devono essere tali che l'espressione "SEND+MORE=MONEY" rimanga valida quando a ciascuna lettera venga sostituito il proprio corrispondente digit. Dall'analisi di questo vincolo, mediante un'operazione di [[inferenza]], il programma ''solver'' deduce che M=1. Di conseguenza tutti i vincoli precedentemente memorizzati, e contenenti la variabile M, sono riesaminati: nell'esempio, mediante la [[propagazione dei vincoli|propagazione del vincolo]] (''constraint propagation'') sul vincolo <code>alldifferent</code>, il valore 1 viene rimosso dal dominio di tutte le altre variabili. La propagazione del vincolo può risolvere il problema riducendo tutti i domini ad un singolo valore, oppure arrivare a dimostrare che il problema non ammette soluzioni, riducendo il dominio ad un insieme vuoto. Inoltre può anche concludersi senza dimostrare nèné la soddisfabilità, nèné l'insoddisfabilità del problema.

I letterali etichettati con '''labeling''' sono usati per avviare l'effettiva ricerca di una soluzione.

==Programmazione a vincoli in linguaggi imperativi==

La programmazione a vincoli è possibile anche con alcuni linguaggi [[programmazione imperativa|imperativi]] utilizzando librerie separate. Alcune fra le più popolari librerie sono:

*[http://choco.sourceforge.net/ Choco] ([[Java]] librerie Java, free: X11 style)

*[http://www.comet-online.org/ Comet] {{Webarchive|url=https://web.archive.org/web/20080112041458/http://www.comet-online.org/ |date=12 gennaio 2008 }} (Librerie free binarie in stile [[C (linguaggio)|C]], disponibili per uso non commerciale).

*[http://choco.sourceforge.net/ Choco] ([[Java]] librerie, free: X11 style)

*[http://www.comet-online.org/ Comet] (Librerie free binarie in stile [[C (linguaggio)|C]], disponibili per uso non commerciale).

*[http://www.research.microsoft.com/~youssefh/Disolver/Disolver.mht Disolver] (librerie proprietarie per [[C++]])

*[http://www.gecode.org/ Gecode] (Librerie C++ library, free: X11 style)

*[https://web.archive.org/web/20080113070848/http://www.gecode.org/gecodej/ Gecode/J] (Java, Gecode, free: X11 style)

*[http://www.ilog.com/products/cpoptimizer/ ILOG CP Optimizer] (Librerie per C++, Java, .NET, proprietarie)

*[https://web.archive.org/web/20080204020451/http://www.ilog.com/products/cp/ ILOG CP] (Librerie C++, proprietarie)

*[http://jopt.sourceforge.net/ JOpt] (Librerie [[Java]] librerie, free)

*[http://www.koalog.com/ Koalog Constraint Solver] (Java, proprietarie)

*[[Minion (solver)|Minion]] (C++, GPL)

*[http://labix.org/python-constraint python-constraint] (Librerie per [[Python]] e GPL)

==Collegamenti esterni==

*{{en}}[http://kti.ms.mff.cuni.cz/~bartak/constraints/index.html On-Line Guide to Constraint Programming]

*{{en}}[http://pubsonline.informs.org/feature/pdfs/0092.2102.01.3106.29.pdf Program Does Not Equal Program: Constraint Programming and its Relationship to Mathematical Programming]

*{{en}}[http://www.mozart-oz.org/ Mozart] ([[Oz programming language|Oz]] based, Free software: X11 style)

*{{en}}[http://www.4c.ucc.ie Cork Constraint Computation Centre (4C)]

*{{en}}[http://www.cr2g.org Constraint Research and Reading Group (UTEP)]

==Voci correlate==

Line 78 ⟶ 67:

*[[Programmazione imperativa]]

==Altri progetti==

{{interprogetto}}

==Collegamenti esterni==

]]

*{{en}}[cita web|http://kti.ms.mff.cuni.cz/~bartak/constraints/index.html |On-Line Guide to Constraint Programming]|lingua=en}}

[[Categoria:Programmazione]]

*{{en}}[cita web|1=http://pubsonline.informs.org/feature/pdfs/0092.2102.01.3106.29.pdf |2=Program Does Not Equal Program: Constraint Programming and its Relationship to Mathematical Programming]|lingua=en|accesso=9 gennaio 2008|urlarchivio=https://web.archive.org/web/20070212223917/http://pubsonline.informs.org/feature/pdfs/0092.2102.01.3106.29.pdf|dataarchivio=12 febbraio 2007|urlmorto=sì}}

*{{en}}[http://www.mozart-oz.org/ Mozart] ([[Oz programming language|Oz]] based, Free software: X11 style)

*{{en}}[cita web|http://www.4c.ucc.ie |Cork Constraint Computation Centre (4C)]|lingua=en}}

*{{en}}[cita web|1=http://www.cr2g.org |2=Constraint Research and Reading Group (UTEP)]|lingua=en|urlmorto=sì}}

{{Paradigmi di programmazione}}

[[de:Constraintprogrammierung]]

{{Controllo di autorità}}

[[en:Constraint programming]]

{{portale|informatica}}

[[es:Programación con restricciones]]

[[fr:Programmation par contraintes]]

[[Categoria:Programmazione]]

[[gl:Programación con restricións]]

[[ja:制約プログラミング]]

[[pt:Programação com restrições]]