tailieunhanh - Ebook Algorithms unplugged: Part 2

(BQ) Part 1 book Algorithms unplugged has contents: Numbers into English words, winning strategies for a matchstick game, scheduling of tournaments or sports leagues, eulerian circuits, shortest paths, marriage broker, the knapsack problem, simulated annealing, and other contents. | Part III Planning, Coordination and Simulation Overview Helmut Alt and R¨diger Reischuk u Freie Universit¨t Berlin, Berlin, Germany a Universit¨t zu L¨beck, L¨beck, Germany a u u Strategic thinking and planning are commonly regarded as typically human capabilities. Ever since computer programs demonstrated that they can beat chess grand masters, however, one can see that some of these skills can be successfully managed by machines. On the other hand, some games can be won with very simple strategies, one must have the right knowledge. In a chapter in this part of the book we see this demonstrated impressively by the match game Nim. In many games, it is important that we don’t allow the enemy to anticipate our moves. A simple strategy – referred to in computer science jargon as deterministic – can, however, be predicted. This can be avoided if you include random decisions – without this many games such as rock–paper–scissors would be quite boring. Many algorithms can be improved or be speeded up in this way – these are called probabilistic or randomized algorithms. Now we need to ask ourselves how a computer could toss a coin, given that we would expect only full precision? The chapter here on random numbers provides an answer. A strategic and algorithmic approach makes sense even with everyday problems, and not just during games. For example, if we wish to disseminate a message to a broad group of people through phone calls or to many computers via an electronic network, then we need a good plan in order to achieve this objective quickly and reliably. We see this in the chapter on broadcasting. In a further chapter we see a clever approach to determining the winner of an election. Some tasks require careful long-term planning. An example is the game schedule for the Bundesliga, the German soccer league, which requires us to consider various constraints. Two chapters in this section deal with simulations, ., simulating natural processes using computers. First