Związki pomiędzy teorią grafów a logiką to zagadnienie, które będzie tematem badań prof. Szymona Toruńczyka z Wydziału Matematyki, Informatyki i Mechaniki UW w projekcie Granice strukturalnej podatności (BUKA). Na jego realizację prof. Toruńczyk otrzymał Consolidator Grant przyznany przez Europejską Radę ds. Badań Naukowych (ERC).
W ramach projektu Granice strukturalnej podatności (BUKA, ang. Limits of structural tractability), dofinansowanego na kwotę 1,94 mln euro, prof. Toruńczyk będzie badać logiczną strukturę grafów.
– Graf to sieć połączeń pomiędzy jakimiś obiektami, zwanymi „węzłami”. Grafy są wszechobecne w informatyce, bo za ich pomocą można opisywać różnego rodzaju sieci, m.in. dotyczące stron internetowych, sieci społecznościowych, połączeń kolejowych, samolotowych i drogowych czy inne rozmaite bazy danych. Z tego powodu bardzo dużą rolę w informatyce odgrywają algorytmy, które wykonują różnego rodzaju obliczenia na grafach – wyjaśnia prof. Toruńczyk.
W ramach projektu Granice strukturalnej podatności będą prowadzone badania naukowe, polegające na dowodzeniu twierdzeń matematycznych, określających teoretyczne możliwości algorytmów wykonujących obliczenia na grafach. W tym celu wykorzystywane zostaną narzędzia teoretyczne, obejmujące różne dziedziny matematyki oraz informatyki teoretycznej, takie jak logika, algorytmika, czy kombinatoryka.
Teoria matematyczna
– Fundamentalne znaczenie ma zrozumienie, jak szybko można – teoretycznie – obliczać różne własności opisane za pomocą logiki, na grafach. To, co badam, to jakie własności strukturalne badanych grafów gwarantują, że pewne zadania obliczeniowe da się szybko na nich wykonać – mówi prof. Toruńczyk.
W projekcie wykorzystane zostaną metody matematyczne polegające na stawianiu precyzyjnych, weryfikowalnych hipotez matematycznych i analizowanie ich na konkretnych przykładach. Spodziewane wyniki projektu to stworzenie teorii matematycznej – składającej się z definicji, twierdzeń oraz dowodów, łącznie opisujących teoretyczne granice możliwości efektywnych algorytmów wykonujących pewnego rodzaju obliczenia na grafach, związanych z logiką.
– Dzięki badaniom możliwe będzie rozwinięcie nowych narzędzi w teorii grafów, nazywanych „parametrami grafowymi”. Są to mierzalne parametry liczbowe, które opisują stopień skomplikowania rozważanego grafu – mówi prof. Toruńczyk.
Projekt rozpocznie się w październiku 2024 i będzie trwał pięć lat.
Granty ERC Consolidator
23 listopada Europejska Rada ds. Badań Naukowych (European Research Council, ERC) ogłosiła wyniki konkursu na Consolidator Grants. Granty te przeznaczone są dla odnoszących sukcesy badaczy, z doświadczeniem sięgającym od siedmiu do dwunastu lat od uzyskania stopnia doktora. Dotychczas badacze z UW otrzymali ich jedenaście.
Szymon Toruńczyk ukończył studia magisterskie na Wydziale Matematyki, Informatyki i Mechaniki UW, gdzie w 2011 roku uzyskał też stopień doktora. Jego rozprawa została wyróżniona Nagrodą Ackermanna, nadawaną przez European Association for Computer Science Logic za wybitne prace z zakresu logiki w informatyce. Naukowiec odbył staże podoktorskie na uczelniach The Ecole Normale Supérieure de Cachan (ENS Cachan) oraz Universitat Politècnica de Catalunya w Barcelonie. Habilitację otrzymał w 2020 roku. Publikacje prof. Toruńczyka przedstawiane były na prestiżowych konferencjach poświęconych informatyce teoretycznej.