Programmazione a vincoli: differenze tra le versioni

Versione delle 19:03, 12 mar 2013

Versione attuale delle 06:59, 14 mar 2025

(14 versioni intermedie di 7 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==

Riga 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:

<sourcesyntaxhighlight lang=prolog>

sendmore(Digits) :-

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

Line 47 ⟶ 45:

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

labeling(Digits). % Inizia la ricerca della soluzione

</syntaxhighlight>

</source>

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é la soddisfabilità, 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] (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://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] (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)

==Voci correlate==

*[[Programmazione dichiarativa]]

*[[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}}

*{{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}}

{{Controllo di autorità}}

==Voci correlate==

{{portale|informatica}}

*[[Programmazione dichiarativa]]

*[[Programmazione imperativa]]

[[Categoria:Programmazione]]