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.