Zpracování jízdních řádů
Mrkus, František; Fink, Jiří; Pilát, Martin
2024 - English A goal of this thesis is to create an open-source application which could serve as foundation for public bus transport analysis and organizing, while di- rectly operating with timetables in a JDF format for a comfortable workflow. The application is centered aroud bus scheduling for public transport orga- nizers and agencies,including related functions such as displaying timetable sheets and departure/arrival lists, map visualization of the planned routes, and creation of custom timetables. All of these features were sucesfully im- plemented and tested on real-world data. Cílem této práce je vytvořit open-source aplikaci, která by mohla slou- žit jako základ pro analýzu a organizaci veřejné autobusové dopravy, přičemž přímo pracuje s jízdními řády ve formátu JDF, pro zajištění pohodlného pra- covního postupu. Aplikace je zaměřena na plánování autobusových spojů pro organizátory a dopravce veřejné dopravy, včetně souvisejících funkcí, jako je zobrazení jízdních řádů a seznamů odjezdů/příjezdů, vizualizace plánovaných tras na mapě a vytváření vlastních jízdních řádů. Všechny tyto funkce byly úspěšně implementovány a otestovány na reálných datech. Keywords: rozvrhování autobusů|veřejná doprava|optimalizace|vývěsný jízdní řád; bus scheduling|public transport|optimization|spreadsheet timetable Available in a digital repository NRGL Zpracování jízdních řádů

A goal of this thesis is to create an open-source application which could serve as foundation for public bus transport analysis and organizing, while di- rectly operating with timetables in a JDF ...

Mrkus, František; Fink, Jiří; Pilát, Martin
Univerzita Karlova, 2024

Segmentace skenovanych PDF dokumentů
Saydametov, Nikita; Šikudová, Elena; Tódová, Lucia
2024 - English Keywords: PDF|OCR|segmentace; PDF|OCR|segmentation Available in a digital repository NRGL Segmentace skenovanych PDF dokumentů

Saydametov, Nikita; Šikudová, Elena; Tódová, Lucia
Univerzita Karlova, 2024

Textové šifry jako nástroj pro lepší pochopení modelů Transformer
Provazník, Jan; Libovický, Jindřich; Kasner, Zdeněk
2024 - English The Transformer architecture is very popular, so it is potentially im- pactful to interpret what influences its performance. We test the hypothesis that the model relies on the linguistic properties of a text when working with it. We remove interference with cultural aspects of meaning by using a character-level task with the ByT5 Transformer model. We train ByT5 to decipher sentences encrypted with text ciphers (Vigenère, Enigma). We annotate a sentence dataset with linguistic properties with published NLP tools. On this dataset, we study the relationships between the linguistic properties and the fine-tuned ByT5 decipherment error rate. We analyze correlations, train ML models to predict error rates from the properties and interpret them with SHAP. We find small significant correlations but can- not predict error rates from the properties. We conclude the properties we identified do not give much insight into the performance of the Transformer. Architektura Transformer je velmi populární, takže může být potenciálně významné interpretovat, co ovlivňuje její výkon. Testujeme hypotézu, že mo- del se při práci s textem spoléhá na jeho lingvistické vlastnosti. Abychom eli- minovali vliv kultury na význam, používáme úlohu pracující na úrovni znaků s Transformer modelem ByT5. Dotrénujeme ByT5-small na dešifrování vět zašifrovaných pomocí textových šifer (Vigenère, Enigma). Anotujeme eva- luační dataset vět pomocí publikovaných nástrojů pro NLP. Na evaluačním datasetu zkoumáme vztahy mezi lingvistickými vlastnostmi a četností chyb dotrénovaného ByT5 při dešifrování vět. Analyzujeme korelace, trénujeme ML modely na predikci četnosti chyb věty z jijích lingvistických vlastností a interpretujeme důležitost vlastností pomocí SHAP. Nacházíme malé signifi- kantní korelace, ale predikce četnosti chyb z vlastností selhává. Dospíváme k závěru, že identifikované vlastnosti neposkytují vhled do výkonu Transfor- merů. Keywords: Transformer|interpretovatelnost|NLP|deep learning|šifry; Transformer|interpretability|NLP|deep learning|ciphers Available in a digital repository NRGL Textové šifry jako nástroj pro lepší pochopení modelů Transformer

The Transformer architecture is very popular, so it is potentially im- pactful to interpret what influences its performance. We test the hypothesis that the model relies on the linguistic properties ...

Provazník, Jan; Libovický, Jindřich; Kasner, Zdeněk
Univerzita Karlova, 2024

Maskované nadřetězce pro efektivní reprezentaci a indexování množin k-merů
Sladký, Ondřej; Veselý, Pavel; Medvedev, Paul
2024 - English The exponential growth of genomic data calls for novel space-efficient algorithms for compression and search. State-of-the-art approaches often rely on tokenization of the data into k-mers, which are substrings of a fixed length. The popularity of k-mer based methods has led to the development of compact textual k-mer set representations, however, these rely on structural assumptions about the data which may not hold in practice. In this thesis, we demonstrate that all these representations can be viewed as superstrings of the k-mers, and as such can be generalized into a unified framework that we call the masked superstrings of k-mers. We provide two different greedy heuristics for their computation and implement them in a tool called KmerCamel. We further demonstrate that masked superstrings can serve as a building block of a novel, simple k-mer set index which we call FMS-index. Additionally, if masked superstrings further integrate a demasking function f, the resulting f-masked superstrings framework allows for seamless set operations with k-mers. We experimentally evaluate the performance of masked superstrings, as well as of our FMS-index implementation, FMSI, and show that masked superstrings achieve better compression in situations where the previous methods were far from optima. Furthermore, we... Současný exponenciální nárůst genomických dat vyžaduje nové prostorově úsporné algoritmy pro jejich kompresi a vyhledávání. Moderní přístupy často místo původních dat využívají příslušných množin k-merů, což jsou podřetězce pevné délky k. Popu- larita metod založených na k-merech vedla k vzniku kompaktních textových reprezen- tací množin k-merů, jež však stojí na strukturálních předpokladech, které pro data v praxi nemusí platit. V této bakalářské práci ukážeme, že na všechny tyto reprezentace lze nahlížet jako na nadřetězce množin k-merů a jako takové je zobecníme pomocí uceleného konceptu, kterému říkáme maskované nadřetězce k-merů. Navrhneme dva různé hladové algoritmy na jejich výpočet a implementujeme je v nástroji KmerCamel. Dále demonstru- jeme, že maskované nadřetězce fungují jako stavební kámen pro nový a jednoduchý index pro množiny k-merů, který nazýváme FMS-index. Pokud k maskovaným nadřetězcům přiřadíme navíc odmaskovávací funkci f, výsledný koncept f-maskovaných nadřetězců umožňuje jednoduché provádění množinových operací s k-mery. Experimentálně ověříme prostorovou úspornost maskovaných nadřetězců, stejně tak i naší implementace FMS- indexu. Ukážeme, že maskované nadřetězce jsou lépe komprimovatelné v situacích, kde předchozí přístupy byly daleko od optima a že FMS-index je prostorově... Keywords: množiny k-merů|bioinformatika|výpočetní genomika|datové struktury|algoritmy|problém nejkratšího nadřetězce; k-mer sets|bioinformatics|computational genomics|data structures|algorithms|shortest superstring problem Available in a digital repository NRGL Maskované nadřetězce pro efektivní reprezentaci a indexování množin k-merů

The exponential growth of genomic data calls for novel space-efficient algorithms for compression and search. State-of-the-art approaches often rely on tokenization of the data into k-mers, which are ...

Sladký, Ondřej; Veselý, Pavel; Medvedev, Paul
Univerzita Karlova, 2024

Vícejazyčné propojování entit pomocí vektorového vyhledávání
Farhan, Dominik; Straka, Milan; Bojar, Ondřej
2024 - English Entity linking (EL) is the computational process of connecting textual mentions to corresponding entities. Like many areas of natural language processing, the EL field has greatly benefited from deep learning, leading to significant performance improvements. However, present-day approaches are expensive to train and rely on diverse data sources, complicating their reproducibility. In this thesis, we develop multiple systems that are fast to train, demonstrating that competitive entity linking can be achieved without a large GPU cluster. Moreover, we train on a publicly available dataset, ensuring reproducibility and accessibility. Our models are evaluated for 9 languages giving an accurate overview of their strengths. Furthermore, we offer a detailed analysis of bi-encoder training hy- perparameters, a popular approach in EL, to guide their informed selection. Overall, our work shows that building competitive neural network based EL systems that oper- ate in multiple languages is possible even with limited resources, thus making EL more approachable. Propojování entit je úloha, ve které jsou zmínky z textu propojovány s příslušnými entitami. Stejně jako v mnoha jiných oblastech zpracovaní přirozeného jazyka se i v pro- pojování entit výrazně projevil vliv hlubokého učení, což vedlo k významnému zlepšení výkonu. V současnosti se ale stávající modely trénují pomalu a spoléhají na nejednotné zdroje dat, což ve výsledku komplikuje reprodukovatelnost. V této práci vyvíjíme něko- lik systémů, které se učí rychle, čímž ukazujeme, že konkurenceschopných výsledků lze dosáhnout i bez velkého GPU clusteru. Zároveň trénujeme na konkrétním veřejně dostup- ném datasetu. Naše výsledky jsou tak snadno reprodukovatelné. Modely vyhodnocujeme na devíti jazycích, což nám poskytuje kvalitní přehled o jejich silných stránkách. Mimo to také podrobně analyzujeme nastavení značného množství hyperparametrů bi-enkóderů - populárního přístupu pro propojování entit - čímž zjednodušujeme rozhodování na- vazujícím pracem. Náš výzkum ukazuje, že lze vytvářet silné mnohojazyčné systémy na propojování entit i za použití pouze omezených výpočetních zdrojů. Tím činíme celou úlohu přístupnější. Keywords: propojování entit|vektorové vyhledávání|vícejazyčné propojování entit|bi-enkóder; entity linking|dense retrieval|entity disambiguation|multilingual entity linking|bi-encoder Available in a digital repository NRGL Vícejazyčné propojování entit pomocí vektorového vyhledávání

Entity linking (EL) is the computational process of connecting textual mentions to corresponding entities. Like many areas of natural language processing, the EL field has greatly benefited from deep ...

Farhan, Dominik; Straka, Milan; Bojar, Ondřej
Univerzita Karlova, 2024

Vizuální editace doménové řídící informace pro plánování
Gráf, Martin; Barták, Roman; Chrpa, Lukáš
2024 - English The ability to only define the physics of an environment in classical plan- ning tasks has been a long-standing obstacle in practical applications of such an approach. Current generic planners are typically capable of finding a solution to a given problem, but their inability to consider domain-specific constraints is often mirrored in a significant performance gap when compared to domain-specific algorithms. Remedying this gap would prove invaluable in making classical domain-independent planners viable in production envi- ronments. In this paper, we will first introduce the area of classical planning and briefly touch on popular approaches to solving planning tasks. We will then show the principle of Attributed Transition-Based Domain Control Knowledge, which encodes additional problem-specific information into a domain. Finally, we will present our implementation along with experimental results. Schopnost definovat pouze možnosti prostředí v úkolu klasického plá- nování je dlouhodobou překážkou pro praktické aplikace tohoto přístupu. Moderní obecné plánovače jsou typicky schopné nalézt řešení daného pro- blému, ale jejich neschopnost využít informací specifických pro doménu se často projeví ve výrazném rozdílu výkonu oproti algoritmům přizpůsobeným dané doméně. Pro použitelnost obecných plánovačů v produkčních prostře- dích je tudíž klíčové tento výkonostní rozdíl dohnat. V této práci nejprve představíme téma klasického plánování a krátce shr- neme běžné přístupy k řešení plánovacích problémů. Poté popíšeme princip Attributed Transition-Based Domain Control Knowledge, což je technika pro zakódování kontextuálních informací do domény a problému. Nakonec odpre- zentujeme naší implementaci spolu s experimentálními výsledky. Keywords: znalostní inženýrství|doménové řídící informace|klasické plánování; domain control knowledge|classical planning|knowledge engineering Available in a digital repository NRGL Vizuální editace doménové řídící informace pro plánování

The ability to only define the physics of an environment in classical plan- ning tasks has been a long-standing obstacle in practical applications of such an approach. Current generic planners are ...

Gráf, Martin; Barták, Roman; Chrpa, Lukáš
Univerzita Karlova, 2024

Experimentální analýza dotazovacích jazyků v moderních databázových systémech
Čorovčák, Martin; Koupil, Pavel; Holubová, Irena
2024 - English The rise of Big Data has highlighted the limitations of relational databases while handling large datasets, leading to the growth of NoSQL databases. This has made DBMS benchmarking crucial for performance evaluation and decision-making. This thesis compares relational (MySQL, SQLite), graph (Neo4j, ArangoDB), docu- ment (MongoDB), and column-family (Cassandra) databases. We analyze the expressive power of their query languages and their runtime efficiency across varying data sizes. We conclude, that there's no "number one" solution for all use cases. The choice depends on factors like data volume, query complexity, and the need for joins. For complex queries and frequent joins, MySQL and SQLite are the most expressive but may struggle with very large datasets. Cassandra and MongoDB excel in perfor- mance and scalability but require efficient schema design and targeted data redundancy. ArangoDB presents a versatile option capable of handling multiple data models but might require further investigation into its performance compared to Neo4j. Príchod Vel'kých Dát poukázal na obmedzenia relačných databáz pri spracovanível'kých datasetov, čo viedlo k nárastu NoSQL databáz. Z tohto dôvodu sa DBMS benchmarking stal kl'účovým pre hodnotenie výkonnosti a celkový rozhodovací proces. Táto práca porovnáva relačné (MySQL, SQLite), grafové (Neo4j, ArangoDB), doku- mentové (MongoDB) a stĺpcovo-orientované (Cassandra) databázy. Analyzujeme vyja- drovaciu silu ich dopytovacích jazykov a efektivitu počas behu pri rôznych vel'kostiach dát. Dospeli sme k záveru, že neexistuje žiadne riešenie "číslo jeden" pre všetky prípady použitia. Výber závisíod faktorov, ako je objem dát, zložitost' dopytov a potreba spájania. V prípade zložitých dotazov a častého spájania majú MySQL a SQLite najv̈ačšiu vy- jadrovaciu silu, avšak môžu mat' problémy s vel'mi vel'kými datasetmi. Cassandra a Mon- goDB vynikajú výkonom a škálovatel'nost'ou, ale vyžadujú efektívny návrh schématu a cielenú redundanciu dát. ArangoDB predstavuje univerzálnu možnost', ktorá dokáže pra- covat' s viacerými dátovými modelmi, ale pre hlbšie porovnanie s Neo4j sa môže vyžadovat' d'alší výskum ich výkonu. Keywords: databázové systémy|výkon|benchmark|statická analýza|experimentální analýza; database management systems|performance|benchmark|static analysis|experimental analysis Available in a digital repository NRGL Experimentální analýza dotazovacích jazyků v moderních databázových systémech

The rise of Big Data has highlighted the limitations of relational databases while handling large datasets, leading to the growth of NoSQL databases. This has made DBMS benchmarking crucial for ...

Čorovčák, Martin; Koupil, Pavel; Holubová, Irena
Univerzita Karlova, 2024

AgentLang - Programovací jazyk pre agentovo orientované modelovanie
Boďa, Tomáš; Petříček, Tomáš; Bednárek, David
2024 - English With the increasing popularity of the agent-based simulation technique in various scientific fields, there is a demand for an all-in-one framework for modeling agent-based simulations. Although there are numerous agent-based tools available, these in most cases feature complex syntax and language structures or are aimed to be used in specific domains only. In response this thesis presents a new approach to modeling agent-based simulations by developing a brand new agent-based framework - AgentLang. The frame- work features a programming language with a unified and simple syntax for defining agents and their properties. Moreover, it provides a web-based interface with a spread- sheet module for manipulating agents and their values using the familiar spreadsheet format as well as a visualisation module for rendering the simulation in real-time. These three features of the AgentLang framework aim to introduce a new way to modeling agent-based simulations and attempt to make agent-based modeling more accessible to people of all scientific fields. S rastúcou popularitou techniky agentovo orientovaného modelovania v rôznych ve- deckých oblastiach vzniká dopyt po jednotnom nástroji na modelovanie simulácií. Aj keď je na trhu dostupné množstvo nástrojov na agentovo orientované modelovanie, vo vač- šine prípadov sa vyznačujú zložitou jayzkovou syntaxou a štruktúrou alebo sú určené na použitie iba v špecifických oblastiach. Vzhľadom na tieto nevýhody táto práca poskytuje nový pohľad na agentovo orientované modelovanie tým, že vyvíja nový nástroj na mo- delovanie agentovo orientovaných simulácií - AgentLang. Tento nástroj poskytuje nový programovací jazyk s jednotnou, ucelenou a jednoduchou syntaxou na definovanie agen- tov a ich vlastností. Okrem toho poskytuje webovú aplikáciu s tabulkovým rozhraním na manipuláciu agentov a ich hodnôt. V neposlednom rade obsahuje vizualizačný modul na zobrazovanie simulácií v reálnom čase. Tieto tri vlastnosti nástroja AgentLang majú za cieľ poskytnúť nový spôsob modelovania agentovo orientovaných simulácií a sprístupniť agentovo orientované modelovanie používateľom zo všetkých vedeckých odvetví. Keywords: agentovo orientované modelovanie|simulácie|programovací jayzk|interpreter; agent-based modeling|simulation|programming language|interpreter Available in a digital repository NRGL AgentLang - Programovací jazyk pre agentovo orientované modelovanie

With the increasing popularity of the agent-based simulation technique in various scientific fields, there is a demand for an all-in-one framework for modeling agent-based simulations. Although there ...

Boďa, Tomáš; Petříček, Tomáš; Bednárek, David
Univerzita Karlova, 2024

Průhlednost nezávislá na pořadí
Rožek, Matúš; Kahoun, Martin; Iser, Tomáš
2024 - English Rendering transparent geometry in realtime brings a set of problems as the transpar- ent objects need to be sorted first and rendered in order from back to front for their correct overlaying. A set of rendering algorithms called Order Independent Transparency (OIT) tries to accomplish this without sorting the geometry in advance. We create a program implementing five algorithms and compare their weaknesses, strengths, and properties. Some algorithms might excel in certain conditions and produce great results, yet fall short in slightly different environments. We aim to answer the question of which OIT algorithm is best suited for which scenarios. Vykresľovanie priehľadnej geometrie v reálnom čase spôsobuje sadu problémov, pre- tože jednotlivé objekty potrebujú byť zoradené a vykreslené v poradí odzadu dopredu pre korektný výsledok. Existuje avšak trieda algoritmov, ktorá sa snaží o vykreslenie obrazu aj bez potreby priehľadné objekty najprv zoradiť. Tieto algoritmy sa nazývajú "priehľadnosť nezávislá na poradí" (anglicky Order Independent Transparency, skratka OIT). Vytvorili sme program, ktorý obsahuje 5 rôznych OIT algoritmov. Poukazujeme na silné a slabé stránky jednotlivých prístupov - niektoré môžu excelovať v určitých pod- mienkach, ale zato podávať výrazne slabšie výsledky v odlišnom prostredí. Snažíme sa odpovedať na otázku, ktorý OIT algoritmus je najlepšie využiť v akej situácii. Keywords: priehľadnosť nezávislá na poradí|vykresľovanie priehľadnosti|alfa kompozícia|realtime rendering; order independent transparency|transparency rendering|alpha compositing|realtime rendering Available in a digital repository NRGL Průhlednost nezávislá na pořadí

Rendering transparent geometry in realtime brings a set of problems as the transpar- ent objects need to be sorted first and rendered in order from back to front for their correct overlaying. A set of ...

Rožek, Matúš; Kahoun, Martin; Iser, Tomáš
Univerzita Karlova, 2024

Zjednodušení použitelnosti nástrojů pro správu kvality dat pro datové inženýry
Tomis, Zdeněk; Bulej, Lubomír; Škoda, Petr
2024 - English In the realm of data quality management, integrating robust data quality rules into automated workflows and data pipelines is essential for maintaining data integrity. This thesis addresses the gap in programmatic accessibility of Ataccama ONE's data qual- ity tools, which primarily leverage the proprietary Ataccama Expression Language. By reimplementing this language in Python, the project enhances its usability for data en- gineers who seek to consume these tools programmatically. The focus is on enabling data engineers to execute Ataccama's rules directly within Python. The viability of this implementation is tested through performance comparisons with similar solutions. V oblasti data quality managementu je pro zachování integrity dat zásadní integrovat pravidla kvality dat do automatizovaných workflows a datových pipelines. Tato práce se zabývá mezerou v programové dostupnosti nástrojů pro kvalitu dat společnosti Ataccama ONE, které využívají především proprietární jazyk Ataccama Expression Language. Re- implementací tohoto jazyka v jazyce Python projekt zvyšuje jeho použitelnost pro datové inženýry, kteří potřebují tyto nástroje využít programmaticky v různým prostředích. Dů- raz je kladen na to, aby datoví inženýři mohli provádět a spravovat pravidla Ataccama přímo v jazyce Python s ohledem na jednoduchost užití a minimální nároky. Užitelnost této implementace je otestována prostřednictvím porovnání výkonu s podobnými řeše- ními. Keywords: data quality management|data engineering|performance evaluation; data quality management|data engineering|performance evaluation Available in a digital repository NRGL Zjednodušení použitelnosti nástrojů pro správu kvality dat pro datové inženýry

In the realm of data quality management, integrating robust data quality rules into automated workflows and data pipelines is essential for maintaining data integrity. This thesis addresses the gap in ...

Tomis, Zdeněk; Bulej, Lubomír; Škoda, Petr
Univerzita Karlova, 2024