BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Departamento de Computación - ECPv6.15.18//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-ORIGINAL-URL:https://www.dc.uba.ar
X-WR-CALDESC:Eventos para Departamento de Computación
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:America/Sao_Paulo
BEGIN:STANDARD
TZOFFSETFROM:-0300
TZOFFSETTO:-0300
TZNAME:-03
DTSTART:20230101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=America/Sao_Paulo:20241010T140000
DTEND;TZID=America/Sao_Paulo:20241010T150000
DTSTAMP:20260405T112439
CREATED:20241004T122728Z
LAST-MODIFIED:20241004T122728Z
UID:9457-1728568800-1728572400@www.dc.uba.ar
SUMMARY:Defensa Tesis Licenciatura Daniel Salvia
DESCRIPTION:Título: Complejidad computacional en distintas formulaciones de ajedrez para un jugador\nDirector: Dr. Ariel Arbiser\nJurados: Dr. Javier Marenco\, Dr. Francisco Soulignac \nResumen:\nEl objetivo de esta tesis es estudiar la complejidad computacional correspondiente al problema del ajedrez solitario\, en que dada una posición el jugador sólo puede hacer jugadas de captura con el objetivo de dejar una sola pieza en el tablero. Demostramos que este problema pertenece a la clase de complejidad de los problemas NP-Completos. Mediante problemas de ciclos hamiltonianos en grafos no dirigidos\, se investiga la NP-Completitud del juego restringiendo el conjunto de piezas a diferentes posibilidades utilizando peones\, alfiles y torres. Para esto se presentan cuatro formas de generar las posiciones con diferentes propiedades como las piezas usadas o las maneras de representar las aristas del grafo. Se compara un método con otro para analizar ventajas de cada uno\, tales como tamaño del tablero y cantidad de piezas necesarias. También se estudia la NP-Completitud de distintas variantes en que se modifican algunas reglas\, así como los efectos de utilizar piezas del ajedrez antiguo. Se investiga asimismo la frontera P de este problema cuando se usa esencialmente un solo tipo de pieza.\n\n\n 
URL:https://www.dc.uba.ar/event/defensa-tesis-licenciatura-daniel-salvia/
LOCATION:Aula 1203
CATEGORIES:Agenda
END:VEVENT
END:VCALENDAR