Generating highly balanced sudoku problems as hard problems

Sudoku problems are some of the most known and enjoyed pastimes, with a never diminishing popularity, but, for the last few years those problems have gone from an entertainment to an interesting research area, a twofold interesting area, in fact. On the one side Sudoku problems, being a variant of Gerechte Designs and Latin Squares, are being actively used for experimental design, as in [8, 44, 39, 9]. On the other hand, Sudoku problems, as simple as they seem, are really hard structured combinatorial search problems, and thanks to their characteristics and behavior, they can be used as benchmark problems for refining and testing solving algorithms and approaches. Also, thanks to their high inner structure, their study can contribute more than studies of random problems to our goal of solving real-world problems and applications and understanding problem characteristics that make them hard to solve. In this work we use two techniques for solving and modeling Sudoku problems, namely, Constraint Satisfaction Problem (CSP) and Satisfiability Problem (SAT) approaches. To this effect we define the Generalized Sudoku Problem (GSP), where regions can be of rectangular shape, problems can be of any order, and solution existence is not guaranteed. With respect to the worst-case complexity, we prove that GSP with block regions of m rows and n columns with m = n is NP-complete. For studying the empirical hardness of GSP, we define a series of instance generators, that differ in the balancing level they guarantee between the constraints of the problem, by finely controlling how the holes are distributed in the cells of the GSP. Experimentally, we show that the more balanced are the constraints, the higher the complexity of solving the GSP instances, and that GSP is harder than the Quasigroup Completion Problem (QCP), a problem generalized by GSP. Finally, we provide a study of the correlation between backbone variables – variables with the same value in all the solutions of an instance– and hardness of GSP.

L’aprenentatge de càlcul mental a través de jocs a un aula d’educació primària

Aquest treball es basa en identificar les estratègies de càlcul mental que fan servir alumnes de quart de primària. Aquesta identificació es realitza a partir de la resolució d’operacions per part dels alumnes i el seu posterior anàlisi. A partir de les estratègies que hagin sorgit, es realitzarà una intervenció didàctica basada en jocs matemàtics per tal de descobrir i treballar noves estratègies matemàtiques. Finalment, amb una nova prova es comprovarà si els nens i nenes coneixen i apliquen diferents estratègies pel càlcul mental. Amb aquesta intervenció es pretén comprovar si a partir de jocs els nens i nenes milloren les estratègies de càlcul mental.

Matemàtica i música amb ADN

Treball de recerca realitzat per un alumne d’ensenyament secundari i guardonat amb un Premi CIRIT per fomentar l'esperit científic del Jovent l’any 2005. Estudi sobre l’ADN que té com a finalitat conèixer introductòriament l’utilització del càlcul matemàtic computacional en les investigacions sobre aquest. Els objectius de l’estudi són per una part, conèixer què és l'ADN i quins són els seus mecanismes de duplicació i de transmissió de la informació genètica, així com el paper d'altres molècules que intervenen en aquest procés ; també s’estudia quins han estat els processos de la cèl·lula que l'ésser humà ha estat capaç de copiar o imitar. A partir d’aquesta introducció, es vol conèixer què s'entén concretament per computació amb ADN i alguns dels problemes matemàtics que s'han resolt, així com algunes aplicacions de l'ADN en altres camps. La recerca ha permès arribar a diverses conclusions. Primerament que l'ADN és un excel·lent candidat per poder fer càlculs matemàtics. En segon lloc, tot i que en el present treball no se solucionen problemes computacionalment difícils es mostra la capacitat de les molècules d'ADN per resoldre problemes. En tercer lloc, l'interès mostrat per importants empreses dedicades a la informàtica fa més esperançador que en un futur hi pugui haver ordinadors que funcionin amb molècules d'ADN. Finalment, es demostra que les matemàtiques, la informàtica i la biologia són tres camps que estan interrelacionats. Per tal de trencar una mica amb la serietat del treball, s'acaba descrivint una manera de posar música a les cadenes d'ADN, i es mostren alguns resultats com són les músiques associades als 24 cromosomes humans, així com les corresponents a 29 proteïnes.

Formació de professorat per a una educació matemàtica de familiars en contextos multiculturals

El projecte “Formació de professorat per a una educació matemàtica de familiars en contextos multiculturals” ha consistit en el desenvolupament i anàlisi d’estratègies formatives en matemàtiques per a familiars d’alumnat de primària i secundària. El projecte dóna resposta a la necessitat de donar eines als familiars de l’alumnat per a facilitar-los l’accés a les matemàtiques que estan aprenent els seus fills i filles i poder ajudar-los. D’aquesta manera se superen les distàncies existents entre les matemàtiques que coneixen els pares/les mares i les que s’ensenyen a l’escola, que s’incrementen en el cas de famílies provinents d’altres països, i es contribueix a desenvolupar una educació de qualitat que faciliti l’assoliment d’una igualtat de resultats educatius entre l’alumnat, en el respecte a les diferències entre cultures, i establint lligams entre l’escola i la comunitat. A través del desenvolupament de dos “tallers de matemàtiques” per a familiars, a una escola de primària i a un institut de secundària, i partint del coneixement existent en educació de persones adultes i del diàleg igualitari entre les diferents persones participants, s’han pogut identificar elements rellevants en la formació matemàtica de familiars que faciliten el seu aprenentatge de les matemàtiques, així com estratègies per a ajudar els seus fills/es en l’aprenentatge de les matemàtiques. Partint d’aquestes situacions reals de formació de pares i mares que s’han donat als tallers, s’han creat materials didàctics que poden ser emprats en altres contextos de formació de familiars: per una banda, un recull de materials en format llibre que poden ser emprats per part de professorat que treballi en formació de familiars o pels propis familiars per a treballar amb els seus fills/es; per altra banda, un material audiovisual amb situacions claus que il·lustren estratègies i elements rellevants per a la formació matemàtica de familiars.

La programació al servei de la matemàtica

Treball de recerca realitzat per un alumne d'ensenyament secundari i guardonat amb un Premi CIRIT per fomentar l'esperit cientí­fic del Jovent l'any 2009. La programació al servei de la matemàtica és un programa informàtic fet amb Excel i Visual Basic. Resol equacions de primer grau, equacions de segon grau, sistemes d'equacions lineals de dues equacions i dues incògnites, sistemes d'equacions lineals compatibles determinats de tres equacions i tres incògnites i troba zeros de funcions amb el teorema de Bolzano. En cadascun dels casos, representa les solucions gràficament. Per a això, en el treball s'ha hagut de treballar, en matemàtiques, amb equacions, nombres complexos, la regla de Cramer per a la resolució de sistemes, i buscar la manera de programar un mètode iteratiu pel teorema de Bolzano. En la part gràfica, s'ha resolt com fer taules de valors amb dues i tres variables i treballar amb rectes i plans. Per la part informàtica, s'ha emprat un llenguatge nou per l'alumne i, sobretot, ha calgut saber decidir on posar una determinada instrucció, ja que el fet de variar-ne la posició una sola lí­nea ho pot canviar tot. A més d'això, s'han resolt altres problemes de programació i també s'ha realitzat el disseny de pantalles.

Les TIC a l'ensenyament de la modelització matemàtica en Ciències Econòmiques i en Ciències Experimentals

Aquest projecte proposa materials didàctics per a un nou plantejament de les assignatures de Matemàtiques dels primers cursos de Ciències Empresarials i d'Enginyeria Tècnica, més acord amb el procés de convergència europea, basat en la realització de projectes que anomenem “Tallers de Modelització Matemàtica” (TMM) en els quals: (1) Els alumnes parteixen de situacions i problemes reals per als quals han de construir per sí mateixos els models matemàtics més adients i, a partir de la manipulació adequada d’aquests models, poden obtenir la informació necessària per donar-los resposta. (2) El treball de construcció, experimentació i avaluació dels models es realitza amb el suport de la calculadora simbòlica Wiris i del full de càlcul Excel com a instruments “normalitzats” del treball matemàtic d’estudiants i professors. (3) S’adapten els programes de les assignatures de matemàtiques de primer curs per tal de poder-les associar a un petit nombre de Tallers que parteixen de situacions adaptades a cada titulació. L’assignatura de Matemàtiques per a les Ciències Empresarials s’articula entorn de dos tallers independents: “Matrius de transició” pel que fa a l’àlgebra lineal i “Previsió de vendes” per a la modelització funcional en una variable. L’assignatura de Matemàtiques per a l’Enginyeria s’articula entorn d’un únic taller, “Models de poblacions”, que abasta la majoria de continguts del curs: successions i models funcionals en una variable, àlgebra lineal i equacions diferencials. Un conjunt d’exercicis interactius basats en la calculadora simbòlica WIRIS (Wiris-player) serveix de suport per al treball tècnic imprescindible per al desenvolupament de les dues assignatures. L’experimentació d’aquests tallers durant 2 cursos consecutius (2006/07 i 2007/08) en dues universitats catalanes (URL i UAB) ha posat en evidència tant els innegables avantatges del nou dispositiu docent per a l’aprenentatge dels estudiants, així com les restriccions institucionals que actualment dificulten la seva gestió i difusió.

Aula matemàtica, 2a. part. : un projecte per a la millora de l'aprenentatge de les matemàtiques a la UAB

El projecte Aula Matemàtica consta de dues parts. 1. Elaborar un material d'autoaprenentatge en suport digital que cobreixi tots els temes de Matemàtiques de 1r. curs de les carreres de Ciències (Biologia, Química, etc.) i les Enginyeries. Aquest material, accessible des de qualsevol ordinador connectat a Internet, és una base de dades de problemes que els alumnes poden utilitzar per a treballar el temes explicats a classe, o be per cobrir deficiències a la seva formació pre-universitària. Al mateix temps, es poden realitzar exàmens, i els alumnes poden practicar amb els problemes d'examen. 2. Durant unes hores cada dia, oferir una (o diverses) aules d'informàtica al campus de la UAB amb presència de personal de suport (professors, o becaris de darrers cursos de matemàtiques o doctorat) per tal que els alumnes que vulguin (o necessitin) puguin practicar amb ajuda, i consultat els dubtes que tinguin. En la fase actual del projecte s’han fet les següents actuacions: 1. S’ha obert una aula d’informàtica amb suport de becaris a la facultat de Ciències, on a més de practicar els alumnes, s’han efectuat exàmens. 2. S’ha treballat en el programa per tal de fer-lo més amigable. 3. S’ha ampliat la base de problemes fins a 1450, i cobrir totes les assignatures de Matemàtiques i Estadística de 1r. curs de la facultat de Ciències i l’Escola Tècnica Superior d’Enginyeries. 4. S’ha començat a treballar per a la utilització del programa a Secundària. 5. S’han fet avanços molt importants per tal d’incorporar problemes amb resposta oberta. 6. El programa és accessible des de qualsevol ordenador amb Internet.

Pla de millora de la docència del Departament de Matemàtica Econòmica, Financera i Actuarial

La finalitat del projecte (bianual 2007-09) era aconseguir una millora de la docència que imparteix el Departament de Matemàtica Econòmica, Financera i Actuarial. La nostra tasca principal ha consistit en obtenir uns indicadors que ens permetessin conèixer millor el nostre alumnat, per tal de tenir la màxima informació a l'hora de plantejar la revisió global que representa la implantació dels nous graus d’acord amb les directrius del procés de Convergència Europea. En aquest projecte han participat tots els coordinadors de les assignatures obligatòries del Departament i els tres Grups d’Innovació Docent formats per membres del Departament. S’han analitzat les dades de les assignatures des del curs 2000-01 fins 2006-07 per tal de tenir informació sobre l’eficàcia de cursar les assignatures d’Introducció a les Matemàtiques i la seva incidència en els aprovats a Matemàtiques I i II . També s’han estudiat dades sobre el col·lectiu de repetidors. Com a resultat d’aquest estudi i de les enquestes que s’han fet, s’han redactat dos articles: “Propuesta de mejora de la actuación docente a partir de las características del alumnado de primer curso de Matemáticas en la Facultad de Economía y Empresa de la Universidad de Barcelona” y “Estudio del perfil del alumnado de primer curso en la Facultad de Economía y Empresa de la Universidad de Barcelona” que s’han presentat a dos congressos d’Innovació Docent (Burgos, setembre-2009 i Vigo, juliol-2009).

Aula Matemàtica, 3a part : un projecte per a la millora de l'aprenentatge de les Matemàtiques a la UAB

Aquest projecte és continuació dels projectes "Aula Matemàtica, un projecte per a la millora de l'aprenentatge de les Matemàtiques a la UAB", primera i segona part, Ref 2003MQD 00030 i Ref 2006MQD00072, els quals han permès identificar els problemes i oferir als estudiants de primer curs d'algunes titulacions pilot de Ciències de la UAB una plataforma d'autoaprenentatge que han valorat positivament. Es tracta d'una base de dades de problemes de resposta tancada, accessible per internet, que permet als estudiants practicar pel seu compte, autoevaluar-se i també al seu professor posar-los-hi un examen i controlar el temps de pràctica dels estudiants. L'aprenentatge de les Matemàtiques requereix l'automatització de certes tècniques de caire, per exemple, manipulatiu, per a l'adquisició de la qual és imprescindible un treball repetitiu d'entrenament de l'estudiant. Es tracta de proporcionar material interactiu que permeti aquest entrenament, al ritme de l’estudiant, de manera autònoma, no presencial i atractiva per a les noves generacions; però alhora oferir suport presencial quan sigui necessari. L'enorme diversificació observada en la formació inicial dels estudiants, amb la convivència de diferents vies de batxillerat en moltes titulacions de ciències, provoca una dificultat d'adaptació de les assignatures de primer curs. Es requereix per tant una major tutorització dels estudiants i oferta d'eines i material complementari per al treball individual. El projecte actual té com a objectius l'elaboració de més material i la classificació d'aquest per permetre l'adaptació de la plataforma a un major nombre d'assignatures i la millora de l'accessibilitat i la gestió d'aquesta plataforma.

Desarrollo de un sistema de clasificación de recursos electrónicos en el ámbito de la lógica matemática

El presente trabajo define una taxonomía para la clasificación de recursos digitales del ámbito de la lógica tradicional, y más concretamente los recursos que se podrían generar en el ámbito de la asignatura de Lógica Matemática del plan de estudios de las titulaciones de Ingeniería Técnica de Gestión y de Sistemas impartidas en la Universitat Oberta de Catalunya (UOC).