Kombinatorische Algorithmen
AG Algorithmen und Komplexität
>

Papiere der AG

Auf dieser Seite werden die Veröffentlichungen der Arbeitsgruppe zum Download angeboten.

 

A n^2 RNA Secondary Structure Prediction Algorithm
Markus E. Nebel and Anika Scheid, 3rd International Conference on Bioinformatics, Models, Methods and Algorithms (BIOINFORMATICS), 2012.

A Unified Approach to the Analysis of Horton-Strahler Parameters of Binary Tree Structures
Markus E. Nebel, Random Structures & Algorithms 21, 2002, 252-277. (preprint of the article published in Random Structures & Algorithms (c) Wiley 2002)

Algebraic and Combinatorial Properties of Common RNA Pseudoknot Classes with Applications
Markus E. Nebel and Frank Weinberg, Journal of Computational Biology (2012) 19(10): 1134-1150

Analysis of Branch Misses in Quicksort
Conrado Martínez, Markus E. Nebel and Sebastian Wild, ACM-SIAM Meeting on Analytic Algorithmics and Combinatorics 2015 (ANALCO15)

Analysis of Pivot Sampling in Dual-Pivot Quicksort
Analysis of Pivot Sampling in Dual-Pivot Quicksort, Markus E. Nebel, Sebastian Wild and Conrado Martínez, submitted

Analysis of Quickselect under Yaroslavskiy's Dual-Pivoting Algorithm
Sebastian Wild, Markus E. Nebel, Hosam Mahmoud, submitted

Analysis of the Free Energy in a Stochastic RNA Secondary Structure Model
Markus E. Nebel, and Anika Scheid, IEEE/ACM Transactions on Computational Biology and Bioinformatics 2011, vol. 8 no. 6, 1468-1482

Applying Length-Dependent Stochastic Context-Free Grammars to RNA Secondary Structure Prediction
Frank Weinberg and Markus E. Nebel, Algorithms Vol. 4, No. 4 (2011), 223-238

Average Case Analysis of Java 7's Dual Pivot Quicksort
Sebastian Wild and Markus E. Nebel, in L. Epstein and P. Ferragina (Eds.): ESA 2012, LNCS 7501, Springer, 2012, 825-836.

Average Case and Distributional Analysis of Dual-Pivot Quicksort
Sebastian Wild, Markus E. Nebel, Ralph Neininger, ACM Transactions on Algorithms, to appear.

Combinatorial Properties of RNA Secondary Structures
Markus E. Nebel, Journal of Computational Biology 9/3, 2002, 541 - 574

Combinatorics of RNA secondary structures with base triples
Robert Müller and Markus E. Nebel, Journal of Computational Biology, to appear.

Digital Search Trees with Keys of Variable Length
Markus E. Nebel, R.A.I.R.O. Theoretical Informatics and Applications 30 (6), 1996, 507 - 520

Engineering Java 7's Dual Pivot Quicksort Using MaLiJAn
Sebastian Wild, Markus E. Nebel, Raphael Reitzig and Ulrich Laube, ACM-SIAM Meeting on Algorithm Engineering & Experiments 2013 (ALENEX13)

Evaluating Algorithms according to their Energy Consumption
Hannah Bayer and Markus E. Nebel, CiE (Computability in Europe) 2009

Evaluating the Effect of Disturbed Ensemble Distributions on SCFG Based Statistical Sampling of RNA Secondary Structures
Anika Scheid and Markus Nebel, BMC Bioinformatics 2012, 13:159 doi:10.1186/1471-2105-13-159

Evaluation of a Sophisticated SCFG Design for RNA Secondary Structure Prediction
Markus E. Nebel and Anika Scheid, Theory in Biosciences (2011) 130: 313-336

Fast String Matching by Using Probabilities: On an Optimal Mismatch Variant of Horspool's Algorithm
Markus E. Nebel, Theoretical Computer Science 359, 2006, 329-343

Generation of RNA pseudoknot structures with genus filtration
Fenix W.D. Huang, Markus E. Nebel and Christian M. Reidys, Mathematical Biosciences (2013), 245(2), 216-225.

Identifying Good Predictions of RNA Secondary Structure
Markus E. Nebel, Proceedings of the Pacific Symposium on Biocomputing 2004, 423-434

Investigation of the Bernoulli-Model of RNA Secondary Structures
Markus E. Nebel, Bulletinof Mathematical Biology 66, 2004, 925 - 964

JAguc -- a software package for environmental diversity analyses
M. E. Nebel, S. Wild, M. Holzhauser, L. Hüttenberger, R. Reitzig, M. Sperber, T. Stoeck, Journal of Bioinformatics and Computational Biology (2011) 9 (6): 749-773

Loops in canonical RNA pseudoknot structures
Markus E. Nebel, Christian M. Reidys and Rita R. Wang, Journal of Computational Biology, December 2011, 18(12): 1793-1806

Maximum Likelihood Analysis of Algorithms and Data Structures
Ulrich Laube and Markus E. Nebel, Theoretical Computer Science, Vol. 411, No. 1 (2010), 188-212

Maximum Likelihood Analysis of Heap Sort
U. Laube and Markus E. Nebel, SIAM Workshop on Analytic Algorithmics and Combinatorics (ANALCO9)

Maximum Likelihood Analysis of the Ford-Fulkerson Method on Special Graphs
Ulrich Laube and Markus E. Nebel, to appear in Algorithmica (2015). DOI: 10.1007/s00453-015-9998-5

New Knowledge on AVL-Trees
Markus E. Nebel, Technical Report 5/99, Fachbereich Informatik, Johann Wolfgang Goethe-Universität Frankfurt, 1999

New Results on the Stack Ramification of Binary Trees
Markus E. Nebel, Journal of Automata, Languages and Combinatorics 2 (3), 1997, 161 - 175

Non Uniform Generation of Combinatorial Objects
Frank Weinberg and Markus E. Nebel, Technical Report University of Kaiserslautern, 2010

On a Statistical Filter for RNA Secondary Structures
Markus E. Nebel, Frankfurter Informatik-Berichte 5/02 (technical report)

On Quantitative Effects of RNA Shape Abstraction
Markus E. Nebel and Anika Scheid, Theory in Biosciences 128, 2009, 211-225

On the Average Complexity of the Membership Problem for a Generalized Dyck Language
Markus E. Nebel, Lecture Notes in Computer Science (FCT 1997) 1279, 1997, 352 - 363

On the Horton-Strahler Number for Combinatorial Tries
Markus E. Nebel, R.A.I.R.O. Theoretical Informatics and Applications 34, 2000, 279 - 296

On the Lexicographical Generation of Compressed Codes
Markus E. Nebel, Information Processing Letters 104, 2007, 95-100

On the Power of Subroutines for Finite State Machines
Markus E. Nebel, Journal of Automata, Languages and Combinatorics 6 (1), 2001, 51 - 74

On the Stack-Size of General Tries
J. Bourdon, M. E. Nebel and B. Vallée, R.A.I.R.O Theoretical Informatics and Applications 35, 2001, 163 - 185

Pivot Sampling in Dual-Pivot Quicksort
Markus E. Nebel, Sebastian Wild, AofA 2014

Predicting RNA Secondary Structures with Pseudoknots by MCMC Sampling
Dirk Metzler and Markus E. Nebel, Journal of Mathematical Biology 56, 2008, 161-181

Random Generation of RNA Secondary Structures According to Native Distributions
Markus E. Nebel and Anika Scheid; a revised version has been publihed at Algorithms for Molecular Biology 2011, 6:24

Random induced subgraphs of Cayley graphs induced by transpositions
Emma Yu Jin and Christian M. Reidys, Discrete Mathematics, to appear

RNA Secondary Structures in a Polymer-Zeta Model -- How Foldings Should be Shaped for Sparsification to Establish a Linear Speedup
Emma Yu Jin and Markus E. Nebel, Journal of Mathematical Biology, to appear.

Statistical RNA Secondary Structure Sampling Based on a Length-Dependent SCFG Model
Anika Scheid and Markus E. Nebel, submitted.

The Expected Order of Saturated RNA Secondary Structures
Emma Yu Jin and Markus E. Nebel, SIAM ANALCO 2012

The scientific works of Rainer Kemp (1949-2004)
P. Flajolet, M.Nebel and H.Prodinger, Theoretical Computer Science 355, 2006, 371-381

The Stack-Size of Combinatorial Tries Revisited
Markus E. Nebel, Discrete Mathematics and Theoretical Computer Science 5, 2002, 1 - 16

The Stack-Size of Tries: A Combinatorial Study
Markus E. Nebel, Theoretical Computer Science 270, 2002, 441 - 461

Topology and prediction of RNA pseudoknots
C .M. Reidys, F. W. D. Huang, J. E. Andersen, R. C. Penner, P. F. Stadler, and M. E. Nebel, Bioinformatics (2011) 27 (8): 1076-1085

Beweistechniken (WS 12/13)

Die Veranstaltung Beweistechniken ist ein Bestandteil des Moduls Entwurf und Analyse von Algorithmen für Angewandte Informatiker, die dazu beitragen soll, die Vorkenntnisse verschiedener Hörergruppen im Bereich der Mathematik, insbesondere dem Beweisen, anzugleichen.

Beweistechniken wird dieses Semester von Sebastian Wild betreut.

Aktuelles

  • Der Abgabezeitraum für Blatt 6 wird bis Montag, 3.12, 12:00 Uhr verlängert.
  • Errata Blatt 5: In Aufgabe 18 soll überall m statt p stehen.

Termine

Beweistechniken findet stets Freitags 08:15 Uhr in Raum 42/110 statt.

Die ersten beiden Termine (19. und 26. Oktober) bestehen aus einer Vorlesung. Ab dann (erstmals am 2. November) wird Dominique Ufer in einer Saalübung die Abgaben zu den Übungsblättern besprechen.

Übungsblätter








Aus den Abgaben müssen auf jedem Blatt 50% der Pflichtpunkte erreicht werden. Bewertet wird die sinnvolle Bearbeitung der Aufgaben. Durch freiwillige Aufgaben können Sie zusätzliche Punkte bekommen.

  • Die Ãœbung vom 10.01.13 wird um eine Woche auf Do, 17.01.13 verschoben. Die Abgabefrist für Blatt 6 wird bis Mo, 14.01. verlängert.
  • Aufgrund des Feiertags wird die erste Ãœbung vom 1.11. auf Di 30.10 15:30 Uhr vorverlegt.
    Wer  da keine Zeit hat, möge einfach bei Sebastian vorbeikommen.
  • Die erste Ãœbung findet Donnerstag, 1. November, 13:45 Uhr in 48-654 statt.
  • Das erste Ãœbungsblatt ist online:

Die Ãœbungen zur Vorlesung finden alle zwei Wochen jeweils am Donnerstag ab 13:45 Uhr im Raum 48-654 statt. Erster Ãœbungstermin ist der 1. November.

Übungsblätter










Im Wintersemester 2012/13 findet die Vorlesung wöchentlich von 10:00 bis 11:30 im Raum 48-654 statt.