Artículos con la etiqueta ‘Algoritmos’

How hard is it to control an election by breaking ties?

Por • 29 abr, 2013 • Category: sociologia

We study the computational complexity of the problem of controlling the result of an election by breaking ties. When the chair is only asked to break ties to choose between one of the co-winners, the problem is trivially easy. However, in multi-round elections like STV, we prove that it can be NP-hard for the chair to compute how to break ties to ensure a given result. Our results contain several surprises. For example, whilst it is NP-hard to compute a manipulating vote for a multi-round rule like Nanson, it is polynomial for the chair to control the result by breaking ties. As a second example, it can be NP-hard to control an election by breaking ties even with a simple two-stage voting rule.

How to Solve the Torus Puzzle

Por • 2 abr, 2013 • Category: Opinion

In this paper, we consider the following sliding puzzle called torus puzzle. In an m by n board, there are mn pieces numbered from 1 to mn. Initially, the pieces are placed in ascending order. Then they are scrambled by rotating the rows and columns without the player’s knowledge. The objective of the torus puzzle is to rearrange the pieces in ascending order by rotating the rows and columns. We provide a solution to this puzzle. In addition, we provide lower and upper bounds on the number of steps for solving the puzzle. Moreover, we consider a variant of the torus puzzle in which each piece is colored either black or white, and we present a hardness result for solving it.

Mathematics in the Age of the Turing Machine

Por • 13 feb, 2013 • Category: Opinion

The article gives a survey of mathematical proofs that rely on computer calculations and formal proofs. Computers have rapidly become so pervasive in mathematics that future generations may look back to this day as a golden dawn. A comprehensive survey is out of the question. It would almost be like asking for a summary of applications of symmetry to mathematics. Computability – like symmetry – is a wonderful structural property that some mathematical objects possess that makes answers flow more readily wherever it isfound.

Information Theory of DNA Sequencing

Por • 4 abr, 2012 • Category: Ciencia y tecnología

DNA sequencing is the basic workhorse of modern day biology and medicine. Shotgun sequencing is the dominant technique used: many randomly located short fragments called reads are extracted from the DNA sequence, and these reads are assembled to reconstruct the original sequence. A basic question is: given a sequencing technology and the statistics of the DNA sequence, what is the minimum number of reads required for reliable reconstruction? This number provides a fundamental limit to the performance of any assembly algorithm. By drawing an analogy between the DNA sequencing problem and the classic communication problem, we formulate this question in terms of an information theoretic notion of sequencing capacity. This is the asymptotic ratio of the length of the DNA sequence to the minimum number of reads required to reconstruct it reliably. We compute the sequencing capacity explicitly for a simple statistical model of the DNA sequence and the read process. Using this framework, we also study the impact of noise in the read process on the sequencing capacity.

The Emerging Art of Algorithmic Music

Por • 20 dic, 2011 • Category: Filosofía

The work of Ville-Matias Heikkila, a Finnish artist and computer programmer, might come as a shock. In the last year or so, he and others have been experimenting with the audio output of simple computer programs in an infinite loop. The output is a modulated stream of pulses that, when played through an audio speaker, sounds melodic. Today, he outlines this work and some of the techniques and tools that he uses to generate the code, listen to it and even visualise it. He’s posted some of these tunes along with their source code on Youtube. Heikkila says that these programs generate surprisingly interesting music, sometimes by repeating only two or three arithmetic operations. So he and others have been exploring the space of all possible simple algorithms, albeit in a rather disorganised way. Now Heikkila, who also goes by the online moniker viznut, is proposing a more methodical search of this space. He wants to set up a program that generates new formulas automatically and a website that allows people to rate the music it finds. In essence, he wants to crowdsource the task of music discovery. One half of this problem may have already been cracked for him. Ten years ago, Stephen Wolfram argued that the laws of physics are no more than a set of simple algorithms. In his book A New Kind of Science, he explores and characterises the entire space of simple algorithms for cellular automata and argues that the Universe is governed by rules like them. The difficult task is finding these rules.

Software Progress Beats Moore’s Law

Por • 10 mar, 2011 • Category: Leyes

The rapid improvement in chips, of course, has its own “law” — Moore’s Law, named after the Intel co-founder Gordon Moore, who in 1965 predicted that the density of transistors on integrated circuits would double every 18 months or so. Physics, along with ingenuity and investment, made that forecast of performance-doubling every year and a half accurate so far.There are no such laws in software. But the White House advisory report cited research, including a study of progress over a 15-year span on a benchmark production-planning task. Over that time, the speed of completing the calculations improved by a factor of 43 million.

The A.I. Revolution Is On

Por • 28 dic, 2010 • Category: Internacionales

Today’s AI doesn’t try to re-create the brain. Instead, it uses machine learning, massive data sets, sophisticated sensors, and clever algorithms to master discrete tasks.