informatik-vortraege

Download

informatik-vortraege@lists.rwth-aachen.de

August 2022

2 participants
2 discussions

Einladung: Informatik-Oberseminar Janosch Fuchs
by fuchs 12 Aug '22

12 Aug '22

+********************************************************************** * * * Einladung * * * * Informatik-Oberseminar * * * +********************************************************************** Zeit: Freitag, 26. August 2022, 13.00 Uhr Der öffentliche Vortrag findet hybrid statt: Ort: Raum 9222, Ahornstr. 55 Zoom: https://rwth.zoom.us/j/92249056004?pwd=cHkwRW1lNTlmS1RXQW95Wmw1MjhFQT09 Referent: Janosch Fuchs M.Sc. Lehrstuhl Informatik 1 Thema: Graph Exploration with Advice (and Online Crossing Minimization) Abstract: Online problems reveal their input instance piece by piece and require an irrevocable decision each time a new piece is revealed. This scenario models critical applications where a decision, once it is made, cannot be changed afterwards and also influences future decisions. Like for classical offline problems, it is common to make a worst-case analysis to give a guarantee on the performance of an online algorithm. A worst-case analysis is achieved by assuming that a malicious adversary, knowing the behavior of the online algorithm, creates the input. Due to the nature of uncertainty online algorithms rarely compute an optimal solution. Thus, their performance is measured in terms of the competitive ratio, which compares the solution computed by the online algorithm to the optimal solution achievable when the whole instance is known beforehand. To measure the impact of the missing knowledge about the future the classical online setting was extended with a helpful oracle providing information about the future input. The online algorithm receives the information by accessing a tape containing a binary bit string. The number of bits that the algorithm reads during its computation is called its advice complexity. Bounds on the advice complexity of an online algorithm that optimally solves an online problem show how much information about the future is needed to avoid any mistake. An obvious upper bound for the advice complexity of all online problems is the size of the binary encoding of the input instance or the optimal solution. But most of the time it is possible to derive better bounds by encoding only critical decisions which then reveals the core difficulty of an online problem. Thus, the advice complexity strongly correlates to the difficulty of an online problem and it can be used to measure the difficulty of different online problems. In the main part, we analyze the advice complexity of the graph exploration problem. Here, an algorithm has to move an agent through a graph from vertex to vertex using the edges such that the agent traverses the cheapest or shortest tour that visits every vertex at least once. The algorithm does not know the graph beforehand and each time the agent is located at a new vertex the reachable neighborhood is revealed together with the cost to reach them from the current location. Already seen or visited vertices are recognizable. Due to the already known tight upper bound of n\log(n) for the advice complexity of the graph exploration problem on dense graphs, we focus on sparse graphs. We show that a linear amount of advice is sufficient and also necessary to solve the graph exploration problem on directed and undirected graphs. Es laden ein: die Dozentinnen und Dozenten der Informatik

1 0

Einladung: Informatik-Oberseminar Herr Zhijian Li
by Leany Maaßen 03 Aug '22

03 Aug '22

+********************************************************************** * * * Einladung * * * * Informatik-Oberseminar * * * +********************************************************************** Zeit: Mittwoch, 10.08.2022, 14:00-15:00 Uhr Ort: Raum 5053.2 (großer B-IT-Raum)/Informatikzentrum, Ahornstraße 55 Referent: Herr Zhijian Li , M.Sc. Institute for Computational Genomics Thema: Computational Method for Single-cell ATAC-seq Imputation and Dimensionality Reduction Abstract: Single-cell sequencing assay for transposase-accessible chromatin (scATAC-seq) allows mapping of regulatory variation of thousands of cells at the single-cell resolution. However, analyzing the scATAC-seq data is computationally challenging due to the sparsity, high dimensionality, and the nature of the binary signal. In this thesis, we proposed scOpen, a computational approach for quantification of single-cell open chromatin status and reduction of the dimensionality based on the non-negative matrix factorization (NMF) topic modeling. We demonstrated that scOpen can improve several crucial downstream analysis steps of scATAC-seq, such as clustering, visualization, cis-regulatory DNA interactions, and delineation of regulatory features. We also applied scOpen to investigate the regulatory programs that drive the development of chronic kidney disease (CKD). Altogether, these results demonstrate that scOpen is a useful computational approach in single-cell open chromatin data analysis. Es laden ein: die Dozentinnen und Dozenten der Informatik _______________________________ Leany Maaßen RWTH Aachen University Lehrstuhl Informatik 5, LuFG Informatik 5 Prof. Dr. Stefan Decker, Prof. Dr. Matthias Jarke, Prof. Gerhard Lakemeyer Ph.D. Ahornstrasse 55 D-52074 Aachen Tel: 0241-80-21509 Fax: 0241-80-22321 E-Mail: maassen(a)dbis.rwth-aachen.de

1 0