|
Size: 6419
Comment:
|
Size: 12635
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 1: | Line 1: |
| = Corso di INFORMATICA = '''Corso di Laurea in Matematica''' ---- [[Anchor(TOP)]] [[BR]] |
#acl EditorsGroup:read,write All:read = Official Problem Suite = == Problem List - Model & Solve and System Track == <<BR>> ||<tablewidth="1024px" tableheight="421px">'''Nr''' ||'''Name''' ||'''Author(s)''' ||'''Type''' ||'''Complexity''' ||'''Domain''' ||'''Problem Description''' ||'''Sample Instances''' ||'''Checker''' || '''ASP-Core-2 encoding''' || ||N01 ||Permutation Pattern Matching ||Martin Lackner, Andreas Pfandler ||Search ||NP ||Combinatorial ||[[https://www.mat.unical.it/aspcomp2013/FinalProblemDescriptions/PermutationPatternMatching|view]] || [[https://www.mat.unical.it/aspcomp2013/files/PPM-samples.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/permutation_pattern_matching-checker.zip|download]] || [[attachment:Permutation-Pattern-Matching-ENCODING.asp|Permutation Pattern Matching]] || ||N02 ||Valves Location Problem ||Andrea Peano ||Optimization ||Beyond NP ||Combinatorial ||[[https://www.mat.unical.it/aspcomp2013/FinalProblemDescriptions/ValvesLocation|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/samples/valves_location_problem-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/valves_location_problem-checker.zip|download]] || [[attachment:Valves-Location-Problem-ENCODING.asp|Valves Location Problem]] || ||N03 ||Rotating Workforce Scheduling ||Francesco Calimeri, Thomas Krennwallner, Nysret Musliu ||Search || ||Scheduling ||[[https://www.mat.unical.it/aspcomp2013/RotatingWorkforceScheduling|view]] || || || - || ||N04 ||Connected Maximum-density Still Life ||Christian Drescher ||Optimization ||Beyond NP ||AI ||[[https://www.mat.unical.it/aspcomp2013/ConnectedMaximumDensityStillLife|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/samples/still_life-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/still_life-checker.zip|download]] || [[attachment:Connected-Maximum-density-Still-Life-ENCODING.asp|Connected Maximum-density Still Life]] || ||N05 ||Graceful Graphs ||Christian Drescher ||Search ||NP ||Graph ||[[https://www.mat.unical.it/aspcomp2013/GracefulGraphs|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/samples/graceful_graphs-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/graceful_graphs-checker.zip|download]] || [[attachment:Graceful-Graphs-ENCODING.asp|Graceful Graphs]] || ||N06 ||Bottle Filling Problem ||Wolfgang Faber ||Search || ||Combinatorial ||[[https://www.mat.unical.it/aspcomp2013/BottleFillingProblem|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/samples/bottle_filling-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/bottle_filling-checker.zip|download]] || [[attachment:Bottle-Filling-Problem-ENCODING.asp|Bottle Filling Problem]] || ||N07 ||Nomystery ||Giovambattista Ianni, Carlos Linares López*, Hootan Nakhost* ||Search || ||Planning ||[[https://www.mat.unical.it/aspcomp2013/Nomystery|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/samples/nomystery-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/nomystery-checker.zip|download]] || [[attachment:Nomystery-ENCODING.asp|Nomystery]] || ||N08 ||Sokoban ||Giovambattista Ianni, Wolfgang Faber*, Carlos Linares López* ||Search || ||Planning ||[[https://www.mat.unical.it/aspcomp2013/Sokoban|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/samples/sokoban-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/sokoban-checker.zip|download]] || [[attachment:Sokoban-ENCODING.asp|Sokoban]] || ||N09 ||Ricochet Robots ||Julius Höfler, Martin Gebser, Philipp Obermeier, Roland Kaminski, Torsten Schaub ||Search || ||Puzzle ||[[https://www.mat.unical.it/aspcomp2013/RicochetRobot|view]] || [[https://www.mat.unical.it/aspcomp2013/files/ricochetSampleInstances.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/ricochet_robot-checker.zip|download]] || [[attachment:Ricochet-Robots-ENCODING.asp|Ricochet Robots]] || ||O10 ||Crossing Minimization ||Carmine Dodaro, Graeme Gange*, Peter Stuckey* ||Optimization ||Beyond NP ||Graph ||[[https://www.mat.unical.it/aspcomp2013/FinalProblemDescriptions/CrossingMinimization|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/samples/crossing_minimization-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/crossing_minimization-checker.zip|download]] || [[attachment:Crossing-Minimization-ENCODING.asp|Crossing Minimization]] || ||O11 ||Reachability ||Carmine Dodaro, Giorgio Terracina* ||Query ||P ||Graph ||[[https://www.mat.unical.it/aspcomp2013/FinalProblemDescriptions/Reachability|view]] || || || [[attachment:Reachability-ENCODING.asp|Reachability]] || ||O12 ||Strategic Companies ||Mario Alviano, Marco Maratea*, Francesco Ricca* ||Query ||Beyond NP ||AI ||[[https://www.mat.unical.it/aspcomp2013/FinalProblemDescriptions/StrategicCompanies|view]] ||[[https://www.mat.unical.it/ aspcomp2013/files/samples/strategic_companies-sample.zip|download]] || || [[attachment:Strategic-Companies-ENCODING.asp|Strategic Companies]] || ||O13 ||Solitaire ||Marcello Balduccini, Yuliya Lierler* ||Search ||NP ||Puzzle ||[[https://www.mat.unical.it/aspcomp2013/Solitaire|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/samples/solitaire_sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/solitaire-checker.zip|download]] || [[attachment:Solitaire-ENCODING.asp|Solitaire]] || ||O14 ||Weighted-Sequence Problem ||Marcello Balduccini, Yuliya Lierlier, Shaden Smith ||Search ||NP ||Database ||[[https://www.mat.unical.it/aspcomp2013/WeightedSequenceProblem|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/samples/weighted_sequence-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/weighted_sequence-checker.zip|download]] || [[attachment:Weighted-Sequence-Problem-ENCODING.asp|Weighted-Sequence Problem]] || ||O15 ||Stable Marriage ||Mario Alviano, Carmine Dodaro, Francesco Ricca ||Search ||P ||Graph ||[[https://www.mat.unical.it/aspcomp2013/StableMarriage|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/samples/stablemarriage-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/stable_marriage-checker.zip|download]] || [[attachment:Stable-Marriage-ENCODING.asp|Stable Marriage]] || ||O16 ||Incremental Scheduling ||Marcello Balduccini, Yuliya Lierler* ||Search ||NP ||Scheduling ||[[https://www.mat.unical.it/aspcomp2013/IncrementalScheduling|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/samples/incremental_scheduling-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/incremental-scheduling-checker.zip|download]] || [[attachment:Incremental-Scheduling-ENCODING.asp|Incremental Scheduling]] || |
| Line 10: | Line 24: |
| [[Anchor(TOC)]] [[TableOfContents]] ---- [[Anchor(docente)]] == Docente == Applicazioni avanzate nei più svariati ambiti spingono oggi verso un utilizzo dei calcolatori (finalmente) per rispondere ai problemi con soluzioni che gli esseri umani non sono in grado di trovare (non facilmente, almeno). [[BR]] Sistemi intelligenti sono già impiegati oggi in svariati ambiti: controllo di processi industriali, controllo del traffico aereo, commercio elettronico, robotica, grid computing, applicazioni mediche, giochi, intrattenimento, e oltre. [[BR]] I sistemi di elaborazione sono inoltre sempre più estesi, e la realtà apre quindi naturalmente alla possibilità di realizzare sistemi costituiti, gestiti o coadiuvati da una pluralità di entità autonome, chiamate agenti, che interagiscono fra loro in ambienti complessi. Essi sono già di fatto dei sistemi multi-agente, essendo costituiti da componenti collocate in un ambiente, autonome e sociali. [[BR]] [#TOP Top of Page] [[BR]] [[Anchor(obiettivi)]] == Obiettivi del Corso == ''[Passibile di modifiche]'' [[BR]] Il corso si propone di fornire le nozioni fondamentali per la comprensione e la progettazione di sistemi che utilizzano tecniche di Intelligenza Artificiale nel senso più ampio, e in particolare affrontare i problemi tipici dell'ingegneria del software orientata agli agenti. [[BR]] Il corso si sofferma (ma non solo) sui metodi per la progettazione di agenti capaci di prendere decisioni razionali, e metodi per la progettazione di sistemi che prevedono la presenza di più agenti, in grado di comunicare e interagire. [[BR]] Alla fine del corso gli studenti dovrebbero acquisire la capacità di progettare, ed eventualmente sviluppare, sistemi intelligenti basati su agenti. [[BR]] [#TOP Top of Page] [[BR]] [[Anchor(prerequisiti)]] == Prerequisiti == Sono indispensabili conoscenze di base di informatica e di programmazione avanzata. Sono utili conoscenze di base di matematica, logica, intelligenza artificiale. [[BR]] [#TOP Top of Page] [[BR]] [[Anchor(materiale)]] == Testi e Materiale Didattico == === Testi consigliati === ''Testi'' * S. Russell, P. Norvig, "Intelligenza artificiale. Un approccio moderno" Volumi 1 e 2. Pearson Education Italia, 2005. [http://aima.cs.berkeley.edu/ link] * ''In alternativa'': S. Russell, P. Norvig, "Artificial Intelligence: A modern approach", Prentice Hall, Englewood Cliffs, NJ, 2nd ed., 1995. [http://aima.cs.berkeley.edu/ link] * Matt Ginsberg, "Essentials of Artificial Intelligence", Morgan Kaufmann Ed., 1993. [http://cirl.uoregon.edu/ginsberg/ link al sito dell'autore] * M.Ghallab, D. Nau, P. Traverso, "Automated Planning - Theory and Practice", Morgan Kaufmann Ed., 2004. [http://www.laas.fr/planning/ link] ''Varie e sparse'' * D. C. Dennett, D. R. Hofstadter, "L'io della mente. Fantasie e riflessioni sul se' e sull'anima", Adelphi Ed., 1997. [http://en.wikipedia.org/wiki/The_Mind's_I link a wikipedia] * D. R. Hofstadter, "Goedel, Escher, Bach: un'eterna ghirlanda brillante", Adelphi Ed., 1990. [http://en.wikipedia.org/wiki/Goedel_Escher_Bach link a wikipedia] |
|
| Line 77: | Line 26: |
| === Materiale Didattico, Links, Varie ed Eventuali === ''Lucidi'' * [attachment:chapter01.pdf AI e agenti: introduzione] (aprile 2009) * [attachment:chapter02.pdf Agenti: razionalità, ambienti, tipologie] (aprile 2009) * [attachment:chapter03.pdf Problem Solving e Ricerca] (maggio 2009) * [attachment:chapter07.pdf Agenti Logici] (maggio 2009) * [attachment:chapter11.pdf Planning: (breve) introduzione] (maggio 2009) * [attachment:chapter11a-dlvK.pdf Planning: K action language e DLV^K] * [attachment:chapter22.pdf Comunicazione e Linguaggio] (maggio 2009) * [attachment:chapter22a-AgentCommunication.pdf Comunicazione tra Agenti] (maggio 2009) * [attachment:Multi-Agent-Interactions.pdf Interazioni multi agente] (giugno 2009) ## * [attachment:200705-Ricca-SeminarioOntoDLP.pdf OntoDLP] - Lucidi del seminario 2007 ''Tutorial'' * [attachment:JADETutorial_FIPA.pdf FIPA] (reperibile su [http://jade.tilab.com/ http://jade.tilab.com/]) * [attachment:JADETutorial_Programming.pdf Jade - Programming] (reperibile su [http://jade.tilab.com/ http://jade.tilab.com/]) * [attachment:JADEProgramming-Tutorial-for-beginners.pdf Utilizzare Jade] (reperibile su [http://jade.tilab.com/ http://jade.tilab.com/]) ''Links'' * [http://www.fipa.org/ FIPA] * [http://www.fipa.org/ JADE] * [http://www.agentlink.org/ agentlink.org] ''Ringraziamenti'' [http://aima.cs.berkeley.edu/ Stuart Russell e Peter Norvig] - [http://www.wfaber.com Wolfgang Faber] - [http://www.kr.tuwien.ac.at/staff/eiter/ Thomas Eiter] e [http://www.kr.tuwien.ac.at/staff/michael/ Michael Fink] - [http://www.mat.unical.it/ricca/ Francesco Ricca] e [mailto:gallucci@exeura.it Lorenzo Gallucci] - [http://staff.unak.is/not/yuan/ Tangming Yuan] [[BR]] [#TOP Top of Page] [[BR]] [[Anchor(prerequisiti)]] == Progetti, Esercizi, Elaborati == * [attachment:2007-Aspirapolvere.jar Aspirapolvere] [Maggio 2007 - Archivio eseguibile java (.jar)] - Simulazione di un agente aspirapolvere. L'agente si muove in un ambiente inizialmente sconosciuto, senza alcuna indicazione sulla posizione di eventuali ostacoli, ne' sullo stato del pavimento. Il suo scopo e' pulire la stanza (a meno di aree irraggiungibili) nel minor tempo possibile, e tornare nel punto di partenza. L'agente e' stato realizzato da [mailto:sirianni.marco@yahoo.it Marco Sirianni] e [mailto:saverio_vescio@yahoo.it Saverio Vescio]. * [attachment:2007-SistemiIntelligenti-ProgettoFinale.pdf SPECIFICHE del progetto di fine corso - A.A. 2006/2007] [Giugno 2007 - File in formato .pdf] |
== Problem List - System Track only == <<BR>> ||<tablewidth="1024px" tableheight="421px">'''Nr''' ||'''Name''' ||'''Author(s)''' ||'''Type''' ||'''Complexity''' ||'''Domain''' ||'''ASP-Core-2 Encoding''' ||'''Problem Description''' ||'''Sample Instances''' ||'''Checker''' || '''ASP-Core-2 encoding''' || ||N17 ||Qualitative Spatial Reasoning ||Jason Jingshi Li ||Search ||NP ||Formal logic || ||[[https://www.mat.unical.it/aspcomp2013/FinalProblemDescriptions/QualitativeSpatialTemporalReasoning|view]] || ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/qualitative_spatial_reasoning-checker.zip|download]]|| [[attachment:Qualitative-Spatial-Reasoning-ENCODING.asp|Qualitative Spatial Reasoning]] || ||N18 ||Chemical Classification ||Despoina Magka ||Search ||P ||Natural Sciences || ||[[https://www.mat.unical.it/aspcomp2013/ChemicalClassification|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/samples/chemical_classification-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/chemical_classification-checker.zip|download]]|| [[attachment:Chemical-Classification-ENCODING.asp|Chemical Classification]] || ||N19 ||Abstract Dialectical Frameworks Well-founded Model ||Stefan Ellmauthaler, Johannes Wallner ||Optimization || ||Formal logic || ||[[https://www.mat.unical.it/aspcomp2013/AbstractDialecticalFrameworks|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/samples/abstract_dialectical_frameworks-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/abstract_dialectical_frameworks-checker.zip|download]]|| [[attachment:Abstract-Dialectical-Frameworks-Well-founded-Model-ENCODING.asp|Abstract Dialectical Frameworks Well-founded Model]] || ||N20 ||Visit-all ||Giovambattista Ianni,Nir Lipovetzky*, Carlos Linares López* ||Search || ||Planning || ||[[https://www.mat.unical.it/aspcomp2013/VisitAll|view]] || [[https://www.mat.unical.it/aspcomp2013/files/Visitall-samples.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/visit_all-checker.zip|download]]|| [[attachment:Visit-all-ENCODING.asp|Visit-all]] || ||N21 ||Complex Optimization of Answer Sets ||Martin Gebser, Roland Kaminski, Torsten Schaub ||Search || ||Synthetic || ||[[https://www.mat.unical.it/aspcomp2013/ComplexOptimizationAnswerSets|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/samples/complex_optimization-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/complex_optimization-checker.zip|download]]|| [[attachment:Complex-Optimization-of-Answer-Sets-ENCODING.asp|Complex Optimization of Answer Sets]] || ||O22 ||Knight Tour with Holes ||Francesco Calimeri, Neng-Fa Zhou* ||Search ||NP ||Puzzle || ||[[https://www.mat.unical.it/aspcomp2013/KnightTour|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/samples/knight_tour-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/knight_tour-checker.zip|download]]|| [[attachment:Knight-Tour-with-Holes-ENCODING.asp|Knight Tour with Holes]] || ||O23 ||Maximal Clique Problem ||Guenther Charwat, Martin Kronegger, Johan Wittocx* ||Optimization ||Beyond NP ||Graph || ||[[https://www.mat.unical.it/aspcomp2013/MaximalClique|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/samples/maximal_clique-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/maximal_clique-checker.zip|download]]|| [[attachment:Maximal-Clique-Problem-ENCODING.asp|Maximal Clique Problem]] || ||O24 ||Labyrinth ||Carmine Dodaro, Giovambattista Ianni, Martin Gebser* ||Search ||NP ||Puzzle || ||[[https://www.mat.unical.it/aspcomp2013/Labyrinth|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/samples/labyrinth-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/labyrinth-checker.zip|download]]|| [[attachment:Labyrinth-ENCODING.asp|Labyrinth]] || ||O25 ||Minimal Diagnosis ||Marcello Balduccini, Martin Gebser* ||Search ||Beyond NP ||Diagnosis || ||[[https://www.mat.unical.it/aspcomp2013/MinimalDiagnosis|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/samples/minimal_diagnosis-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/minimal_diagnosis-checker.zip|download]]|| [[attachment:Minimal-Diagnosis-ENCODING.asp|Minimal Diagnosis]] || ||O26 ||Hanoi Tower ||Gayathri Namasivayam, Miroslaw Truszczynski, Shaden Smith, Alex Westlund ||Search ||NP ||AI || ||[[https://www.mat.unical.it/aspcomp2013/HanoiTower|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/samples/hanoi_tower-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/hanoi_tower-checker.zip|download]]|| [[attachment:Hanoi-Tower-ENCODING.asp|Hanoi Tower]] || ||O27 ||Graph Colouring ||Johannes Wallner, Marcello Balduccini*, Yuliya Lierler* ||Search ||NP ||Graph || ||[[https://www.mat.unical.it/aspcomp2013/GraphColouring|view]] ||[[https://www.mat.unical.it/aspcomp2013/files/samples/graph_colouring-sample.zip|download]] ||[[https://www.mat.unical.it/aspcomp2013/files/checkers/graph_colouring-checker.zip|download]]|| [[attachment:Graph-Colouring-ENCODING.asp|Graph Colouring]] || |
| Line 114: | Line 42: |
| [[BR]] | |
| Line 116: | Line 43: |
| [#TOP Top of Page] | |
| Line 118: | Line 44: |
| ---- [[Anchor(docente)]] == Docente == '''Francesco Calimeri''' [http://www.mat.unical.it/calimeri link alla home page] [[BR]] Dipartimento di Matematica, Università della Calabria, 87036 Rende (CS). [[BR]] Ufficio: cubo 30B, 2°piano [[BR]] Telefono: +39 0984 496478 [[BR]] Fax: +39 0984 496410 [[BR]] Email: calimeri[AT]mat.unical.it [[BR]] [[BR]] |
== Legend == Columns in the table below are to be read as following: |
| Line 135: | Line 47: |
| [#TOP Top of Page] ---- Torna alla pagina ["didattica"] Torna alla home page di [http://www.mat.unical.it/calimeri Francesco Calimeri] ---- |
* '''Nr'''. ID of the benchmark. The prefixes ''N'' resp. ''O'' denote a newly added resp. a 2011 benchmark. * '''Author(s)'''. Names of authors. A ''^*^'' denotes that they authored the respective package in previous years. * '''Type'''. One of ''Search'', ''Optimization'', ''Query''. See the problem [[BenchmarkProblems|classification]] page. * '''Final Problem Description'''. Problem specifications in their official form, with latest notes and updates. * '''Sample Instances'''. A link to sample instances of the given problem. |
Official Problem Suite
Problem List - Model & Solve and System Track
Nr |
Name |
Author(s) |
Type |
Complexity |
Domain |
Problem Description |
Sample Instances |
Checker |
ASP-Core-2 encoding |
N01 |
Permutation Pattern Matching |
Martin Lackner, Andreas Pfandler |
Search |
NP |
Combinatorial |
||||
N02 |
Valves Location Problem |
Andrea Peano |
Optimization |
Beyond NP |
Combinatorial |
||||
N03 |
Rotating Workforce Scheduling |
Francesco Calimeri, Thomas Krennwallner, Nysret Musliu |
Search |
|
Scheduling |
|
|
- |
|
N04 |
Connected Maximum-density Still Life |
Christian Drescher |
Optimization |
Beyond NP |
AI |
||||
N05 |
Graceful Graphs |
Christian Drescher |
Search |
NP |
Graph |
||||
N06 |
Bottle Filling Problem |
Wolfgang Faber |
Search |
|
Combinatorial |
||||
N07 |
Nomystery |
Giovambattista Ianni, Carlos Linares López*, Hootan Nakhost* |
Search |
|
Planning |
||||
N08 |
Sokoban |
Giovambattista Ianni, Wolfgang Faber*, Carlos Linares López* |
Search |
|
Planning |
||||
N09 |
Ricochet Robots |
Julius Höfler, Martin Gebser, Philipp Obermeier, Roland Kaminski, Torsten Schaub |
Search |
|
Puzzle |
||||
O10 |
Crossing Minimization |
Carmine Dodaro, Graeme Gange*, Peter Stuckey* |
Optimization |
Beyond NP |
Graph |
||||
O11 |
Reachability |
Carmine Dodaro, Giorgio Terracina* |
Query |
P |
Graph |
|
|
||
O12 |
Strategic Companies |
Mario Alviano, Marco Maratea*, Francesco Ricca* |
Query |
Beyond NP |
AI |
|
|||
O13 |
Solitaire |
Marcello Balduccini, Yuliya Lierler* |
Search |
NP |
Puzzle |
||||
O14 |
Weighted-Sequence Problem |
Marcello Balduccini, Yuliya Lierlier, Shaden Smith |
Search |
NP |
Database |
||||
O15 |
Stable Marriage |
Mario Alviano, Carmine Dodaro, Francesco Ricca |
Search |
P |
Graph |
||||
O16 |
Incremental Scheduling |
Marcello Balduccini, Yuliya Lierler* |
Search |
NP |
Scheduling |
Problem List - System Track only
Nr |
Name |
Author(s) |
Type |
Complexity |
Domain |
ASP-Core-2 Encoding |
Problem Description |
Sample Instances |
Checker |
ASP-Core-2 encoding |
N17 |
Qualitative Spatial Reasoning |
Jason Jingshi Li |
Search |
NP |
Formal logic |
|
|
|||
N18 |
Chemical Classification |
Despoina Magka |
Search |
P |
Natural Sciences |
|
||||
N19 |
Abstract Dialectical Frameworks Well-founded Model |
Stefan Ellmauthaler, Johannes Wallner |
Optimization |
|
Formal logic |
|
||||
N20 |
Visit-all |
Giovambattista Ianni,Nir Lipovetzky*, Carlos Linares López* |
Search |
|
Planning |
|
||||
N21 |
Complex Optimization of Answer Sets |
Martin Gebser, Roland Kaminski, Torsten Schaub |
Search |
|
Synthetic |
|
||||
O22 |
Knight Tour with Holes |
Francesco Calimeri, Neng-Fa Zhou* |
Search |
NP |
Puzzle |
|
||||
O23 |
Maximal Clique Problem |
Guenther Charwat, Martin Kronegger, Johan Wittocx* |
Optimization |
Beyond NP |
Graph |
|
||||
O24 |
Labyrinth |
Carmine Dodaro, Giovambattista Ianni, Martin Gebser* |
Search |
NP |
Puzzle |
|
||||
O25 |
Minimal Diagnosis |
Marcello Balduccini, Martin Gebser* |
Search |
Beyond NP |
Diagnosis |
|
||||
O26 |
Hanoi Tower |
Gayathri Namasivayam, Miroslaw Truszczynski, Shaden Smith, Alex Westlund |
Search |
NP |
AI |
|
||||
O27 |
Graph Colouring |
Johannes Wallner, Marcello Balduccini*, Yuliya Lierler* |
Search |
NP |
Graph |
|
Legend
Columns in the table below are to be read as following:
Nr. ID of the benchmark. The prefixes N resp. O denote a newly added resp. a 2011 benchmark.
Author(s). Names of authors. A * denotes that they authored the respective package in previous years.
Type. One of Search, Optimization, Query. See the problem classification page.
Final Problem Description. Problem specifications in their official form, with latest notes and updates.
Sample Instances. A link to sample instances of the given problem.