Department of Theoretical Computer Science

Projects

Advanced Methods of Data Processing and Information Mining

Period
2015
Description
The project focuses on perspective and ever-expanding field of data processing and extraction of information of valuable content from the data. The methods for information extraction are increasingly using selected methods of artificial intelligence such as neural networks and evolutionary algorithms. Combined models or algorithms for text processing (text mining) come to the fore. The need of these topics is evident from the fact that each year, the volume of data is doubling. At the same time, only 20 % of the available data are processed.

Algorithms and Game Comonads

Program
Horizon Europe
Provider
European Commission
Code
101111373
Period
2024 - 2026
Description
The emerging theory of game comonads establishes a fruitful interplay between category theory, mathematical logic, and algorithms. This theory has shown its power when obtaining new Lovasz-type theorems, preservation theorems and decomposition theorems in finite model theory. In our recent work we show that the theory of game comonads can be leveraged to obtain the two traditional Courcelle theorems, stating FPT decidability of monadic second order logic on classes of bounded tree-width and clique-width. This result is only a first step in concrete algorithmic applications of the theory. The abstract setting of game comonads is a good candidate for a systematic treatment of algorithmic problems. The first objective of the project is to formulate a general theory of FPT decidability in terms of game comonads. To start with, we describe some of the important model-theoretic algorithms.

Algorithms for Next-Generation Sequencers

Program
Studentská grantová soutěž ČVUT
Code
SGS11/082/OHK3/1T/18
Period
2011
Description
Sequencing technology has come a long way since the time when traditional sequencing techniques required many labs around the world to cooperate for over a decade, in order to sequence the human genome for the first time. Nowadays, with the advent of next-generation sequencing (NGS) technologies, sequencing has been reduced to a matter of days or hours, and the cost has decreased by many orders of magnitude, making it an accessible experimental procedure to many laboratories. The data resulting from a single sequencing experiment can be quite large and it is not uncommon to have data from multiple experiments. This trend of increasing availability of sequencing will continue as projects even more ambitious than the 1000 Genomes Project start to materialize. This can be achieved only if computer scientists are designing new efficient algorithms for assembling millions of short sequences (reads), and for mapping a new set of reads to an existing genome sequence. The need for more efficie

Algorithms for Processing Tree Data Structures and Data Compression

Program
Studentská grantová soutěž ČVUT
Code
SGS15/116/OHK3/1T/18
Period
2015
Description
With the vast amount of data needed to be archived, indexed and procesed, special data structures are required. The tree is a typical data structure which is used very often for hierarchically storing data. Specialized algorithms are needed for indexing tree data structures and also accessing, extracting and analyzing data stored in them. Another goal of this project is a design and implementation of novel methods of data compression and indexing in two areas: DNA sequence compression using dictionary methods and approximate pattern matching in genomes.

Algorithms for Processing Tree Structures and Data Compression

Program
Studentská grantová soutěž ČVUT
Code
SGS14/101/OHK3/1T/18
Period
2014
Description
With the vast amount of data needed to be archived, indexed and procesed, special data structures are required. The tree is a typical data structure which is used very often for hierarchically storing data. Specialized algorithms are needed for indexing tree data structures and also accessing, extracting and analyzing data stored in them. The aim of this research is to design efficient yet simple to understand algorithms dealing with tree pattern matching (both exact and approximate) and tree indexing, and provide a toolkit implementation. Another goal of this project is a design and implementation of novel methods of data compression in two areas: DNA sequence compression and difference compression of files.

All-Purpose Model of Database Web Pages for Faculty of Architecture, CTU

Program
IGS ČVUT
Code
300113938
Period
2001
Description
CTU300113938

Alogirthms for Processing Tree Data Structures, Implementing Programming Languges and Data Compression

Program
Studentská grantová soutěž ČVUT
Code
SGS17/209/OHK3/3T/18
Period
2017 - 2019
Description
With the vast amount of data needed to be archived, indexed and procesed, efficient data structures and algorithms are required. The tree is a typical data structure which is used very often for hierarchically storing data. Another goal of this project is to design and implement novel methods for data indexing combined with data compression and methods for various approximate pattern matching over the indexes. The indexes and pattern matching find applications in searching in DNA and RNA sequences. Another topic of our research is the area of algorithms for implementing dynamic programming languages.

Anonymizing of User Data: A Parameterized Perspective

Program
Projects of the Ministry of Education, Youth and Sports not included in the CEP
Provider
Ministry of Education, Youth and Sports
Period
2022
Description
When collecting user data nowadays we care about these being sufficiently anonymous, that is, we usually replace the real data with some perturbed data so that we protect the sole identity of the end-user. This is a challenging task both from computational and algorithmical (theoretic) approach. Therefore we often have to employ advanced methods of analysis and algorithmic techniques to identify tractable cases. We will identify new paramaters that attain low values in realworld data and analyze if these result in fixed-parameter tractable case or to parameterized hardness.

Applications of Methods of Knowledge Engineering in Data Mining

Program
Standard projects
Provider
Czech Science Foundation
Code
GA201/08/0802
Period
2008 - 2012

Complex security solution focused on detection and prevention of cyber frauds in the financial services domain

Program
Programme of applied research and experimental development EPSILON
Provider
Technology Agency of the Czech Republic
Code
TH01010737
Period
2015 - 2016
Description
Cílem projektu v rámci podprogram 1 - Znalostní ekonomika - je vývoj uceleného softwarového řešení v oblasti odhalování a předcházení frauduletnímu jednání ve finančním sektoru s využitím nejnovějších poznatků v oblasti datového a prediktivního modelování, analýzy komplexních grafových struktur a dynamických systémů a vytěžování znalostí z online datových zdrojů. Na řešení projektu se podílejí vynikající odborníci v oblasti modelování a algoritmizace z FIT ČVUT, společně s experty ze společnosti Profinit s mnohaletými zkušenostmi v oblasti softwarového vývoje pro finanční sektor.

Computing and Approximating Equilibria in Games With Complex Strategy Spaces

Program
Standard projects
Provider
Czech Science Foundation
Code
GA24-12046S
Period
2024 - 2026
Description
While there is an increasing number of practical applications of game theory, there are still severe computational limitations of the current models and algorithms used to find approximate optimal strategies. One such limitation is the high computational complexity of finding an equilibrium for games with large or even infinite sets of actions. Moreover, the strategy space in applications have often a complex inner structure making the equilibrium computations even more difficult. We propose advancing the state-of-the-art in the theoretical understanding of the structure of equilibria in games with complex strategy spaces, developing novel iterative strategy-generating algorithms for finding approximate solutions, investigating the computational complexity of equilibrium problem for special classes of games, and applying these fundamental results to various card games.

Constructing Advanced Comprehensible Classifiers

Program
Standard projects
Provider
Czech Science Foundation
Code
GA13-17187S
Period
2013 - 2015

Data-mining of non-structured data

Period
2016
Description
The project is focused on data mining of non-structured data from large-scale sources. The data are represented by textual and image/video information. To porcess the data, selected methods of artificial intelligence such as neural networks/deep learning, evolutionary algorithms and methods of image processing will be used. The need of these topics is evident from the fact that each year, the volume of data is doubling. At the same time, only 20 % of the available data are processed.

Detection of diseased cattle

Program
Projekty podpořené z ČR (pracovní kód k dodatečnému upřesnění)
Provider
Another domestic provider
Period
2018
Description
Research and development of the disease detection system for cattle.

Development and testing of algorithms for predictive behavioral analysis of persons crossing the EU's external borders

Program
Program bezpečnostního výzkumu pro potřeby státu 2016 - 2021 (BV III/2 ? VZ)
Provider
Ministry of Interior
Code
VH20182019034
Period
2018 - 2019
Description
In order to achieve the objectives of the project, ie the establishment of a system for the early detection of persons crossing the external borders of the EU and the Czech Republic, it is necessary first to prepare available data in a format suitable for the use of data mining methods. Already preparing data and extracting interesting symptoms will be an iterative process because after getting feedback from the customer, the symptoms can be further improved. The data will be processed by several approaches that are appropriate to address this type of problem. The data mining method can be divided into several groups according to the use method, anomaly detection methods in the data, predictive models for revealing repeating patterns, clustering methods for searching similar persons and flights, and other methods that can be beneficial. Due to the nature of the problem, a relatively extensive prototyping and research phase will be necessary before the implementation phase of the production version of the selected algorithms will work. A prerequisite for successful algorithm tuning is the relatively intense synergy of the assignor, whether in terms of feedback to partial results or annotation of data. The research team will use state-of-the-art methods to minimize work on the part of the sponsor - such as semi-supervised or active learning models.

Efficient String Matching for Bioinformatics

Program
Standard projects
Provider
Czech Science Foundation
Code
GA19-20759S
Period
2019 - 2020
Description
Index is a way to rapidly increase the speed of searching in data given in advance. The constructed index then allows search time proportional to the pattern size and the number of its occurrences. The aim of the project is to develop new algorithms and data structures for areas managing large data collections (DNA/RNA sequences) supporting not only exact pattern matching but also more complex tasks like degenerate or elastic pattern matching. There are many advanced techniques for indexing strings combining both data compression and stringology. However, there are still challenging new tasks for special cases like indexing highly similar texts where general purpose indexing methods are not efficient. This is for instance the case of genomes of the same species. Some on-line methods for elastic pattern matching will also be developed.

Evolving Language Ecosystems

Program
Horizon 2020
Provider
European Commission
Code
695412
Period
2016 - 2022
Description
The Evolving Language Ecosystems project explores the fundamental techniques and algorithms for evolving programming languages and their ecosystems. Our purpose is to reduce the cost of wide-ranging language changes and obviate the need for devising entirely new languages. Our findings will grant both researchers and practitioners a greater degree of freedom when experimenting with new ideas on how to express computation.

FIT - Fioravantes, Foivos

Period
2022 - 2024
Description
Fixed-parameter tractability and approximation algorithms are nowadays standard tools for design of algorithms for hard problems in the area of Computational Social Choice. Surprisingly, kernelization, a prominent technique in FPT algorithmics, is not used as often to tackle social choice problems. Kernelization is a formalism of safe data reduction which we believe does have its place in all research disciplines dealing with large and complex datasets. The most recent approach is the so-called lossy kernelization which on the one hand cooperates with approximation algorithms (unlike kernelization which can only be pipelined with exact algorithms) and on the other hand, allows circumventing hardness results (in exchange for introducing a possible loss in the quality of the solution).

FIT - Melissinos, Nikolaos

Period
2022 - 2024
Description
Parameterized or multivariate analysis became in the last two decades a standard approach for (NP-) hard computational problems. Here, in contrast to classical complexity, the efficiency of algorithms is not measured only with respect to the length of the input instance, but also with respect to a specified parameter. The outcome is a more fine grained complexity landscape which allows for a better prediction of the complexity of particular instances encountered. The goal is to design algorithms with running time that is polynomial in the input size and exponential only in the designated parameter. Fundamentally, the degree of the polynomial is required to be independent of the value of the parameter. Parameterized complexity provides a mathematical framework to analyze these algorithms and also to show that for some problems and parameters there is (probably) no such algorithm.

Fusion-Based Knowledge Discovery in Human Activity Data

Program
Standard projects
Provider
Czech Science Foundation
Code
GA18-18080S
Period
2018 - 2021
Description
One of the key tasks faced by the rapidly developing area of knowledge discovery in multimedia data, especially from video data, is detecting various human activities. The project will have two objectives, both belonging to basic research: On the one hand, it will contribute to further development of methods for the discovery of different kinds of knowledge in video data recording human activities, such as knowledge concerning shape, motion, color, background, scene, person-object interactions, or thermal infrared images making use of the available experimental environment at the Image Processing Laboratory at FIT CTU. On the other hand, it will perform research into different ways of fusion of multiple classification or regression models in such knowledge discovery tasks. In connection with that objective, the project will rely on the previous experience of its team members from research into combining classifiers and aggregating regression models.

Governance support tools for dynamic aspects of Big Data environments

Program
Programme of applied research and experimental development EPSILON
Provider
Technology Agency of the Czech Republic
Code
TH02010287
Period
2017 - 2019
Description
The key trend in management has been to attempt to make all decisions data driven. A critical element in this effort has been the data warehouse or, more broadly, business intelligence (BI). Fast changes are forcing companies to develop faster, and fast development requires effective BI management, so-called data governance (DG). Without solid DG processes and rapid development in place, companies are not able to use their own data successfully. The ongoing big data revolution brings more issues to an already complex field and shows that current DG technologies are not ready for the future. The goal of this project is to create tools which will ensure effective DG in big data environments and thereby protect the billions of dollars invested into BI development worldwide.

InovaFOND

Program
Programme of applied research, experimental development and innovations GAMA
Provider
Technology Agency of the Czech Republic
Code
TG02010033
Period
2016 - 2019
Description
Hlavním cílem projektu je ověřit aplikační potenciál výsledků VaV, za pomoci aktivit proof of concept nalézt konkrétní průmyslově uplatnitelná řešení a připravit jejich následné komerční využití. Stávající podpůrné nástroje ČVUT budou doplněny o nástroj nový – fond, z něhož budou aktivity proof of concept podporovány. Dalším cílem projektu je pak nastartovat a ustálit mechanismus postupného nahrazování projektem poskytnutých prostředků prostředky vlastními, získanými z úspěšně komercializovaných výsledků a fundraisingem, a zajistit tak nejen dlouhodobou udržitelnost systému aktivní podpory uplatnění výsledků s aplikačním potenciálem, ale díky zviditelnění úspěšně komercializovaných řešení pozitivně formovat myšlení zaměstnanců a studentů ČVUT k uplatňování výsledků v praxi.

InovaFOND

Program
Programme of applied research, experimental development and innovations GAMA
Provider
Technology Agency of the Czech Republic
Code
TG02010033
Period
2017 - 2018
Description
Zařízení pro detekci vad transparentních materiálů

International Mobility of Researchers in CTU

Program
Operational Programme – Research, Development and Education – Structural Funds EU
Provider
European Commission
Code
EF16_027/0008465, CZ.02.2.69/0.0/0.0/16_027/0008465
Period
2018 - 2022
Description
Hlavním cílem projektu je realizace mezinárodní mobility výzkumných pracovníků ČVUT se zaměřením na posílení mezinárodní spolupráce a rozvoj lidských zdrojů ve výzkumu. Dalším cílem projektu je podpora profesního růstu výzkumných pracovníků a rozvoj výzkumných organizace ČVUT prostřednictvím posílením lidských zdrojů. Projekt bude realizován pracovními pobyty výzkumných pracovníků v zahraničí v případě výjezdů z ČR nebo pracovními pobyty výzkumných pracovníků v ČR v případě příjezdů do ČR.

Laboratory of Image Processing

Program
Operational Programme – Research, Development and Education – Structural Funds EU
Provider
European Commission
Code
, CZ.02.2.67/0.0/0.0/16_016/0002551
Period
2017 - 2019
Description
Cílem ERDF aktivity je HW dovybavení nově budované laboratoře zpracování obrazu na FIT ČVUT a zabezpečení jejího fungování. Laboratoř bude dovybavena kamerami, měřicími stojany, zdroji osvětlení, objektivy, filtry a nap. zdroji. Aktivita navazuje na ESF aktivitu, která má za cíl vytvoření SW nástrojů pro zpracování obrazu pro práci studentů. Výstupem těchto dvou aktivit bude HW a SW infrastruktura pro realizaci projektů v oblasti zpracování obrazu a videa a podporu související výuky.

Mobility CTU - STA

Program
Operational Programme – Research, Development and Education – Structural Funds EU
Provider
European Commission
Code
EF18_053/0016980, CZ.02.2.69/0.0/0.0/18_053/0016980
Period
2020 - 2023
Description
Projekt je zaměřen na posílení mezinárodní mobility vědeckých, technických a administrativních pracovníků (jak výjezdů, tak příjezdů) na ČVUT. ČVUT patří k největším a nejstarším technickým vysokým školám v Evropě. V současné době má 8 fakult (stavební, strojní, elektrotechnickou, jadernou a fyzikálně inženýrskou, architektury, dopravní, biomedicínského inženýrství, informačních technologií) a 6 ústavů. Vybrané mobility svým zaměřením pokrývají téměř všechny hlavní výzkumné směry žadatele. Cílem projektu je realizace mobilit vědeckých, technických a administrativních pracovníků ČVUT, které přispějí k rozvoji jejich dovedností, kompetencí a získání zkušeností ze zahraničních pracovišť. V rámci 6 klíčových aktivit proběhne dle předpokladu celkem 116 mobilit, které svým zaměřením pokrývají všechny hlavní výzkumné oblasti žadatele. Celková disponibilní alokace byla mezi jednotlivá výzkumná pracoviště rozdělena adekvátně dle velikosti pracovišť a podílů dle RIV tak, aby byl zajištěn rovný přístup a nediskriminace v rámci celé organizace. Rozvoj odbornosti perspektivních pracovníků pomocí stáží na mezinárodních renomovaných pracovištích v oblastech důležitých pro další rozvoj ČVUT je nezbytnou součástí kariérního vývoje vybraných pracovníků, pro vědecké pracovníky pak představuje nedílnou součást jejich profesního a odborného růstu. Součástí všech realizovaných výjezdových mobilit bude také návratová fáze, jejímž cílem je zajištění přenosu zkušeností ze zahraničí a diseminace výsledků mobility. Přilákání zahraničních vědeckých pracovníků umožní také navázání nových kontaktů se špičkovými pracovišti v zahraničí. Mezinárodní mobilita technických a administrativních pracovníků významně přispěje ke sdílení informací o spolupracujících institucích, diseminaci informací o probíhajících výzkumech a rozvíjení vzájemných kontaktů.

Mobility ČVUT MSCA-F-CZ-III

Program
Programme Johannes Amos Comenius
Provider
European Commission
Code
, CZ.02.01.01/00/22_010/0008601
Period
2024 - 2026
Description
V souladu s výzvou projekt umožní mezinárodní mobilitu výzkumným pracovníkům, kterým byl v minulých letech schválen projekt Horizont 2020 z programu Marie Skłodowska-Curie Individual / Postdoctoral Fellowships, jež dosáhl hodnocení alespoň 70 %, ale z důvodů nedostatku financí byl zařazen do kategorie tzv. no-money projektů. Projekt bude realizován pracovními pobyty zahraničních VP na ČVUT. Hlavním cílem projektu je podpora profesního růstu výzkumných pracovníků, kvalitního výzkumu, vzdělávání pro praxi a rozvoje komunikace a spolupráce. Na FIT se jedná o příjezdovou mobilitu na 24 měsíců výzkumného pracovníka, Foivos Fioravantes Ph.D., z Francie. Školitel je doc. Ing. Dušan Knop, Ph.D.

Modern data-mining methods for advanced extraction of information from data

Program
Studentská grantová soutěž ČVUT
Code
SGS17/210/OHK3/3T/18
Period
2017 - 2019
Description
The project focuses on perspective and ever-expanding field of data processing and extraction of information of valuable content from the data. The methods for information extraction are increasingly using selected methods of artificial intelligence such as neural networks and evolutionary algorithms. Combined models or algorithms for text processing (text mining) come to the fore. The need of these topics is evident from the fact that each year, the volume of data is doubling. At the same time, only 20 % of the available data are processed.

Natural Language and Formal Language Data Compression

Program
Studentská grantová soutěž ČVUT
Code
SGS10/306/OHK3/3T/18
Period
2010 - 2012
Description
The main goal of this project is design and implementation of novel methods of data compression. The contextual data compression methods are a part of lossless data compression methods. Lossless means that the compression process is fully reversible and decompressed data is identical to the original data. These methods are based on similarities in the input data. The main sight of nowadays research is aimed to word-based contextual data compression and preprocessing transformations. Word-based text compression is more adaptive to the input data. This approach takes advantage of the strictly defined structures of formal languages and natural languages and achieves better compression ratio than equivalent character-based data compression methods. The goal of this project is to use introduced possibilities to design new natural language compression methods with compression ratio comparable or better than the compression ratio of the best nowadays methods of data compression. This proje

New directions in blending evolutionary techniques with data mining

Program
Studentská grantová soutěž ČVUT
Code
SGS13/098/OHK3/1T/18
Period
2013
Description
This project is targeted to basic research in areas emerging by novel approaches to application of evolutionary techniques in data mining

New Frontiers in Computational Social Choice

Program
Standard projects
Provider
Czech Science Foundation
Code
GA22-19557S
Period
2022 - 2024
Description
Fixed-parameter tractability and approximation algorithms are nowadays standard tools for design of algorithms for hard problems in the area of Computational Social Choice. Surprisingly, kernelization, a prominent technique in FPT algorithmics, is not used as often to tackle social choice problems. Kernelization is a formalism of safe data reduction which we believe does have its place in all research disciplines dealing with large and complex datasets. The most recent approach is the so-called lossy kernelization which on the one hand cooperates with approximation algorithms (unlike kernelization which can only be pipelined with exact algorithms) and on the other hand, allows circumventing hardness results (in exchange for introducing a possible loss in the quality of the solution). This project aims on filling this gap of usage of these tools in computational social choice. The suggested line of research continues our current studies in this area and the new proposed directions will need novel algorithmic approaches as they focus on the boundaries of traceability. We have identified several interesting questions where there is potential to apply the above. Our aim is to significantly deepen our understanding of these computationally hard problems by providing polynomial-sized (lossy) kernels or showing that the problems are resistant to this line of attack.

New Frontiers in Computational Social Choice

Program
Projekty podpořené z ČR (pracovní kód k dodatečnému upřesnění)
Provider
Another domestic provider
Period
2022
Description
New Frontiers in Computational Social Choice

New methods and tools for knowledge discovery in databases

Program
Standard projects
Provider
Czech Science Foundation
Code
GA201/05/0325
Period
2005 - 2007
Description
The project objective is to develop new methods and tools for KDD (Knowledge Discovery in Databases). The project is focused on the whole KDD process, from business and data understanding down to presentation of the results. That requires involvement of several branches of informatics, mathematics and integration with other knowledge technologies. This integration is understood in two ways. The first is related to utilization of the KDD results in applications of other knowledge technologies, the other is related to utilization of knowledge technologies to intensify the KDD process. The project follows up the applicant''s and co-applicants'' long-term activities. Related to these activities are internationally acclaimed results, experience with European and national grants, experience from both practical applications and teaching. The methods and tools being developed follow the line of reached results in the area of support of various phases of the KDD process. The project results shall be implemented

New Methods of Preprocessing and Data Mining

Period
2014
Description
The project focuses on perspective and ever-expanding field of data pre-processing and extraction of information of valuable content from the data. The methods for information extraction are increasingly using selected methods of artificial intelligence such as neural networks and evolutionary algorithms. Combined models or algorithms for text processing (text mining) come to the fore. The need of these topics is evident from the fact that each year, the volume of data is doubling. At the same time, only 20 % of the available data are processed.

Novel Model Ensembling Algorithms

Program
Studentská grantová soutěž ČVUT
Code
SGS10/307/OHK3/3T/18
Period
2010 - 2012
Description
Cornerstone of successful data mining is to choose a suitable modelling algorithm for given data. Recent results show, the best performance can be achieved by an efficient combination of diverse models or classifiers. In this project, we develop new algorithms for ensembling models or classifiers. Within our experimental platform FAKE GAME, we can compare new algorithms to already implemented state-of-the-art solutions in the field.

Online experimental enviroment for testing adaptive algorithms for control SW agents

Program
Studentská grantová soutěž ČVUT
Code
SGS11/083/OHK3/1T/18
Period
2011
Description
Software agents technology has been the focus of research and development in recent years. Agents can do partial tasks, but for practical use, it is necessary to control their cooperation efficiently. Adaptive algorithms (e.g. evolution algorithms or neural networks) seem to be a promising approach for cooperation control. A suitable software environment is needed for experiments with control algorithms which can be difficult to configure and run. This project will try to adress and simplify this problem from the perspective of a software agents developer.

Optimization of hybrid neural networks

Program
Studentská grantová soutěž ČVUT
Code
SGS11/081/OHK3/1T/18
Period
2011
Description
Existuje mnoho algoritmů na optimalizaci dopředných neuronových sítí, většina z nich je však určena pro sítě s jedním typem neuronů. Náš výzkum ukázal, že neuronová síť s různými typy neuronů je universálnější a mnohdy přesnější. V tomto projektu se snažíme vytvořit efektivnější algoritmy pro učení takových druhů neuronových sítí.

Parameterized Algorithms for Fundamental Network Problems Related to Connectivity

Program
Post-graduate (doctorate) grants
Provider
Czech Science Foundation
Code
GP14-13017P
Period
2014 - 2016
Description
Parameterized algorithmics became in the last two decades a standard tool to solve computationally hard (NP-hard) problems. The running time here is expressed in terms of a secondary measure (the parameter) additionally to the input size, which provides a more refined analysis of where the hardness of the problem comes from. Parameterized complexity provides a mathematical framework to analyze these algorithms and also to show that for some problems and parameters there is (probably) no such algorithm. In this research proposal we plan to study several open questions related to fundamental problems in the field of network design within the framework of parameterized complexity. More precisely, we will focus on the following two areas: Steiner-type problems in graphs; Network Measurement, Navigation, and Resource Placement. We plan to provide a systematic multivariate complexity analysis, which we feel is missing in the area.

POSTER 2014

Program
Studentská vědecká konference ČVUT
Code
SVK 20/14/F3
Period
2014
Description
Studentská vědecká konference POSTER 2014 bude již osmmnáctým ročníkem konference, která si jako svá témata vybrala kompletní průřez elektrotechnikou a informatikou rozšířený o související problematiku přírodních věd, biomedicínského inženýrství a historie vědy a techniky. Cílem konference je vytvořit fórum pro publikace doktorandů a magisterských studentů, na němž mohou získat první zkušenosti s vytvořením a obhajobou svých příspěvků. Anglický jazyk je jazykem jednacím. Konference je otevřená zahraničním účastníkům, kterých bývý pravidelně přes dvacet procent, takže stimuluje zkušenosti doktorandů s publikací na mezinárodním fóru. Na závěr konference jsou vyhodnocovány nejlepší prezentace v jednotlivých sekcích, čímž se daří využít přirozené soutěživosti mladých ke zlepšení kvality jejich písemných projevů i obhajoby posterů před návštěvníky, kterými jsou i členové hodnotících (programových) výborů. Konference se běžně účastní doktorandi FEL, FBMI a FIT. Těmito fakultami byla také spolupořádána v loňském roce a de facto bude takto pořádána i letos, i když to aplikace pro podání přihlášek nepodporuje. Seznam sekcí, informaci o programovém výboru a další informace lze získat na www stránce konference.

POSTER 2015

Program
Studentská vědecká konference ČVUT
Code
SVK 28/15/F3
Period
2015
Description
Studentská vědecká konference POSTER 2015 bude již devatenáctým ročníkem konference, která si jako svá témata vybrala kompletní průřez elektrotechnikou a informatikou rozšířený o související problematiku přírodních věd, biomedicínského inženýrství a historie vědy a techniky. Cílem konference je vytvořit fórum pro publikace doktorandů a magisterských studentů, na němž mohou získat první zkušenosti s vytvořením a obhajobou svých příspěvků. Anglický jazyk je jazykem jednacím. Konference je otevřená zahraničním účastníkům, kterých bývá pravidelně přes dvacet procent, takže stimuluje zkušenosti doktorandů s publikací na mezinárodním fóru. Na závěr konference jsou vyhodnocovány nejlepší prezentace v jednotlivých sekcích, čímž se daří využít přirozené soutěživosti mladých ke zlepšení kvality jejich písemných projevů i obhajoby posterů před návštěvníky, kterými jsou i členové hodnotících (programových) výborů. Konference se běžně účastní doktorandi FEL, FBMI a FIT. Těmito fakultami byla také spolupořádána v předcházejících letech a de facto bude takto pořádána i letos (i když to aplikace pro podání přihlášek nepodporuje). Seznam sekcí, informaci o programovém výboru a další informace lze získat na www stránce konference.

POSTER 2016

Program
Studentská vědecká konference ČVUT
Code
SVK 23/16/F3
Period
2016
Description
Studentská vědecká konference POSTER 2016 bude jubilejním dvacátým ročníkem konference, která si jako svá témata vybrala kompletní průřez elektrotechnikou a informatikou rozšířený o související problematiku přírodních věd, biomedicínského inženýrství a historie vědy a techniky. Cílem konference je vytvořit fórum pro publikace doktorandů a magisterských studentů, na němž mohou získat první zkušenosti s vytvořením a obhajobou svých příspěvků. Anglický jazyk je jazykem jednacím. Konference je otevřená zahraničním účastníkům, kterých bývá pravidelně přes dvacet procent, takže stimuluje zkušenosti doktorandů s publikací na mezinárodním fóru. Na závěr konference jsou vyhodnocovány nejlepší prezentace v jednotlivých sekcích, čímž se daří využít přirozené soutěživosti mladých ke zlepšení kvality jejich písemných projevů i obhajoby posterů před návštěvníky, kterými jsou i členové hodnotících (programových) výborů. Konference se běžně účastní doktorandi FEL, FBMI a FIT. Těmito fakultami byla také spolupořádána v předcházejících letech a de facto bude takto pořádána i letos (i když to aplikace pro podání přihlášek nepodporuje). Seznam sekcí, informaci o programovém výboru a další informace lze získat na www stránce konference.

POSTER 2017

Program
Studentská vědecká konference ČVUT
Code
SVK 21/17/F3
Period
2017
Description
Studentská vědecká konference POSTER 2017 je jednadvacátým ročníkem konference, která si jako svá témata vybrala kompletní průřez elektrotechnikou a informatikou rozšířený o související problematiku přírodních věd, biomedicínského inženýrství a historie vědy a techniky. Cílem konference je vytvořit fórum pro publikace doktorandů a magisterských studentů, na němž mohou získat první zkušenosti s vytvořením a obhajobou svých příspěvků. Anglický jazyk je jazykem jednacím. Konference je otevřená zahraničním účastníkům, kterých bývá pravidelně přes dvacet procent, takže stimuluje zkušenosti doktorandů s publikací na mezinárodním fóru. Na závěr konference jsou vyhodnocovány nejlepší prezentace v jednotlivých sekcích, čímž se daří využít přirozené soutěživosti mladých ke zlepšení kvality jejich písemných projevů i obhajoby posterů před návštěvníky, kterými jsou i členové hodnotících (programových) výborů. Konference se běžně účastní doktorandi FEL, FBMI a FIT. Těmito fakultami byla také spolupořádána v předcházejících letech a de facto bude takto pořádána i letos (i když to aplikace pro podání přihlášek nepodporuje). Seznam sekcí, informaci o programovém výboru a další informace lze získat na www stránce konference.

Processing Tree Data Structures and Data Compression

Program
Studentská grantová soutěž ČVUT
Code
SGS16/118/OHK3/1T/18
Period
2016
Description
With the vast amount of data needed to be archived, indexed and procesed, efficient data structures and algorithms are required. The tree is a typical data structure which is used very often for hierarchically storing data. Another goal of this project is to design and implement novel methods for data indexing combined with data compression and methods for various approximate pattern matching over the indexes. The indexes and pattern matching find applications in searching in DNA and RNA sequences.

Processing Tree Structures and Data Compression

Program
Studentská grantová soutěž ČVUT
Code
SGS13/097/OHK3/1T/18
Period
2013
Description
With the vast amount of data needed to be archived, indexed and procesed, special data structures are required. The tree is a typical data structure which is used very often for hierarchically storing data. Specialized algorithms are needed for indexing tree data structures and also accessing, extracting and analyzing data stored in them. The aim of this research is to design efficient yet simple to understand algorithms dealing with tree pattern matching (both exact and approximate) and tree indexing, and provide a toolkit implementation. Another goal of this project is design and implementation of novel methods of data compression in two areas: first, music score compression; second, natural language compression.

Quantum Informatics

Program
Rozvojové programy MŠMT
Provider
Ministry of Education, Youth and Sports
Code
NPO_ČVUT_16597/2022
Period
2022 - 2024
Description
The project (B) aims to create a new Master's degree programme called „Quantum Informatics“ with a significant share of computer science. It is intended to prepare professionals for the technological and engineering practices associated with the second quantum revolution enabling radically new computational and control procedures and communication with unprecedented security. Graduates will be equipped with a range of engineering skills and will be able to implement quantum practices in advanced technology-oriented workplaces. Two laboratories of quantum communication and cryptography (FEL, FJFI) and quantum computing (FIT, FS, FJFI, FEL) are planned. The teaching laboratories will be available to the faculties as part of their teaching. A quantum computing laboratory will be established at FIT. The project will equip the classroom(s) with purchased quantum optical computer simulators. The faculty will develop quantum computing, in particular focusing on quantum algorithms for parallelization of computation, encryption/encryption, security algorithms, complexity theory, data mining (learning parallel structures - deep learning networks). FEL and FJFI will jointly create a teaching laboratory for quantum cryptography and its subsequent connection to the national cryptographic network. The project should also serve to prepare study fields/programmes at CTU units (FJFI, FIT, FEL, FS). Furthermore, it will be an effort to actively participate in the emerging international consortium for quantum technologies.

Searching in trees

Program
Studentská grantová soutěž ČVUT
Code
SGS10/225/OHK3/2T/18
Period
2010 - 2011
Description
With the vast amount of data needed to be archived, indexed and procesed, special data structures are required. The tree is a typical data structure which is used very often for hierarchically storing data. Specialized algorithms are needed for indexing tree data structures and also accessing, extracting and analyzing data stored in them. Examples of applications can be the optimization of abstract syntax trees in the process of compiling, term-rewriting, mechanical theorem proving, searching in phylogenic trees, indexing the secondary structure of RNA, searching in XML documents and evaluating the source code of functional programming languages. For this purpose we have introduced a new research discipline called Arbology, a generalization of Stringology, that deals with tree structures. We use the pushdown automaton as our computational model since the linear notions of trees, being generated by context-free grammars, are in fact context-free languages. The aim of this research is to

Selected questions of discrete and computational geometry

Program
Grantové projekty excelence v základním výzkumu EXPRO
Provider
Czech Science Foundation
Code
GX23-04949X
Period
2023 - 2027
Description
The project will be focused on several fundamental problems in discrete and computational geometry, and their surrounding (sub)areas.

Software for evaluation of age with use of pelvis in Retrospective Anthropology, Archeology and Forensic Sciences

Program
Programme of applied research and experimental development in social sciences and humanities ETA
Provider
Technology Agency of the Czech Republic
Code
TL03000646
Period
2020 - 2022
Description
The main objective and output of the project is to create user-friendly software for automatic evaluation of the age of adult skeletal remains. SW will allow age estimation based on sophisticated anthropological and statistical approaches, but its use will be easy even for the general bioarchaeological or forensic public. The aim of the project is to reduce subjectivity and at the same time to increase the accuracy and reliability of methods for assessing the age of skeletal remains. The approach is based on quantification of changes in the surface area of the pelvic bone. It is an interconnection of several areas of science, from anthropology, archeology and acquisition of 3D data by surface scanners, through their processing by sophisticated statistical approaches, to computer science. Aplikační garant

STIGMA - School on Theoretical Informatics, Graphs and Mathematical Applications

Program
Studentská vědecká konference ČVUT
Code
SVK 57/16/F8
Period
2016
Description
Cílem konference STIGMA je poskytnout studentům a mladým vědeckým pracovníkům prostor pro prezentaci jejich vědecké práce a činnosti mezi sebou, příležitost naučit se novým technikám a postupům z aktuálních vědeckých výsledků, nabídnout čas, ve kterém mohou účastníci řešit otevřené problémy, a v neposlední řadě též příležitost navázat mezi sebou kontakty. Během dne proběhne několik přednáškových bloků. Zbývající čas je vyhrazen na řešení problémů a diskuze. Doktorandi a studenti přednesou přednášky týkající se buďto jejich vlastního výzkumu, nebo aktuálního vědeckého výsledku zapadajícího do tématiky konference. Mladí vědečtí pracovníci přednesou přednášky, které budou mít za cíl inspirovat studenty k budoucímu výzkumu a nabídnou tak vhodné problémy k řešení. Tématicky je konference vymezena na tyto oblasti: - teoretická informatika - diskrétní matematika - teorie grafů - výpočetní složitost a algoritmy - datové struktury Konference je určena především pro doktorandy a studenty ČVUT, kteří na ní budou mít přednášku.

STIGMA - School on Theoretical Informatics, Graphs and MAthematics

Program
Studentská vědecká konference ČVUT
Code
SVK 54/20/F8
Period
2020
Description
Jedná se již o 5. ročník této konference. Cílem konference STIGMA je poskytnout studentům a mladým vědeckým pracovníkům prostor pro prezentaci jejich vědecké práce a činnosti mezi sebou, příležitost naučit se novým technikám a postupům z aktuálních vědeckých výsledků, nabídnout čas, ve kterém mohou účastníci řešit otevřené problémy, a v neposlední řadě též příležitost navázat mezi sebou kontakty. Během dne proběhne několik přednáškových bloků. Zbývající čas je vyhrazen na řešení problémů a diskuze. Doktorandi a studenti přednesou přednášky týkající se buďto jejich vlastního výzkumu, nebo aktuálního vědeckého výsledku zapadajícího do tématiky konference. Mladí vědečtí pracovníci přednesou přednášky, které budou mít za cíl inspirovat studenty k budoucímu výzkumu a nabídnou tak vhodné problémy k řešení. Tématicky je konference vymezena na tyto oblasti: - teoretická informatika - diskrétní matematika - teorie grafů - výpočetní složitost a algoritmy - datové struktury Konference je určena především pro doktorandy a studenty ČVUT, kteří na ní budou mít přednášku.

STIGMA - School on Theoretical Informatics, Graphs and MAthematics

Program
Studentská vědecká konference ČVUT
Code
SVK 66/24/F8
Period
2024
Description
Cílem konference STIGMA je poskytnout studentům a mladým vědeckým pracovníkům prostor pro prezentaci jejich vědecké práce a činnosti mezi sebou, příležitost naučit se novým technikám a postupům z aktuálních vědeckých výsledků, nabídnout čas, ve kterém mohou účastníci řešit otevřené problémy, a v neposlední řadě též příležitost navázat mezi sebou kontakty. Během dne proběhne několik přednáškových bloků. Zbývající čas je vyhrazen na řešení problémů a diskuze. Doktorandi a studenti přednesou přednášky týkající se buďto jejich vlastního výzkumu, nebo aktuálního vědeckého výsledku zapadajícího do tématiky konference. Mladí vědečtí pracovníci přednesou přednášky, které budou mít za cíl inspirovat studenty k budoucímu výzkumu a nabídnou tak vhodné problémy k řešení. Tématicky je konference vymezena na tyto oblasti: - teoretická informatika - diskrétní matematika - teorie grafů - výpočetní složitost a algoritmy - datové struktury Konference je určena především pro doktorandy a studenty ČVUT, kteří na ní budou mít přednášku.

STIGMA - School on Theoretical Informatics, Graphs and MAthematics

Program
Studentská vědecká konference ČVUT
Code
SVK 54/22/F8
Period
2022
Description
Jedná se již o 7. ročník této konference. Cílem konference STIGMA je poskytnout studentům a mladým vědeckým pracovníkům prostor pro prezentaci jejich vědecké práce a činnosti mezi sebou, příležitost naučit se novým technikám a postupům z aktuálních vědeckých výsledků, nabídnout čas, ve kterém mohou účastníci řešit otevřené problémy, a v neposlední řadě též příležitost navázat mezi sebou kontakty. Během dne proběhne několik přednáškových bloků. Zbývající čas je vyhrazen na řešení problémů a diskuze. Doktorandi a studenti přednesou přednášky týkající se buďto jejich vlastního výzkumu, nebo aktuálního vědeckého výsledku zapadajícího do tématiky konference. Mladí vědečtí pracovníci přednesou přednášky, které budou mít za cíl inspirovat studenty k budoucímu výzkumu a nabídnou tak vhodné problémy k řešení. Tématicky je konference vymezena na tyto oblasti: - teoretická informatika - diskrétní matematika - teorie grafů - výpočetní složitost a algoritmy - datové struktury Konference je určena především pro doktorandy a studenty ČVUT, kteří na ní budou mít přednášku.

STIGMA - School on Theoretical Informatics, Graphs and MAthematics

Program
Studentská vědecká konference ČVUT
Code
SVK 61/23/F8
Period
2023
Description
Cílem konference STIGMA je poskytnout studentům a mladým vědeckým pracovníkům prostor pro prezentaci jejich vědecké práce a činnosti mezi sebou, příležitost naučit se novým technikám a postupům z aktuálních vědeckých výsledků, nabídnout čas, ve kterém mohou účastníci řešit otevřené problémy, a v neposlední řadě též příležitost navázat mezi sebou kontakty. Během dne proběhne několik přednáškových bloků. Zbývající čas je vyhrazen na řešení problémů a diskuze. Doktorandi a studenti přednesou přednášky týkající se buďto jejich vlastního výzkumu, nebo aktuálního vědeckého výsledku zapadajícího do tématiky konference. Mladí vědečtí pracovníci přednesou přednášky, které budou mít za cíl inspirovat studenty k budoucímu výzkumu a nabídnou tak vhodné problémy k řešení. Tématicky je konference vymezena na tyto oblasti: - teoretická informatika - diskrétní matematika - teorie grafů - výpočetní složitost a algoritmy - datové struktury Konference je určena především pro doktorandy a studenty ČVUT, kteří na ní budou mít přednášku.

STIGMA - School on Theoretical Informatics, Graphs and MAthematics

Program
Studentská vědecká konference ČVUT
Code
SVK 55/21/F8
Period
2021
Description
Jedná se již o 6. ročník této konference. Cílem konference STIGMA je poskytnout studentům a mladým vědeckým pracovníkům prostor pro prezentaci jejich vědecké práce a činnosti mezi sebou, příležitost naučit se novým technikám a postupům z aktuálních vědeckých výsledků, nabídnout čas, ve kterém mohou účastníci řešit otevřené problémy, a v neposlední řadě též příležitost navázat mezi sebou kontakty. Během dne proběhne několik přednáškových bloků. Zbývající čas je vyhrazen na řešení problémů a diskuze. Doktorandi a studenti přednesou přednášky týkající se buďto jejich vlastního výzkumu, nebo aktuálního vědeckého výsledku zapadajícího do tématiky konference. Mladí vědečtí pracovníci přednesou přednášky, které budou mít za cíl inspirovat studenty k budoucímu výzkumu a nabídnou tak vhodné problémy k řešení. Tématicky je konference vymezena na tyto oblasti: - teoretická informatika - diskrétní matematika - teorie grafů - výpočetní složitost a algoritmy - datové struktury Konference je určena především pro doktorandy a studenty ČVUT, kteří na ní budou mít přednášku.

STIGMA - School on Theoretical Informatics, Graphs and MAthematics

Program
Studentská vědecká konference ČVUT
Code
SVK 49/18/F8
Period
2018
Description
Jedná se již o 4. ročník této konference. Cílem konference STIGMA je poskytnout studentům a mladým vědeckým pracovníkům prostor pro prezentaci jejich vědecké práce a činnosti mezi sebou, příležitost naučit se novým technikám a postupům z aktuálních vědeckých výsledků, nabídnout čas, ve kterém mohou účastníci řešit otevřené problémy, a v neposlední řadě též příležitost navázat mezi sebou kontakty. Během dne proběhne několik přednáškových bloků. Zbývající čas je vyhrazen na řešení problémů a diskuze. Doktorandi a studenti přednesou přednášky týkající se buďto jejich vlastního výzkumu, nebo aktuálního vědeckého výsledku zapadajícího do tématiky konference. Mladí vědečtí pracovníci přednesou přednášky, které budou mít za cíl inspirovat studenty k budoucímu výzkumu a nabídnou tak vhodné problémy k řešení. Tématicky je konference vymezena na tyto oblasti: - teoretická informatika - diskrétní matematika - teorie grafů - výpočetní složitost a algoritmy - datové struktury Konference je určena především pro doktorandy a studenty ČVUT, kteří na ní budou mít přednášku.

STIGMA - School on Theoretical Informatics, Graphs and MAthematics

Program
Studentská vědecká konference ČVUT
Code
SVK 51/17/F8
Period
2017
Description
Jedná se již o 3. ročník této konference. Cílem konference STIGMA je poskytnout studentům a mladým vědeckým pracovníkům prostor pro prezentaci jejich vědecké práce a činnosti mezi sebou, příležitost naučit se novým technikám a postupům z aktuálních vědeckých výsledků, nabídnout čas, ve kterém mohou účastníci řešit otevřené problémy, a v neposlední řadě též příležitost navázat mezi sebou kontakty. Během dne proběhne několik přednáškových bloků. Zbývající čas je vyhrazen na řešení problémů a diskuze. Doktorandi a studenti přednesou přednášky týkající se buďto jejich vlastního výzkumu, nebo aktuálního vědeckého výsledku zapadajícího do tématiky konference. Mladí vědečtí pracovníci přednesou přednášky, které budou mít za cíl inspirovat studenty k budoucímu výzkumu a nabídnou tak vhodné problémy k řešení. Tématicky je konference vymezena na tyto oblasti: - teoretická informatika - diskrétní matematika - teorie grafů - výpočetní složitost a algoritmy - datové struktury Konference je určena především pro doktorandy a studenty ČVUT, kteří na ní budou mít přednášku.

STIGMA - School on Theoretical Informatics, Graphs and MAthematics

Program
Studentská vědecká konference ČVUT
Code
SVK 49/15/F8
Period
2015
Description
Cílem konference STIGMA je poskytnout studentům a mladým vědeckým pracovníkům prostor pro prezentaci jejich vědecké práce a činnosti mezi s sebou, příležitost naučit se novým technikám a postupům z aktuálních vědeckých výsledků, nabídnout čas, ve kterém mohou účastníci řešit otevřené problémy, a v neposlední řadě též příležitost navázat mezi sebou kontakty. Během dne proběhne několik přednáškových bloků. Zbývající čas je vyhrazen na řešení problémů a diskuze. Doktorandi a studenti přednesou přednášky týkající se buďto jejich vlastního výzkumu, nebo aktuálního vědeckého výsledku zapadajícího do tematiky konference. Mladí vědečtí pracovníci přednesou přednášky, které budou mít za cíl inspirovat studenty k budoucímu výzkumu a nabídnou tak vhodné problémy. Tematicky je konference vymezena na tato témata: - teoretická informatika - diskrétní matematika - teorie grafů a grafové algoritmy - výpočetní složitost a algoritmy Konference je určena především pro doktorandy a studenty ČVUT, kteří na ní budou mít přednášku.

String and Tree Analysis and Processing

Program
Standard projects
Provider
Czech Science Foundation
Code
GA201/09/0807
Period
2009 - 2011
Description
Information society uses results of pattern matching every day and its importance keeps rising. The pattern matching is no longer limited to ordinary texts. Searching in more complex structures is required like searching in trees (XML data structures), in 2D images, or in compressed data. The proposed project aims not only to extend our research results in Stringology, but also apply our knowledge in quite new topic dealing with pattern matching in trees that we call Arborology. Our strong background in parsing seems to be very efficiently utilized in Arborology. In Stringology we would like to continue on topics like multidimensional pattern matching, searching for regularities in strings, generalized string matching, and parallel approaches to pattern matching. In Data Compression we developed algorithms for exact pattern matching in compressed data. We want to improve our results and expand to approximate pattern matching.

Structural Approaches in Stability Under Diversity Constraints

Program
Promoting the mobility of researchers and workers in the framework of international cooperation in R&D
Provider
Ministry of Education, Youth and Sports
Code
8J21AT021
Period
2021 - 2022
Description
Výpočetní kolektivní volba (Computational Social Choice) je moderní oblast informatiky, ve které se setkává teoretická informatika a teorie her (ekonomie). Mnoho zásadních problémů v této oblasti je NP-těžkých, proto se začala v poslední dekádě stále častěji uplatňovat tzv. parametrizovaná analýza, která si klade za cíl identifikovat parametry, jejichž zafixování na malých hodnotách vede k efektivní řešitelnosti daného problému. V předkládaném projektu se hodláme zaměřit na strukturální parametry (mezi nejznámější bezpochyby patří stromová šířka) vstupních instancí, čímž omezíme například vzájemnou interakci mezi agenty hledajícími kolektivní rozhodnutí a podobně.

Text and Tree Structures Processing and Their Applications

Program
Standard projects
Provider
Czech Science Foundation
Code
GA13-03253S
Period
2013 - 2015
Description
The project deals with four topics which are closely related: Arbology, Data Compression for natural languages, and selected topics of Stringology and Bioinformatics. In Arbology we research new indexing and pattern matching algorithms on trees. In Bioinformatics we work on problems of mapping millions of short reads to genomic sequences and their indexing. In Data Compression we focus on efficient algorithms for natural languages based on knowledge of the source language and on algorithms allowing fast compression and decompression as well as efficient search. In Stringology we work on 2D text indexing and on algorithms for identifying cribbed texts and source codes, which may be compressed.

Theoretical computer science, discrete models and algorithms

Program
Studentská grantová soutěž ČVUT
Code
SGS20/208/OHK3/3T/18
Period
2020 - 2022
Description
The main topic of the grant proposal is theoretical computer science, research of discrete models and algorithms. We study complexity of graph and other problems, game theory mechanisms and combinatorial games, we design effective algorithms and we study stringological problems.

Theoretical computer science, discrete models and algorithms

Program
Studentská grantová soutěž ČVUT
Code
SGS23/205/OHK3/3T/18
Period
2023 - 2025
Description
The main topic of the grant proposal is theoretical computer science, research of discrete models and algorithms. We study complexity of graph and other problems, game theory mechanisms and combinatorial games, we design effective algorithms and we study stringological problems.

Tight Parameterized Results for Directed Connectivity Problems

Program
Standard projects
Provider
Czech Science Foundation
Code
GA17-20065S
Period
2017 - 2019
Description
A parameterized or multivariate analysis became in the last two decades a standard approach for (NP-) hard computational problems. Here, in contrast to classical complexity, the efficiency of algorithms is not measured only with respect to the length of the input instance, but also with respect to a specified parameter. Recently, more focus is put on achieving the best possible polynomial degree as well as the best asymptotic time dependency on the parameter. This is justified by providing matching lower bounds, showing that the existence of significantly faster algorithms is improbable, typically relying on the Exponential Time Hypothesis or its strong form. In this research proposal we target on several fundamental problems in network design related to connectivity in directed graphs from the parameterized perspective. Our aim is to either obtain new algorithms for the problems with better running time than that of the existing algorithms, or to obtain lower bounds showing that such an improvement is unlikely. Our main focus are Steiner-type problems in directed graphs.

Tools for Automatizing the Quality Assurance in Large Business Intelligence Systems and Data Warehouses

Program
Programme of applied research and experimental development ALFA
Provider
Technology Agency of the Czech Republic
Code
TA03010964
Period
2013 - 2016
Description
Environments of BI Systems and DWHs consist of thousands of program artefacts. An automatized management of a large amount of the artefacts requires highly powerful tools, which have been lacking in the market. Using recent theoretical results and long-term practical experiences with a maintenance of environments based on SQL and XML standards, we will create tools that will represent a revolutionary change in the area of the current tools of Quallity Assurance, wherein large financial means have been invested.

Tree pattern matching and indexing trees

Program
Studentská grantová soutěž ČVUT
Code
SGS12/092/OHK3/1T/18
Period
2012
Description
With the vast amount of data needed to be archived, indexed and procesed, special data structures are required. The tree is a typical data structure which is used very often for hierarchically storing data. Specialized algorithms are needed for indexing tree data structures and also accessing, extracting and analyzing data stored in them. Examples of applications can be the optimization of abstract syntax trees in the process of compiling, term-rewriting, mechanical theorem proving, searching in phylogenic trees, indexing the secondary structure of RNA, searching in XML documents and evaluating the source code of functional programming languages. For this purpose we have introduced a new research discipline called Arbology, a generalization of Stringology, that deals with tree structures. We use the pushdown automaton as our computational model since the linear notions of trees, being generated by context-free grammars, are in fact context-free languages. The aim of this research is to

User interface generation through a code-inspection driven development

Program
Studentská grantová soutěž ČVUT
Code
SGS12/147/OHK3/2T/13
Period
2012 - 2013
Description
User interface part of software application development is considered time consuming (according to recent research up 50% of the total time is devoted to user interface). Code fragment of the interface part are often complex and hard to read. This is because the interface combines multiple cross-cutting concerns such as security, presentation, layout, validation or contextual help. Besides the presentation aspect itself are here captured information, that already exist elsewhere in the application. This makes the development and maintenance hard. The goal of our project is to minimize manual work that is related to user interface development. We suggest that machine driven code inspection is applied to transform the information to user interface. This allows us to separate cross-cutting interface concerns and manage these individually. All concerns can be combined and weaved together in the transformation process. Besides optimization of the interface code the interface can be generat