ejercicio número 55 de la revista antena de telecomunicación

En esta ocasión,

las blancas juegan y dan mate en cinco jugadas





A ver lo que se me ocurre ... ;)

ejercicio número 54 de la revista antena de telecomunicación

Juegan Blancas



y a pesar del peligro que tienen en b2, consiguen mate en cinco movimientos.

A falta de la solución en el próximo número, esta es mi propuesta:

1. Rh8+, Bxh8
2. Bh6+, Bg7
3. Bxg7+, Kg8
4. Bh6+, Kh8
5. Qg7#

Multiple-choice Knapsack Problem

In my new job at University of Cantabria, where I work on a FP7 European research called MULTICUBE, whose objective is to build an innovative design space exploration (DSE) tool for MpSoCs, I've found out an unexpected application of genetic algorithms.

When you co-design a hardware/software application on a MpSoC architecture you must chose a suitable architecture (doing an architecture exploration by tuning parameters of the afore mentioned architecture in order to optimize power, performance, area, etc) and then you must map the functionality implemented by the application software optimally (run-time exploration) over the different hardware resources (e.g. microprocessor cores) in order to fully use all the resources available within the constraints imposed by the application.

The process of mapping optimally could be seen as a classical Knapsack Problem (see a Google Search on the subject), which is a problem in combinatorial optimization. The thing is, that instead of 0-1-knapsack problem, we've got a Multiple-choice Knapsack Problem (MMKP), that is one of the list of knapsack problems with n items (e.g. application tasks) and m knapsacks (e.g. hardware resources) with capacities Wi.

There are several approximations to the solution of the (NP-Complete) problem including greedy ones, dynamic programming ones, heuristic ones, etc. But the ones that I'm interested in are the evolutionary computation approaches. It's not easy to find open access to papers which present such solution approaches. I've found out a paper who explains a heuristic approach (convex hull) with the quality of service (QoS) management problem of the Multiple Resource Multiple Dimension (MRMD) systems example.

Solving the Multidimensional Multiple-choice Knapsack Problem by constructing convex hulls
Md Mostofa Akbar (a),(b), M. Sohel Rahman (b), M. Kaykobad (b), E.G. Manning (a), G.C. Shoja (a)

(a) Department of CSC, PANDA Lab, University of Victoria, Victoria, BC, Canada, USA
(b) Department of CSE, BUET, Dhaka, Bangladesh

In the paper the authors state that:

Various other techniques like tabu search [14], simulated annealing [15] and genetic algorithms [16] can also be applied to solve the variants of Knapsack Problem. The genetic algorithm has the exponential worst-case complexity—it can explore all the items. Tabu search and simulated annealing are based on looking at the neighbours. These are costlier than the greedy approach used in HEU (heuristic). HEU uses a two-way interchange approach and searches candidates in the neighbourhood which yield better revenue, and changes one selection to another. But in tabu search, simulated annealing and genetic algorithm approach, current solution is moved to another solution by upgrading some and downgrading some. This upgrade and downgrade at the same step requires more time because we have to search all neighbouring combinations of current solution. In the next section, we present our main contribution by presenting a new heuristic to solve MMKP by constructing convex hulls.

The references aforementioned are:

[14] Dammeyer F,Voss S. Dynamic tabu list management using the reverse elimination method.Annals of Operations Research 1991.

[15] Drexel A. A simulated annealing approach to the multiconstraint zero-one knapsack problem. Annals of Computing 1988;40:1–8.

[16] Khuri S, Back T, Heitkotter J. The zero/one multiple knapsack problem and genetic algorithms. ACM Symposium of applied computation; 1994.

So it seems this time genetic algorithms are not the best option at hand to solve the problem ... :)

ejercicio número 53 de la revista antena de telecomunicación

En el rincón de ocio de la revista Antena de Telecomunicación del primer cuatrimestre del primer cuatrimestre de este año (número 1, abril 2008) del Colegio de Ingenieros Técnicos de Telecomunicación (COITT) tenemos la sección habitual dedicada a los problemas de ajedrez, con el siguiente ejercicio planteado:

Ejercicio n.º 53

Las negras están al completo y con amenaza inminente al Rey blanco; sin empbargo las blancas consiguen mate en cuatro movimientos.



Después de pensar un rato y ensayar los movimientos en el scid, he llegado a la siguiente propuesta de solución:

1. Qxe8+!, Kxe8
2. a8=Q+, Qd8
3. Ba4+, Kf8
4. Qxd8#

Hasta el siguiente cuatrimestre no podré saber si acerté con la solución ... :)

The Wombats - Kill The Director

Almost my favourite band!!! :)



Lyrics

Kill the director

I've met someone that makes me feel seasick
Oh what a skill to have
Oh what a skill to have
So many skills that make her distinctive
But they're not mine to have
No they're not mine

Whenever she looks i read the nearest paper
No i don't care about the soaps
No i don't care about the soaps
Though i'm acting like i'm in an Eastenders episode

If this is a rom-com
Kill the director
If this is a rom-com
Kill the director please

Carrots help us see much better in the dark
Don't talk to girls; they'll break your heart
And this is my head and this is my spout
They work together; they can't figure anything out

So with the angst of a teenage band
Here's another song about a gender i'll never understand
Here's another song about a gender i'll never understand

If this is a rom-com
Kill the director
If this is a rom-com
Kill the director
If this is a rom-com
Kill the director please

This is no Bridget Jones
This is no Bridget Bridget
This is no Bridget Jones
This is no Bridget Bridget
This is no Bridget Jones
This is no Bridget Bridget
This is no Bridget Jones
This is no Bridget Bridget
This is no Bridget Jones
This is no Bridget Bridget
This is no Bridget Jones
This is no Bridget
Bridget Jones