Maschinennahe Programmierung - Testergebnis vom 22.12.2011

Student ID Grade Passed
46393 1,3 YES
21049777 3,7 YES
21153872 1,7 YES
21153903 1,7 YES
21153910 3,7 YES
21154277 3,3 YES
21155244 1,3 YES
21155749 3,3 YES
21155930 3,3 YES
21156068 5 NO
21156075 1,7 YES
21156649 2 YES
21156786 5 NO
21157026 1,7 YES
21157199 5 NO
21157296 3,3 YES
21157331 2 YES
21157374 2 YES
21157410 2 YES
21157422 2,3 YES
21157469 3,3 YES
21157584 2,3 YES
21157664 2,3 YES
21157747 2 YES
21158090 1,7 YES
21158112 4 YES
21158277 2,3 YES
21158377 2 YES
21158378 3,3 YES
21158485 2 YES
21158569 3 YES
21159202 3,7 YES
21159404 1,7 YES
21159510 5 NO
21160026 1,7 YES
21160305 3 YES
21160335 2,7 YES
21160447 3,7 YES
21160478 1,3 YES
21160533 2,7 YES
21160732 2,3 YES
22157353 3 YES
unknown 3,3 YES

Discrete Algebraic Structures - Lecture 9

Themen:

• Teilbarkeitslehre: ggT, Euklidischer Algorithmus, Satz von Bezout
• Restklassenringe modulo n
• Potenzieren in Z modulo n.

Computational Biology - Lecture 9

Topics:

• Gröbner bases: existence, minimal and reduced bases
• Hilbert's Basis Theorem.

Seminar: Constructive Algebraic Geometry

Topics:

• Nakayama's Lemma and its application to local rings
• Regular local rings and nonsingular varieties.

Seminar: Constructive Algebraic Geometry

Topics:

• Local orders, localization of polynomial rings
• ring of rational functions regular at a point of an affine variety
• standard bases in localized polynomial rings
• application to code ideals.

Discrete Algebraic Structures - Lecture 8

Themen:

• Ringe, Ring der ganzen Zahlen, Polynomring
• Division mit Rest
• ggT
• Euklidischer Algorithmus.

Computational Biology - Lecture 8

Topics:

• Monomial orders
• division algorithm in polynomial rings
• Dickson's Lemma
• Gröbner bases.

Seminar: Constructive Algebraic Geometry

Topics: Local rings and discrete valuation rings.

Discrete Algebraic Structures - Lecture 7

Themen:

• Mengenpartitionen, Stirlingzahlen 2. Art
• Zahlentheoretische Partitionen.

Computational Biology - Lecture 7

Topics:

• EM algorithm for HMM 
• Polynomial rings and term orders.

Discrete Algebraic Structures - Lecture 6

Themen:

• Kombinationen
• Permutationen
• Mengentheoretische Partitionen

Computational Biology - Lecture 6

• Hidden Markov model

• Example: CpG islands.

Seminar: Constructive Algebraic Geometry

Topics:

• Functions on affine varieties
• rings of regular functions
• valuation rings and basic properties.

Discrete Algebraic Structures - Lecture 5

Themen:

• Überabzählbarkeit der Menge der reellen Zahlen
• Kontinuumshypothese
• Elementare Zählprinzipien
• Doppelte Abzählung, Inklusion-Exklusion
• k-Kombinationen von n, Binomialzahl.

Computational Biology - Lecture 5

Topics:

• General algebraic statistical models, DiaNA
• maximum likelihood estimation (MLE)
• fully observed toric Markov model
• fully observed Markov model, MLE.

Seminar. Constructive Algebraic Geometry

Topics:

• graded rings and homogeneous ideals
• graded modules and graded homomorphisms
• graded resolutions and Hilbert's syzygy theorem
• Hilbert function and Hilbert polynomial.

Discrete Algebraic Structures - Lecture 4

Themen:

• Permutationen vom Grad n, Zykeldarstellung, Signum
• vollständige Induktion
• Peano-Axiome, Aufbau der natürlichen Zahlen
• Abzählbarkeit
• 1. Diagonalisierungsmethode (Cantor).

Computational Biology - Lecture 4

Topics:

• Normal cones and normal fans
• pollytope algebra
• Newton polytopes
• polytope propagation 
• finding the optimal alignments for all scores - example

Seminar: Constructive Algebraic Geometry

Topics:

• Evaluation codes.
• Reed-Muller codes and Reed-Solomon codes as evaluation codes.
• Hermitian codes.
• A result of van Lint on evaluation codes.

Discrete Algebraic Structures - Lecture 3

Themen:

• Digraphen, Wege und Kreise,
• Äquivalenzrelationen, Äquivalenzklassen, Quotientenmengen, Partitionen
• Halbordnungen, halbgeordnete Mengen
• Abbildungen
• Gleichheit und Komposition von Abbildungen
• Spezielle Abbildungen

Computational Biology - Lecture 3

Topics - Combinatorial Geometry:

• convex sets and polytopes, affine sets, cones, dimension
• hyperplanes, supporting hyperplanes
• faces, normal cones, and normal fan of polytope.

Seminar: Constructive Algebraic Geometry

Topics:

• projective n-space
• homogeneous ideals
• projective algebraic sets
• Zariski topology
• irreducibility and dimension

Discrete Algebraic Structures - Lecture 2

Themen:

• Mengen, Mengenverknüpfungen, Rechenregeln, Potenzmenge, Mengensysteme, Antinomien
• Geordnete Paare, Paarmengen, n-Tupel, kartesisches Produkt
• Relationen, homogene Relationen, inverse Relation, Allrelation, Gleichheitsrelation
• Komposition von Relationen, Rechenregeln.

Computational Biology - Lecture 2

Topics:

• Sum-product decomposition of marginal probability
• Tropicalization of sum-product decomposition
• Needleman-Wunsch algorithm, example.

Discrete Algebraic Structures - Lecture 1

Themen:

• Aussagen, Junktoren, Aussagenvariablen, Aussageformen, Erfüllbarkeit, Tautologien, Rechengesetze, Syntax und Semantik.
• Prädikate, All- und Existenzquantor, Negation, freie und gebundene Variablen und deren Umbenennung.

Computational Biology - Lecture 1

Topics:

• Representation of alignment
• scoring schemes,
• pair hidden Markov model,
• tropicalization of scoring function.

Vorlesung: Computational Biology

Algebraische Methoden

Zeit und Ort:

Donnerstag, 16:00 - 17:30,

Beginn:

27. Oktober 2011 - 2. Vorlesungswoche.

Sprache:

Englisch

Empfohlene Vorkenntnisse:

Grundkenntnisse aus Diskreter Mathematik, Linearer Algebra und Analysis.

Inhalt:

• Algebraische Geometrie (Gröbnerbasen, algebraische Varietäten, Eliminationstheorie)
• Algebro-statistische Modelle (lineare und torische Modelle, Markov-Modelle, Invarianz, statistische Inferenz)
• Anwendungen: Alignment biologischer Sequenzen, Hidden-Markov-Modell.
  

Qualifikationsziele:

• Kenntnisse: Vertiefte Kenntnisse auf einem neuen Gebiet zwischen algebraischer Geometrie und Statistik.
• Fertigkeiten. Theorie geleitetes Anwenden algebro-statistischer Methoden.
• Kompetenzen: Formalisieren von Problemstellungen, Bewerten unterschiedlicher Lösungsansätze, Einsatz von Computeralgebrasystemen.
  

Literatur:

• L. Pachter, B. Sturmfels: Algebraic Statistics for Computational Biology. Cambridge Univ Press, 2004.
  

Studien/Prüfungsleistungen:

Mündliche Prüfung.

Vorlesung: Diskrete Algebraische Strukturen

Diskrete Algebraische Strukturen

Zeit und Ort:

Freitag, 8:00 bis 9:30 h, SBS 95 - H0.16

Beginn:

28. Oktober 2011 - 2. Vorlesungswoche.

Inhalt:

• Elementare Abzählungsprinzipien, Schubfachprinzip, Prinzip der doppelten Abzählung, Prinzip der Inklusion-Exklusion
• Kombinationen, Permutationen, Bellzahlen, Typisierung von Permutationen
• Mengenpartitionen, Zahlpartitionen, Stirlingzahlen
• Arithmetik der ganzen Zahlen, Ringe, Schedules für Laufschleifen.
• Teilbarkeitslehre, Euklidischer Algorithmus, Satz von Bezout, Primzahlen, Hauptsatz der Arithmetik, Gödelisierung.
• Restklassenringe, lineare Kongruenzensysteme, Zerlegung von Restklassenringen, modulare Rechenwerke.
• Einheiten in Ringen, Eulersche Phi-Funktion, Integritätsringe, Körper, moderne Kryptographie (RSA).

Qualifikationsziele:

• Kenntnisse: Grundlegende Theorie und Anwendung algebraischer Grundstrukturen.
• Fertigkeiten: Beherrschung grundlegender Begriffe, Methoden und Beweisverfahren.
• Kompetenzen: Verwendung von rudimentären Methoden in informatischen und ingenieurwissenschaftlichen Anwendungen. Abbildung einer allgemeinen Problemstellung auf ein Teilproblem. Befähigung zum selbständigen und effizienten Lernen.

Literatur:

• K.-H. Zimmermann: Diskrete Mathematik, BoD, 412 S., 2006 - digital verfügbar.
• R. Haggerty: Diskrete Mathematik, Addison Wesley, 2004.
• F. Kasch, B. Pareigis: Grundbegriffe der Mathematik, Fischer Verlag, 1991.
• S. Singh: Fermats letzter Satz - Die abenteuerliche Geschichte eines mathematischen Rätsels, Hanser, 1998.
• D. Hofstaedter: Gödel, Escher, Bach, dtv Verlag, 1996, (5. Auflage).

Leslie Lamport @ TUHH

Leslie Lamport an der TUHH (20. Okt, 17 Uhr) Speaker: Dr. Leslie Lamport, Microsoft Research
Title: The PlusCal Algorithm Language

Time: Oct. 20, 17:00
Location: Dietze Auditorium (H.016)

Abstract:
Algorithms are different from programs and should not be described with programming languages. For example, algorithms are usually best described in terms of mathematical objects like sets and graphs instead of the primitive objects like bytes and integers provided by programming languages. Until now, the only simple alternative to programming languages has been pseudo-code.

PlusCal is an algorithm language based on TLA+. A PlusCal algorithm is automatically translated to a TLA+ specification that can be checked with the TLC model checker or reasoned about formally. (No knowledge of TLA+ is assumed.)

PlusCal makes pseudo-code obsolete.



Bio:
Dr. Leslie Lamport is a prinicipal researcher at Microsoft Research in
Mountain View, California since 2001. Prior to joining Microsoft, he held positions at Mitre, Marlboro College, SRI International, DEC, and Compaq. Dr. Lamport received a number of prestigious awards, including the IEEE Emanuel R. Piore Award for seminal contributions to the theory and practice of concurrent programming and fault
tolerant computing in 2004 and the IEEE John von Neumann Medal for pioneering work in distributed and concurrent algorithms in 2008. He holds five honorary doctorates, from the universities of Rennes, Kiel, Lausanne, Lugano, and Nancy. He is elected member of the National Academy of Engineering as well as the National Academy of Science, and, among other contributions, also known as the author of LaTeX, a widely used document preparation system.

Diskrete Mathematik - Monographie

Kurzfassung in Deutsch

Das Buch entstand aus Vorlesungen über Diskrete Mathematik, die der Autor an der Technischen Universität Hamburg für Studierende der Informatik in den letzten Jahren gehalten hat. Dieses Werk behandelt neben den Grundlagen der Diskreten Mathematik auch eine Reihe von weiterführender Themen, deren Kenntnis heute von jedem Informatiker und Mathematiker erwartet wird. Das Buch eignet sich für das Selbststudium und als Textbuch zum Gebrauch neben der Vorlesung.

Die Diskrete Mathematik ist die Mathematik der endlichen Mengen - besser gesagt: der endlichen Konfigurationen unter Nebenbedingungen. Dabei geht es u.a. um die Abzählung, Konstruktion und Existenz von Konfigurationen und das Rechnen mit Konfigurationen. Wichtige Teilgebiete der Diskreten Mathematik sind die Kombinatorik, Graphentheorie, Verbandstheorie, Codierungstheorie, Kryptographie und kombinatorische Optimierung. Zudem stellt die Diskrete Mathematik Algorithmen und Datenstrukturen bereit und ist damit eng verknüpft mit der Theoretischen Informatik.

---

SWD-Schlagwörter:		Algebra , Arithmetik , Kombinatorik , Graphentheorie , Codes
Freie Schlagwörter (Englisch):		algebra , arithmetics , combinatorics , graph theory , codes
MSC - Klassifikation:		68-XX
Institut:		Rechnertechnologie E-13
DDC-Sachgruppe:		Mathematik
Dokumentart:		Buch (Monographie)
ISBN:		3-8334-5529-2
Quelle:		Books on Demand GmbH, Norderstedt
Sprache:		Deutsch
Erstellungsjahr:		2006
Publikationsdatum:		05.10.2011
Lizenz:		Veröffentlichungsvertrag für Publikationen mit Print on Demand

Erata und Lösungen zu den Selbsttestaufgaben: http://www.tu-harburg.de/ti6/mitarbeiter/khz/Books.html

 Copyright: K.-H. Zimmermann

http://doku.b.tu-harburg.de/volltexte/2011/1118/
 
https://katalog.b.tu-harburg.de/DB=1/XMLPRS=N/PPN?PPN=669373419

Prüfungsplan - Mündliche Prüfungen

Berechenbarkeit & Komplexität
Mittwoch, 12. Oktober, ab 10 Uhr, SBS 95 - Raum 3006

• 10:00 h: Jan Holste
• 10:30 h: Andre De Cruz Guerreiro
• 11:00 h: Marcel Gehrke
• 11:30 h: Robert Oehlmann
• 15:00 h: Jan Winkelmann

Algebraische Geometrie & Statistik
Donnerstag, 13. Oktober, ab 9 Uhr, SBS 95 - Raum 3006

•  9:30 h: Sergej Sturn 
• 10:30 h: Deniz Atac

Repetitorium: Berechenbarkeit & Komplexität

Termine:

• 5. Oktober, 2011, 10:00 - 11:30 h, 14:00 - 15:30 h, D-SBS 95, D0010
• 6. Oktober, 2011, 10:00 - 11:30 h, 14:10 - 15:45 h, H-SBS 95, H0.10

Die mündlichen Prüfungen werden in der Woche darauf stattfinden (12. Okt.).

Results - DM I Exam

Korrektur - siehe Kommentar


17387 3,3
41722 5,0 (nicht bestanden)
43214 3,3
43240 5,0 (nicht bestanden)
43245 3,0
2147328 2,7
20805940 3,0
21046098 2,0
21046127 5,0 (nicht bestanden)
21046148 5,0 (nicht bestanden)
21047113 5,0 (nicht bestanden)
21047985 3,3
21048521 3,0
21048568 1,7
21048828 2,7
21050233 5,0 (nicht bestanden)
21050258 2,0

Results - DM II Exam

17852 3,3
22383 5,0 (nicht bestanden)
29381 1,7
31691 1,0
34097 3,0
41822 3,0
41830 1,3
41832 1,3
43191 1,7
43194 1,7
43197 1,3
43198 2,0
43200 2,0
43202 2,7
43203 2,0
43206 3,3
43209 2,0
43210 2,3
43214 2,3
43232 1,7
43240 2,3
43246 2,0
43252 1,7
43258 1,3
43460 2,3
43930 2,0
43935 1,3
44514 1,7
44851 2,7
44859 1,7
45109 2,3
46065 2,3
2062484 2,0
2104728 2,3
20422423 2,3
20624957 2,7
20730151 2,0
20731512 2,3
20835940 3,0
20836013 3,0
20836843 2,3
20836920 5,0 (nicht bestanden)
20837236 2,7
20837348 2,3
20837618 3,0
20838374 1,7
20885682 1,7
21045035 2,3
21045749 2,0
21045847 1,3
21046136 2,3
21046148 3,3
21046393 2,3
21046810 2,7
21046887 2,7
21046925 2,3
21047049 1,7
21047113 3,0
21047714 2,0
21047946 2,3
21047985 3,3
21048521 2,3
21048568 2,3
21048796 1,0
21048818 1,3
21048828 2,0
21049336 3,0
21049441 2,3
21049824 1,3
21050233 5,0 (nicht bestanden)
21050258 2,3
21050392 3,0
0 0,0

Repetitorium - Diskrete Mathematik I

Im Rahmen des Repetitoriums zur Diskreten Mathematik I (Diskrete Algebraische Strukturen) wurden zwei weitere Sitzungen anberaumt:

• Mi., 14.09., 10 h, SBS 95 H, Raum 0.07,
• Fr., 16.09., 10 h, SBS 95 E, Raum 3032.

Written Exams

Bioinformatik: 13. 9. 2011, 11:30 h, Poolräume E2039P5a u. E2042P5b Diskrete Mathematik I (Diskrete Algebraische Strukturen): 21. 9. 2011, 9:00 h, Audimax II Diskrete Mathematik II (Graphentheorie &Optimierung): 12. 9. 2011, 13:00 h, Audimax I

Issues - Computational Informatics MS

The course „Personalmanagement und Organisationsentwicklung“ from Prof. Ringle will take place in the summer term 2011 and not as published in the winter term 2011/12.

Master-Studiengang Computational Informatics

Der Masterstudiengang setzt den gleichnamigen Bachelorstudiengang fort und bereitet zugleich auf eine Promotion vor. Er bildet hochqualifizierte Generalisten für den Umgang mit nachhaltigen, intelligenten programmierbaren Systemen aus. Absolventinnen und Absolventen sind in der Lage, selbständige und anspruchsvolle Tätigkeiten in Industrie, Verwaltung und Wissenschaft wahrzunehmen und insbesondere leitende Funktionen auszufüllen.
Die Absolventinnen und Absolventen verfügen über Kompetenzen, die sie in die Lage versetzen,

1. komplexe Aufgaben im Bereich der Informationstechnologie (IT) zu übernehmen und dabei das theoretische Wissen aus den Bereichen Software- und Hardwaretechnik sowie Mathematische Modellierung erfolgreich in die Praxis umzusetzen;
2. in leitender Funktion an informationstechnischen Projekten mitzuwirken;
3. Prozesse, Systeme und innovative Technologien im Bereich Informationstechnologie zu entwickeln, analysieren und kritisch zu bewerten;
4. auch nichttechnische Auswirkungen der Ingenieurtätigkeit im sozioökonomischen Kontext systematisch zu reflektieren.

Die bereits im Bachelor-Studium erworbenen Schlüsselqualifikationen in den Bereichen Intelligence Engineering, Mathematical Computing und Software Engineering werden innerhalb des Master-Studiengangs erweitert und vertieft. Zudem soll die Vertiefung Management und Ökonomie einen Einstieg in die höhere Führungsebene eines Unternehmens gestatten.

Bachelor-Studiengang Computational Informatics

Der Bachelor-Studiengang Computational Informatics (CI-BC)  bietet ein wissenschaftlich fundiertes, Grundlagen orientiertes Studium mit den Schwerpunkten Softwaretechnik, Mathematik und Betriebswirtschaftslehre. Das Bachelor-Studium ist mit englischsprachigen Lehrveranstaltungen international ausgerichtet und offeriert ein ausgewogenes Verhältnis von Theorie und Praxis. Studienanfänger benötigen keine Programmierkenntnisse.
Die Absolventinnen und Absolventen besitzen im Einzelnen:

1. Grundkenntnisse in den Themenfeldern Angewandte Mathematik und Betriebswirtschaftslehre.
   
2. Fundierte Kenntnisse auf den Gebieten Diskrete Mathematik, Software- und Hardwaretechnik sowie Theoretische Informatik.
   
3. Vertiefte Kenntnisse in einem der Bereiche Intelligence Engineering, Mathematical Computing oder Software Engineering.
   
4. Die Fähigkeit zu wissenschaftlichem Arbeiten und eigenständiger Erweiterung des Fachwissens.
   

Absolventen werden in die Lage versetzt, komplexe Problemstellungen mit informationstechnischen Methoden unter Berücksichtigung technischer, ökonomischen und gesellschaftlicher Rahmenbedingungen zu behandeln und algorithmisch umzusetzen.
Eine Besonderheit des Studiengangs ist ein sechswöchiges Praktikum, das in der Industrie oder an der Universität absolviert werden kann. Die Studierenden sollen sich auf diese Weise vertiefte praktische oder theoretische Kenntnisse erarbeiten.
Die Gesellschaft für Informatik (GI) klassifiziert CI-BC als so genannten Typ-1-Studiengang, d.h., als einen Informatik-Studiengang mit einem zwei Drittel Anteil an Informatik - demgegenüber ist der Studiengang Informatik-Ingenieurwesen (IIW-BC) ein so genannter Typ-3-Studiengang mit einem ein Drittel Anteil an Informatik.
Der Bachelor-Abschluss ist berufsqualifizierend und ermöglicht ein Anschlussstudium im gleichnamigen Master-Studiengang. Die Absolventen sind berechtigt, die Berufsbezeichnung „Ingenieur“ im Sinne des Ingenieurgesetzes (IngG) der Freien und Hansestadt Hamburg zu führen.

Thesis: Shortest-path algorithm via CUDA

Graphics Processor Unit (GPU) are general purpose stream processor capable of very high computation and data throughput. In certain applications requiring massive vector operations, this can yield several orders of magnitude higher performance than a conventional CPU.

This task comprises of parallel implementation of Floyd-Warshall algorithm using CUDA. Floyd-Warshall algorithm is used to find shortest path in weighted graph. This task should be implemented by matrix-matrix multiplication approach and using CUBLAS library functions (if possible).

The design has to be optimized in terms of throughput and latency requirements.

Prerequisites: C programming.

Contact: Muhammad Kashif Hanif

muhammad.hanif@tu-harburg.de

Thesis: Converting OpenCL into CUDA

Compute Unified Device Architecture (CUDA) is mature tool for developing high performance scientific applications on the GPU. OpenCL is open standard for cross-platform, parallel programming of heterogeneous processing systems which proposes a model which maps well to contemporary GPU architectures and a GPU programming model that bears close similarities to CUDA. OpenCL has attracted vendor support, with implementations available from NVIDIA, AMD , Apple and IBM. A tool for porting CUDA program to OpenCL called SWAN is already developed.

This task comprises porting of OpenCL program to CUDA and to test performance of application on OpenCL and on CUDA platform after porting. The design has to be optimized in terms of throughput and latency requirements of the system.

Prerequisites: C programming.

Contact: Muhammad Kashif Hanif

muhammad.hanif@tu-harburg.de

Thesis: Implementation of CUBTAS library

Basic Linear Algebra Subprograms (BLAS) is a de facto application programming interface standard for publishing libraries to perform basic linear algebra operations such as vector and matrix multiplication. BLAS functionality is divided into three levels.

1. Vector operations
2. Matrix-Vector operations
3. Matrix-Matrix Operations

NVIDIA has implemented a similar library, called CUBLAS (Compute Unified Basic Linear Algebra Subprograms), for parallel programming on GPUs. The task is to implement a new library CUBTAS (Compute Unified Basic Tropical Algebra Subprograms) which performs similar operations to CUBLAS but using tropical algebra (min-plus algebra).

The design has to be optimized in terms of throughput and latency requirements of the system.

Prerequisites: C programming.

Contact: Muhammad Kashif Hanif

muhammad.hanif@tu-harburg.de

Thesis: Parallel implementation of algorithm for phylogeny (ClustalW)

Sequence alignment is the fundamental operation in molecular biology for comparing bio molecular sequences to identify regions of similarity that consequences of structural, functional, or evolutionary relationships. ClustalW is a progressive alignment algorithm for multiple sequence alignment.

• Step 1: Determine all pairwise alignment between sequences and determine degrees of similarity between each pair.
• Step 2: Construct a guide tree.

• Step 3: Combine the alignments starting from the most closely related groups to the most distantly related groups, using the “once a gap always a gap” rule.

Graphics Processor Unit (GPU) are general purpose stream processor capable of very high computation and data throughput. In certain applications requiring massive vector operations, this can yield several orders of magnitude higher performance than a conventional CPU.

This work comprises of parallel implementation of ClustalW algorithm using CUDA. The resulting implementation design has to be optimized in terms of throughput and latency requirements.

Prerequisites: C programming.

Contact: Muhammad Kashif Hanif

muhammad.hanif@tu-harburg.de

Courses - Winter Term 2011/12

Computational Biology (Rechnerorientierte Biologie)		E-13
Karl-Heinz Zimmermann
Donnerstag, 16:00-17:30 in N - ES40 Raum 0008

Diskrete Algebraische Strukturen		E-13
Karl-Heinz Zimmermann
Freitag, 8:00-9:30 in H - SBS95 Raum H0.16

Exercise: Computational Biology (Übung: Rechnerorientierte Biologie)		E-13
Karl-Heinz Zimmermann
Dienstag, 12:15-13:00 in D - SBS95 Raum D0010

Übung: Diskrete Algebraische Strukturen		E-13
Karl-Heinz Zimmermann und Mitarbeiter
Donnerstag, 13:15-14:00 in H - SBS95 Raum H0.07
Montag, 13:15-14:00 in H - SBS95 Raum H0.09

Projekt based learning: Maschinennahe Programmierung **		E-13
Karl-Heinz Zimmermann, Ralf Möller und Mitarbeiter
Donnerstag, 9:45-11:15 in H - SBS95 Raum H0.03

** Diese Veranstaltung findet in der Orientierungswoche nicht statt.

Revision Course (Repetitorium) - Linear Algebra

Here are the dates for the three classes to meet in advance of the exam:

1. Monday 8th of August at 10:00 a.m.

2. Wednesday 10th of August at 10:00 a.m.

3. Friday 12th of August at 10:00 a.m.

Room: SBS 95, 3032.

There are 5 days till Wednesday 17th of August to review and get ready for the exam.

Tutor: Arash Massoudi

Book on Computability Theory

License
In terms of citation, please refer to
URN: urn:nbn:de:gbv:830-tubdok-11072
URL: http://doku.b.tu-harburg.de/volltexte/2011/1107/


Preface

Why do we need a formalization of the notion of algorithm or effective computation? In order to show that a specific problem is algorithmically solvable, it is sufficient to provide an algorithm that solves it in a sufficiently precise manner. However, in order to prove that a problem is in principle not solvable by an algorithm, a rigorous formalism is necessary that allows mathematical proofs. The need for such a formalism became apparent in the works of David Hilbert (1900) on the foundations of mathematics and Kurt Gödel (1931) on the incompleteness of elementary arithmetic.

The first investigations in the field were conducted by the logicians Alonzo Church, Stephen Kleene, Emil Post, and Alan Turing in the early 1930s. They provided the foundation of computability theory as a branch of theoretical computer science. The fundamental results established Turing computability as the correct formalization of the informal idea of effective calculation. The results led to Church’s thesis stating that ”everything computable is computable by a Turing machine”. The theory of computability has grown rapidly from its beginning. Its questions and methods are penetrating many other mathematical disciplines. Today, computability theory provides an important theoretical background for logicians and computer scientists. Many mathematical problems are known to be undecidable such as the word problem for groups, the halting problem, and Hilbert’s tenth problem.

This book is a development of class notes for a two-hour lecture including a one-hour lab held for Bachelor students of Computer Science at the Hamburg University of Technology in the summer term 2011. The aim of the course was to present the basic results of computability theory, including mathematical models of computability (Turing machine, unlimited register machine, and LOOP and GOTO programs), primitive recursive and partial recursive functions, Ackermann’s function, Gödel numbering, universal functions, smn theorem, Kleene’s normal form, undecidable sets, theorems of Rice, and word problems. The manuscript partly follows the notes taken by the author during his studies at the University of Erlangen-Nuremberg. I would like thank again my teachers Martin Becker† and Volker Strehl for giving inspiring lectures in this field.

First of all, I would like to express my thanks to my colleague Ralf Möller for valuable comments. I am also grateful to my PhD student Mahwish Saleemi for conducting the lab and to our technical engineer Wolfgang Brandt for valuable technical support. Finally, I thank my students for their attention, their stimulating questions, and their dedicated work.

ccAlign - Softwarepaket für Sequenzalignment (Studienarbeit)

In der Biologie sind Sequenzalignments von großer Bedeutung. Sie ermöglichen die Untersuchung von Proteinen auf strukturelle, evolutionäre und funktionelle Verwandtschaft und liefern Erkenntnisse, die in verschiedenen Bereichen der Molekularbiologie wie etwa der Klassifizierung von Proteinen oder der Behandlung von auf Proteindefekten basierenden Krankheiten Anwendung finden.

Die Komplexität von Proteinen und die daraus resultierenden Datenmengen motivieren die Verwendung von computergestützten Lösungsverfahren. Die Analyse von Sequenzen ist somit auch eine Disziplin der Bioinformatik, die sich mit der informationstechnischen Verarbeitung von auf Lebenswissenschaften basierenden Daten beschäftigt und für viele der in diesen Bereichen auftretenden Probleme algorithmische Lösungsstrategien formuliert.

Einige dieser Lösungsverfahren sind grundlegende Techniken in der Sequenzanalyse und werden nicht nur in den Grundlagen der Bioinformatik behandelt, sonder auch in der Praxis angewandt: Online-Dienste wie ClustalW oder BLAST sind gängige Plattformen, auf denen diese Alignment-Algorithmen eingesetzt und Anwendern zur Verfügung gestellt werden. Diese Dienste genügen professionellen Ansprüchen und richten sich an versierte Anwender, während sie für die Anwendung im Rahmen des Studiums weniger geeignet sind. Ohne nötige Vorkenntnisse ist eine im biologischen Sinne sachgemäße Bedienung oder die Beurteilung eines Ergebnisses kaum möglich.

Das Ziel der Studienarbeit ist die Entwicklung einer grafischen Benutzeroberfläche für die gegebene Sequenzalignment-Software ccalign. Diese implementiert einige Alignment-Verfahren, die zu den Grundlagen der Bioinformatik gehören. Im Vordergrund der Aufgabenstellung steht die Verbesserung und Erleichterung der Programmbedienung. Ferner soll das als Vorlage dienende Programm um zusätzliche Funktionen ergänzt werden, so dass es für Lehrzwecke geeignet ist und autodidaktischen Ansprüchen gerecht wird. Hilfsfunktionen, die über den Standardumfang von GUI-Funktionen hinausgehen, sollen hinzugefügt werden um Zusammenhänge und Funktionsweisen der einzelnen im Programm implementierten Verfahren zu beschreiben, so dass Anwender das Programm begleitend für Übungen und Klausurvorbereitungen verwenden können.

cand. ing. Mark Schlüter

Mitschreiben der Klausur 'Diskrete Mathematik II' im Ausland

Mitschreiben ist möglich unter folgenden Randbedingungen:

• Bescheinigung über Auslandsaufenthalt,
• Aufsicht durch vertrauensvolle Person,
• zeitgleiches Schreiben,
• übliche Klausurmodalitäten (Zeit- und Hilfsmittel-Beschränkung).

Die Aufsichtsperson muss mich im Vorfeld per Email kontaktieren. Die geschriebene Klausur muss per Post an mich geschickt werden; vorher sollte die Aufsicht eine Kopie anfertigen.

Computability & Complexity - Lecture 13

Today, the last lecture was concerned with the word problems for Thue systems and semigroups, diophantine sets, and Hilbert's 10th problem.

A new version of the manuscript including the index is available.

Repetitorien - Diskrete Mathematik

Repetitorium zu DM II (Graphentheorie und Optimierung):

4 Termine:
1. Dienstag, 30. August, 10 h, SBS 95-3032
2. Dienstag, 30. August, 14 h, SBS 95-3032
3. Mittwoch, 31. August, 10 h, SBS 95-3032
4. Mittwoch, 31. August, 14 h, SBS 95-3032

Inhalt: Rechnen von Klausuraufgaben.


Repetitorium zu DM I (Diskrete Algebraische Strukturen):

2 Termine:
1. Donnerstag, 1. September, 10 h, SBS 95-3032
2. Donnerstag, 1. September, 14 h, SBS 95-3032

Inhalt: Rechnen von Klausuraufgaben.

Tutor: Ralf Dittombee.

Discrete Mathematics II - Lecture 14

Examples of linear programming by using Maple. The worksheet is available under Stud.Ip.

Tutorien für Zweitsemester des Studiengangs CI-Bachelor

1. Linear Algebra
Tutor: Hr. Massoudi
Erstes Treffen: 4. August, 10 h, SBS95-3032

2. Diskrete Algebraische Strukturen
Tutor: Hr. Dittombee
Erstes Treffen: 7. September, 10 h, SBS95-3032

3. Rechnerarchitektur
Tutor: Hr. Amiri
Erstes Treffen: 11. August, 10 h, SBS95-3023

Pro Tutorium sind 4 Treffen à 90 Minuten geplant.

 

Computability and Complexity - Lecture 12

Theorem of Rice-Shapiro, word problem for semi-Thue systems.

Computability and Complexity - Lecture 11

Recursive and recursively enumerable sets.

Discrete Mathematics II - Lecture 13

Letzten Mittwoch: Lösen von LPs durch Auflistung aller Ecken, ganzzahlige lineare Programmierung, total unimodulare Matrizen, ganzzahlige Polyeder, bipartite Graphen und total unimodulare Matrizen, Beweis des Satzes von König-Egervary mithilfe des Dualitätssatzes der linearen Programmierung.

Discrete Mathematics II - Lecture 12

Lineare Optimierung:

• Graphische Lösung von 2D-Problemen
• Dualitätssatz
• Die Rolle der Ecken.

Computability & Complexity - Lecture 10

Topics:

• decidable and undecidable sets
• diagonalization and reduction
• prototype set K
• halting problem
• theorem of Rice.

Discrete Mathematics II - Lecture 11

Themen:

1. Kombinatorische Optimierung:

• Genetische Algorithmen
• Beispiel: Rucksackproblem

 2. Lineare Optimierung

• Einführende Beispiele
• Allgemeine Darstellung, kanonische und Standard-Form.

Computability & Complexity - Lecture 9

Turing Machine:

• abstract Turing machine
• Post-Turing programs
• simulation of GOTO programs by Post-Turing programs

Discrete Mathematics II - Lecture 10

Themen:

• Heuristische Methoden
• Hill Climbing
• Simulated Annealing
• Beispiele

Computability & Complexity - Lecture 8

Topics:

• Universal functions
• Kleene's normal form theorem

Discrete Mathematics II - Lecture 9

Themen:

• Rucksackproblem
• Backtracking
• Bounding-Funktion
• rationales Rucksackproblem
• Rundreiseproblem
• Knotenüberdeckungsproblem

Computability & Complexity - Lecture 7

Topics:

• Gödel numbering of GOTO programs
• parametrization (Kleene's smn theorem)

Discrete Mathematics II - Lecture 8

Themen:

• P und NP
• NP-Vollständigkeit
• Beispiele

Computability & Complexity - Lecture 6

Topics:

• Small Ackermann functions
• Loop programs and runtime
• Loop hierarchy
• Ackermann's function and growth

Discrete Mathematics II - Lecture 7

Heutige Themen:

• Satz von Menger
• Satz von König-Egervary
• Satz von Hall.

Computability and Complexity - Lecture 5

Topics:

• Goto programs
• Goto computability
• Goto-2 programs
• Church's thesis.

Discrete Mathematics II - Lecture 6

Themen:

• Algorithmus von Ford-Fulkerson
• Ganzzahligkeitssatz
• Beispiele

Computability & Complexity - Lecture 4

Topics:

• number theoretic functions
• loop programs and loop computable functions
• partial recursive functions
• (unbounded) minimalization
• partial recursive functions are URM computable

Discrete Mathematics II - Lecture 5

Themen:

• Algorithmus von Kruskal 
• Sehnen und Fundamentalkreise
• Flussnetze
• Flüsse und Schnitte

Computability & Complexity - Lecture 3

Topics:

Closure properties of the class of primitive recursive functions:

• definition by cases
• bounded sum and product
• bounded minimization
• iteration.

Primitive recursive sets:

• characteristic function
• bounded existential and universal quantification.

Discrete Mathematics II - Lecture 4

Heutige Themen:

• Netzwerke
• Floyd-Warshall
• Dijkstra
• minimale Spannbäume
• Satz von Cayley.

Discrete Mathematics II - Lecture 3

Themen:

• Kriterien für die Planarität von Graphen
• Satz von Kuratowski
• Adjazenz- und Inzidenzmatrizen, Adjazenzlisten
• Tiefen- und Breitensuche.

Computability & Complexity - Lecture 2

Topics:.

• Peano schemes
• Fundamental lemma
• Primitive recursion
• Class of primitive recursive functions
• Each primitive recursive function is URM computable
• Closure properties: transformation of variables and parametrization.

Discrete Mathematics II - Lecture 2

Heutige Themen:

• Zusammenhangskomponenten
• Graph-Metrik
• Bäume
• Spannbäume
• bipartite Graphen
• planare Graphen
• Eulersche Polyederformel

Computability and Complexity - Lecture I

The first lecture held on Friday provided an introduction to register machines (URMs):

• states and state transformations
• syntax of URM programs
• semantics of URM programs.

Computability and Complexity

Preface 

Why do we need a formalization of the notion of algorithm or effective computation? In order to show that a specific problem is algorithmically solvable, it is sufficient to provide an algorithm that solves it in a sufficiently precise manner. However, in order to prove that a problem is in principle not solvable by an algorithm, a rigorous formalism is necessary that allows mathematical proofs. The need for such a formalism became apparent in the work of David Hilbert (1900) about the foundations of mathematics and Kurt Gödel (1931) about the incompleteness of elementary arithmetic.

The first investigations in the field were conducted by the logicians Alonzo Church, Stephen Kleene, Emil Post, and Alan Turing in the early 1930s. They provided the foundation of computability theory as a branch of theoretical computer science. The fundamental results established Turing computability as the correct formalization of the informal idea of effective calculation. The results led to Church’s thesis stating that ”everything computable is computable by a Turing machine”. The theory of computability has grown rapidly from its beginning. Its questions and methods are penetrating many other mathematical disciplines. Today, computability theory provides an important theoretical background for logicians and computer scientists.

Many mathematical problems are known to be undecidable such as the word problem for groups, the halting problem, and Hilbert’s tenth problem.

Contents - Computability:

• Register Machine
• Primitive Recursive Functions
• Partial Recursive Functions
• Ackermann's Function
• Acceptable Programming Systems
• Turing Machine
• Undecidability
• Word Problems

Discrete Mathematics II - Lecture 1

The first lecture held on Wednesday covered the following topics:

• basic definitions (graph, diagram, degree, degree sequence)
• hand-shaking lemma
• graph isomorphism
• subgraphs
• paths and cycles.

Discrete Mathematics II

The lecture takes place on Wednesday, 10:30 - 12:00 am, in building K - DE 15, room 0506, and will cover four topics:

• graph theory
• algorithmic graph theory
• combinatorial optimization
• linear optimization.

Discrete Mathematics - Repetitorium

For more information, please check http://www.tu-harburg.de/ti6/aktuell.html

Seminar: DNA Computing

This seminar will not take place in the summer term 2011 due to other obligations.

Bioinformatics - Exam

1. Consider the following proteins from UniProtKB:

 P04655
 P04654
 P47710
 P08949
 P47851

a) Determine the families to which these proteins belong by using an appropriate tool.
Describe the consensus patterns of these families.

b) For each detected family, construct a multiple sequence alignment for the proteins belonging to the family. Find highly conserved regions in the proteins under consideration by examining the multiple sequence alignments. Are the consensus patterns of the families correctly reflected in the alignments?

c) Use a corresponding tool to provide a phylogenetic tree for the five proteins.
Does the tree reflect the family relationship correctly?

2. Consider the fibrinogen-binding protein from Staphylococcus aureus (accession P68799). Determine the secondary structure by a method of your choice.  Compare the predicted secondary structure for the given protein with the real one.

3. Basic Questions:
a) Explain the difference between standard Monte Carlo method and importance sampling.

b) How many genes has the HI virus?
 Which genes are not present in the human genome?

c) Given a phylogenetic tree with character data at the leaves:

            /\
           /  \
          /\  /\
        GCCA

Find the most parsimonious tree using Fitch's method.

d) What is an additive tree?

Discrete Mathematics - Lecture 14

Topics of the day:

• Anwendung: Konstruktion endlicher Körper (siehe letzte Vorlesung).
• Nullstellen und Einsetzungshomomorphismus.
• Eulersche Phi-Funktion.
• Satz von Euler und Kleiner Fermatscher Satz.
• Potenzieren in Restklassenringen.
• Anwendung: RSA-Algorithmus.

Discrete Mathematics I - Lecture 13

Heutige Themen:

• Einheiten in kommutativen Ringen,
• Fundamentalsatz der Arithmetik,
• Lineare Gleichungen in Restklassenringen (Z mod n und Q[x] mod f),
• Berechnung von Inversen
• Nullteiler in kommutativen Ringen,
• Integritätsbereiche und Körper

Computational Biology - Lecture 13

Today, the following topics were on the roster:

• Closure theorem,
• parametric representation,
• implicitization theorem,
• model invariants for algebraic statistical models.

Introduction to Bioinformatics - Lecture 13

Today, statistical sampling methods were considered. Here are the topics:

• Statistical mechanics,
• canonical and micro-canonical ensemble,
• observables and partition function,
• molecular dynamics simulations (verlet and velocity verlet algorithm),
• consideration of time step,
• improvement of simulation (cutoff, distance, and multipole schemes),
• standard Monte Carlo method,
• calculation of partition function,
• importance sampling,
• sampling of protein structures.

Discrete Mathematics I - Lecture 12

Heutige Themen:

• Hauptsatz der Arithmetik,
• Restklassenringe modulo Z bzw. Q[x].

Computational Biology - Lecture 12

Yesterday, we resumed with the introduction into algebraic geometry:

• ideal-variety correspondence,
• elimination theorem,
• extension theorem.

Introduction to Bioinformatics - Lecture 12

Today, we will give an introduction to 3D structure prediction of proteins:

• Force fields (CHARMM, Oobatake-Crippen),
• rigid geometry models,
• buildup method,
• basic heuristic methods,
• conformational space annealing,
• HP model.

Discrete Mathematics I - Lecture 11

Kurze Einführung in die Teilbarkeitslehre (Ring der ganzen Zahlen, Polynomring):

• Division mit Rest
• ggT und kgV
• Euklidischer Algorithmus
• Satz von Bezout, erweiterter Euklidischer Algorithmus.

In der Vorlesung gab es Fragen nach der Definition des ggT, d.h., gemeinsamer Teiler und größter unter allen gemeinsamen Teilern. Mathematisch handelt es sich um das Infimum der beteiligten Zahlen. Die gemeinsamen Teiler bilden die unteren Schranken und das Infimum ist die größte untere Schranke. Für das kgV gilt die duale Aussage.

Computational Biology - Lecture 11

Today, we will give an introduction to affine algebraic sets:

• Hilbert's Nullstellensatz (weak and strong version),
• correspondence between affine algebraic sets and ideals.

Introduction to Bioinformatics - Lecture 11

Today, we finished the considerations about 2D structure prediction:

• Nearest neighbor classification (intrinsic dimension, Bhattacharyya distance).
• Consensus prediction
• Neural network classification (Rost-Sander approach).

Exams in the Winter Term

Written exams:

• Bioinformatics, Feb. 8, 2011.
• Discrete Mathematics I and II, March 21, 2011.

Oral exams do not follow a fixed schedule, day and time can be negotiated on a case-by-case basis.

Discrete Mathematics I - Lecture 10

In der heutigen Vorlesung wurden folgende Themen behandelt:

• Aufbau der ganzen Zahlen 
• Definition von Ringen und ihre Grundeigenschaften
• Polynomringe
• Binomialsatz

Computational Biology - Lecture 10

Today, we will finish the topic on Groebner bases:

• Minimal Groebner bases,
• Reduced Groebner bases,
• Buchberger's S-criterion,
• Buchberger's algorithm.

Introduction to Bioinformatics - Lecture 10

Today, an introduction to the prediction of secondary protein structures was given:

• GOR method,
• Chow-Fasman method,
• Generation of sample sets,
• Nearest neighbor classification.

Reed-Muller Codes - Revisited

Recently, we published the article:

• From Ideals in Polynomial Rings to Linear Codes Using Groebner Bases, Int. J. Pure Applied Math., vol. 65, no. 1, pp. 41-53, 2010.

This paper studies linear codes as ideals in the group algebra over an elementary abelian p-group. These codes are described in terms of Groebner bases and corresponding encoding and decoding procedures are given. It is shown that the class of codes studied contains an interesting family of linear codes. These codes have a designed Hamming distance and turn out to be superior to the primitive Reed-Muller codes in the non-binary case.

The Reluctant Mr. Darwin

The other day, I read the book The Reluctant Mr. Darwin from David Quammen, 2006. The book provides insight into the course of Charles Darwin's life from his return from the voyage on the Beagle until his death. Darwin spent years to catalogue the vast collection of specimens he brought back. He was a self-taught scientist and eventually came to a theory of evolution. He was reluctant to publish but first choose to share his ideas with colleagues. He was afraid of a public backlash and sometimes diverted his attention and energies elsewhere. In the meantime, another scientist, Alfred R. Wallace, independently came to the same ideas about evolution. Then Darwin's colleagues eventually convinced him to publish his theory. His book, The Origin of the Species, found both, acclaim and dislike.

German translation:

• David Quammen: Charles Darwin - Der große Forscher und seine Theorie der Evolution, Piper Verlag, 2010, 9,95 €.

Happy New Year!