Draque Penso, Lucia; Rautenbach, Dieter; Szwarcfiter, Jayme Luiz
Connectivity and diameter in distance graphs. - In: Networks. - New York, NY : Wiley-Interscience, ISSN 10970037, Bd. 57 (2011), 4, S. 310-315
http://dx.doi.org/10.1002/net.20397
Connectivity and diameter in distance graphs. - In: Networks. - New York, NY : Wiley-Interscience, ISSN 10970037, Bd. 57 (2011), 4, S. 310-315
http://dx.doi.org/10.1002/net.20397
Dietzfelbinger, Martin; Mitzenmacher, Michael; Rink, Michael
Cuckoo hashing with pages. - In: Algorithms - ESA 2011 / ESA ; 19 (Saarbrücken) : 2011.09.05-09. - Berlin [u.a.] : Springer (2011), S. 615-627
http://dx.doi.org/10.1007/978-3-642-23719-5
Cuckoo hashing with pages. - In: Algorithms - ESA 2011 / ESA ; 19 (Saarbrücken) : 2011.09.05-09. - Berlin [u.a.] : Springer (2011), S. 615-627
http://dx.doi.org/10.1007/978-3-642-23719-5
Zapf, Benjamin
Theoretische und experimentelle Untersuchungen zu modernen Priority-Queue-Realisierungen, 2011. - 116 S.
Ilmenau, Techn. Univ., Diplomarbeit, 2011
In der Informatik sind Prioritätswarteschlangen oder Priority Queues oft verwendete und etablierte Hilfsmittel, um in kurzer Zeit Objekte nach einer bestimmten Wichtung auszugeben. Auch aus diesem Grund haben Verbesserungen in diesem Bereich nichts von ihrer wissenschaftlichen Relevanz eingebüßt. Verschiedene Forschungseinrichtungen sind dabei diese Priority Queues effektiver oder auch nur einfacher zu gestalten. Dabei werden unterschiedliche Denkansätze verfolgt. Diese reichen von dynamischeren Baumstrukturen bis hin zu mehrteiligen Heaps. Die vorliegende Arbeit beschreibt und analysiert Ideen verschiedener Autoren aus den Jahren 2005 bis 2010 und führt einen Vergleich ausgewählter Arten an praktischen Beispielen durch. Die Algorithmen lassen sich hierbei nach den verschiedenen Baumstrukturen einteilen, auf denen sie aufgebaut sind. Daneben ist eine Unterteilung der Algorithmen nach ihrer Struktur möglich. Während bei einigen eine starre Struktur mit Markierungen genutzt wird, bieten andere Algorithmen die Möglichkeit die Struktur eingeschränkt oder auch zu großen Teilen zu variieren.
http://www.gbv.de/dms/ilmenau/abs/667580549zapf.txt
Theoretische und experimentelle Untersuchungen zu modernen Priority-Queue-Realisierungen, 2011. - 116 S.
Ilmenau, Techn. Univ., Diplomarbeit, 2011
In der Informatik sind Prioritätswarteschlangen oder Priority Queues oft verwendete und etablierte Hilfsmittel, um in kurzer Zeit Objekte nach einer bestimmten Wichtung auszugeben. Auch aus diesem Grund haben Verbesserungen in diesem Bereich nichts von ihrer wissenschaftlichen Relevanz eingebüßt. Verschiedene Forschungseinrichtungen sind dabei diese Priority Queues effektiver oder auch nur einfacher zu gestalten. Dabei werden unterschiedliche Denkansätze verfolgt. Diese reichen von dynamischeren Baumstrukturen bis hin zu mehrteiligen Heaps. Die vorliegende Arbeit beschreibt und analysiert Ideen verschiedener Autoren aus den Jahren 2005 bis 2010 und führt einen Vergleich ausgewählter Arten an praktischen Beispielen durch. Die Algorithmen lassen sich hierbei nach den verschiedenen Baumstrukturen einteilen, auf denen sie aufgebaut sind. Daneben ist eine Unterteilung der Algorithmen nach ihrer Struktur möglich. Während bei einigen eine starre Struktur mit Markierungen genutzt wird, bieten andere Algorithmen die Möglichkeit die Struktur eingeschränkt oder auch zu großen Teilen zu variieren.
http://www.gbv.de/dms/ilmenau/abs/667580549zapf.txt
Dietzfelbinger, Martin
Fingerprinting. - In: Algorithms unplugged. - Berlin [u.a.] : Springer (2011), S. 181-193
Fingerprinting. - In: Algorithms unplugged. - Berlin [u.a.] : Springer (2011), S. 181-193
Dietzfelbinger, Martin; Rowe, Jonathan E.; Wegener, Ingo; Woelfel, Philipp
Precision, local search and unimodal functions. - In: Algorithmica. - New York, NY : Springer, ISSN 14320541, Bd. 59 (2011), 3, S. 301-322
We investigate the effects of precision on the efficiency of various local search algorithms on 1-D unimodal functions. We present a (1+1)-EA with adaptive step size which finds the optimum in O(log n) steps, where n is the number of points used. We then consider binary (base-2) and reflected Gray code representations with single bit mutations. The standard binary method does not guarantee locating the optimum, whereas using the reflected Gray code does so in O ((log n)2) steps. A(1+1)-EA with a fixed mutation probability distribution is then presented which also runs in O ((log n)2). Moreover, a recent result shows that this is optimal (up to some constant scaling factor), in that there exist unimodal functions for which a lower bound of Omega ((log n)2) holds regardless of the choice of mutation distribution. For continuous multimodal functions, the algorithm also locates the global optimum in O((log n)2). Finally, we show that it is not possible for a black box algorithm to efficiently optimise unimodal functions for two or more dimensions (in terms of the precision used).
http://dx.doi.org/10.1007/s00453-009-9352-x
Precision, local search and unimodal functions. - In: Algorithmica. - New York, NY : Springer, ISSN 14320541, Bd. 59 (2011), 3, S. 301-322
We investigate the effects of precision on the efficiency of various local search algorithms on 1-D unimodal functions. We present a (1+1)-EA with adaptive step size which finds the optimum in O(log n) steps, where n is the number of points used. We then consider binary (base-2) and reflected Gray code representations with single bit mutations. The standard binary method does not guarantee locating the optimum, whereas using the reflected Gray code does so in O ((log n)2) steps. A(1+1)-EA with a fixed mutation probability distribution is then presented which also runs in O ((log n)2). Moreover, a recent result shows that this is optimal (up to some constant scaling factor), in that there exist unimodal functions for which a lower bound of Omega ((log n)2) holds regardless of the choice of mutation distribution. For continuous multimodal functions, the algorithm also locates the global optimum in O((log n)2). Finally, we show that it is not possible for a black box algorithm to efficiently optimise unimodal functions for two or more dimensions (in terms of the precision used).
http://dx.doi.org/10.1007/s00453-009-9352-x
Vöcking, Berthold; Alt, Helmut; Dietzfelbinger, Martin
Algorithms unplugged. - Berlin [u.a.] : Springer, 2011. - X, 406 S.. - ISBN 978-3-642-15327-3
Literaturangaben
Algorithms specify the way computers process information and how they execute tasks. Many recent technological innovations and achievements rely on algorithmic ideas they facilitate new applications in science, medicine, production, logistics, traffic, communi cation and entertainment. Efficient algorithms not only enable your personal computer to execute the newest generation of games with features unimaginable only a few years ago, they are also key to several recent scientific breakthroughs for example, the sequencing of the human genome would not have been possible without the invention of new algorithmic ideas that speed up computations by several orders of magnitude. The greatest improvements in the area of algorithms rely on beautiful ideas for tackling computational tasks more efficiently. The problems solved are not restricted to arithmetic tasks in a narrow sense but often relate to exciting questions of nonmathematical flavor, such as: How can I find the exit out of a maze? How can I partition a treasure map so that the treasure can only be found if all parts of the map are recombined? How should I plan my trip to minimize cost? Solving these challenging problems requires logical reasoning, geometric and combinatorial imagination, and, last but not least, creativity the skills needed for the design and analysis of algorithms. In this book we present some of the most beautiful algorithmic ideas in 41 articles written in colloquial, nontechnical language. Most of the articles arose out of an initiative among German-language universities to communicate the fascination of algorithms and computer science to high-school students. The book can be understood without any prior knowledge of algorithms and computing, and it will be an enlightening and fun read for students and interested adults.
http://d-nb.info/1005009791/04
Algorithms unplugged. - Berlin [u.a.] : Springer, 2011. - X, 406 S.. - ISBN 978-3-642-15327-3
Literaturangaben
Algorithms specify the way computers process information and how they execute tasks. Many recent technological innovations and achievements rely on algorithmic ideas they facilitate new applications in science, medicine, production, logistics, traffic, communi cation and entertainment. Efficient algorithms not only enable your personal computer to execute the newest generation of games with features unimaginable only a few years ago, they are also key to several recent scientific breakthroughs for example, the sequencing of the human genome would not have been possible without the invention of new algorithmic ideas that speed up computations by several orders of magnitude. The greatest improvements in the area of algorithms rely on beautiful ideas for tackling computational tasks more efficiently. The problems solved are not restricted to arithmetic tasks in a narrow sense but often relate to exciting questions of nonmathematical flavor, such as: How can I find the exit out of a maze? How can I partition a treasure map so that the treasure can only be found if all parts of the map are recombined? How should I plan my trip to minimize cost? Solving these challenging problems requires logical reasoning, geometric and combinatorial imagination, and, last but not least, creativity the skills needed for the design and analysis of algorithms. In this book we present some of the most beautiful algorithmic ideas in 41 articles written in colloquial, nontechnical language. Most of the articles arose out of an initiative among German-language universities to communicate the fascination of algorithms and computer science to high-school students. The book can be understood without any prior knowledge of algorithms and computing, and it will be an enlightening and fun read for students and interested adults.
http://d-nb.info/1005009791/04
Ackermann, Heiner; Röglin, Heiko; Schellbach, Ulf; Schweer, Nils
Analysis of algorithms. - In: Algorithm engineering. - Berlin [u.a.] : Springer (2010), S. 127-193
http://dx.doi.org/10.1007/978-3-642-14866-8_4
Analysis of algorithms. - In: Algorithm engineering. - Berlin [u.a.] : Springer (2010), S. 127-193
http://dx.doi.org/10.1007/978-3-642-14866-8_4
Dietzfelbinger, Martin
Ingo Wegener: seine Bücher. - In: Informatik-Spektrum. - Berlin : Springer, ISSN 1432122X, Bd. 33 (2010), 4, S. 485
http://dx.doi.org/10.1007/s00287-010-0463-1
Ingo Wegener: seine Bücher. - In: Informatik-Spektrum. - Berlin : Springer, ISSN 1432122X, Bd. 33 (2010), 4, S. 485
http://dx.doi.org/10.1007/s00287-010-0463-1
Dourado, Mitre Costa; Draque Penso, Lucia; Rautenbach, Dieter; Szwarcfiter, Jayme Luiz
Brief announcement: on reversible and irreversible conversions. - In: Distributed computing / DISC ; 24 (Cambridge, MA) : 2010.09.13-15. - Berlin [u.a.] : Springer (2010), S. 395-397
We study two types of iterative 0/1-vertex-labeling processes in arbitrary network graphs where in each synchronous round every vertex - either never changes its label from 1 to 0, and changes its label from 0 to 1 if sufficiently many neighbours have label 1, - or changes its label if sufficiently many neighbours have a different label. In both scenarios the number of neighbours required for a change depends on individual threshold values of the vertices. Our contributions concern computational aspects related to the sets with minimum cardinality of vertices with initial label 1 such that during the process all vertices eventually change their label to 1 and remain with 1 as label. We establish hardness results for the general case and describe efficient algorithms for restricted instances.
http://dx.doi.org/10.1007/978-3-642-15763-9_37
Brief announcement: on reversible and irreversible conversions. - In: Distributed computing / DISC ; 24 (Cambridge, MA) : 2010.09.13-15. - Berlin [u.a.] : Springer (2010), S. 395-397
We study two types of iterative 0/1-vertex-labeling processes in arbitrary network graphs where in each synchronous round every vertex - either never changes its label from 1 to 0, and changes its label from 0 to 1 if sufficiently many neighbours have label 1, - or changes its label if sufficiently many neighbours have a different label. In both scenarios the number of neighbours required for a change depends on individual threshold values of the vertices. Our contributions concern computational aspects related to the sets with minimum cardinality of vertices with initial label 1 such that during the process all vertices eventually change their label to 1 and remain with 1 as label. We establish hardness results for the general case and describe efficient algorithms for restricted instances.
http://dx.doi.org/10.1007/978-3-642-15763-9_37
Junqueira, Flavio Paiva; Marzullo, Keith; Herlihy, Maurice; Draque Penso, Lucia
Threshold protocols in survivor set systems. - In: Distributed computing. - Berlin : Springer, ISSN 14320452, Bd. 23 (2010), 2, S. 135-149
Many replication protocols employ a threshold model when expressing failures they are able to tolerate. In this model, one assumes that no more than t out of n components can fail, which is a good representation when failures are independent and identically distributed (IID). In many real systems, however, failures are not IID, and a straightforward application of threshold protocols yields suboptimal results. Here, we examine the problem of transforming threshold protocols into survivor-set protocols tolerating dependent failures. Our main goal is to show the equivalence between the threshold model and the core/survivor set model. Toward this goal, we develop techniques to transform threshold protocols into survivor set ones. Our techniques do not require authentication, self-verification or encryption. Our results show in one case that we can transform a threshold protocol to a subset by spreading a number of processes across processors. This technique treats a given threshold algorithm as a black box, and consequently can transform any threshold algorithm. However, it has the disadvantage that the transformation is not possible for all sets of survivor sets. The second technique instead focuses on transforming voters: functions that evaluate to a value out of a set of tallied values in a replication protocol. Voters are an essential part of many fault-tolerant protocols, and we show a universal way of transforming them. With such a transformation we expect that a large number of protocols in the literature can be directly transformed with our technique. It is still an open problem, however, if the two models are equivalent, and our results constitute an important first step in this direction.
http://dx.doi.org/10.1007/s00446-010-0107-3
Threshold protocols in survivor set systems. - In: Distributed computing. - Berlin : Springer, ISSN 14320452, Bd. 23 (2010), 2, S. 135-149
Many replication protocols employ a threshold model when expressing failures they are able to tolerate. In this model, one assumes that no more than t out of n components can fail, which is a good representation when failures are independent and identically distributed (IID). In many real systems, however, failures are not IID, and a straightforward application of threshold protocols yields suboptimal results. Here, we examine the problem of transforming threshold protocols into survivor-set protocols tolerating dependent failures. Our main goal is to show the equivalence between the threshold model and the core/survivor set model. Toward this goal, we develop techniques to transform threshold protocols into survivor set ones. Our techniques do not require authentication, self-verification or encryption. Our results show in one case that we can transform a threshold protocol to a subset by spreading a number of processes across processors. This technique treats a given threshold algorithm as a black box, and consequently can transform any threshold algorithm. However, it has the disadvantage that the transformation is not possible for all sets of survivor sets. The second technique instead focuses on transforming voters: functions that evaluate to a value out of a set of tallied values in a replication protocol. Voters are an essential part of many fault-tolerant protocols, and we show a universal way of transforming them. With such a transformation we expect that a large number of protocols in the literature can be directly transformed with our technique. It is still an open problem, however, if the two models are equivalent, and our results constitute an important first step in this direction.
http://dx.doi.org/10.1007/s00446-010-0107-3
