Seminar za teorijsko racunarstvo - 06.06.2022.

[Robert Manger]

Dragi kolege,

Na zajedničkom sastanku Seminara za teorijsko računarstvo te Seminara za matematičku logiku i osnove matematike, u ponedjeljak 6. lipnja 2022. u 15 sati, Goran Žužić (ETH Zurich, Computer Science Department) održat će predavanje pod naslovom:

"Universal optimality in distributed computing and its connections to diverse areas of theoretical computer science".

Sažetak: The modern computation and information processing systems shaping our world have become massively distributed, and a fundamental understanding of distributed algorithmics has never been more important. At the same time, despite 40 years of intense study, we often do not have an adequate understanding of the fundamental barriers that rule out the existence of ultra-fast distributed algorithms. This is true even for the most well-studied problems in computer science---including the shortest path, minimum spanning tree, minimum cut, and many other well-known tasks. In this talk, I will present a high-level overview of a sequence of papers that give a near-complete answer to the above question. Its culmination is the following pie-in-the-sky result called *universal optimality*: for all of the tasks mentioned, there exists a single distributed algorithm that, when run on any communication network G, is provably competitive with the fastest algorithm on G. The pursuit of universal optimality has led to the development of many new connections between distributed computing and other seemingly unrelated areas of theoretical computer science. Curiously, these connections have been mutually-beneficial and have already led to many breakthroughs not only in distributed computing, but also in the theory of metric embedding, information theory, and oblivious packet routing. I will briefly explore these connections.

Predavanje će se održati UŽIVO u zgradi PMF-Matematičkog odsjeka, dvorana 104.

Pozivaju se članovi oba seminara, studenti diplomskih studija, kao i ostali zainteresirani da se pridruže.

Lijep pozdrav, Robert Manger.

[Robert Manger]

Dragi kolege,

U okviru Seminara za teorijsko računarstvo, u ponedjeljak 10. listopada 2022. u 15 sati, Robert Manger (PMF-MO, Zagreb) održat će predavanje pod naslovom:

"O računskoj složenosti problema dvostruke rimske dominacije".

Sažetak: Dvostruka rimska dominacija (DRD) je optimizacijski problem koji se zadaje na neusmjerenom grafu. Može se smatrati nadogradnjom klasičnog problema dominirajućeg skupa vrhova ili problema (jednostavne) rimske dominacije. Primjenjuje se u operacijskim istraživanjima, npr. za određivanje optimalnog broja i rasporeda vatrogasnih postrojbi koji će za odabrane lokacije u gradu omogućiti zadovoljavajuću razinu obranjivosti od požara. U ovom predavanju daje se pregled novijih članaka raznih autora koji se odnose na računsku složenost problema DRD. Pokazuje se da je problem NP-težak, i to ne samo u općenitom slučaju nego i za neke specijalnije vrste grafova (npr. planarne ili bipartitne grafove). S druge strane, pokazuje se da postoje i takve vrste grafova (npr. stabla ili intervalni grafovi) gdje se rješenje može dobiti u polinomijalnom vremenu.

Predavanje će se održati UŽIVO u zgradi PMF-Matematičkog odsjeka, dvorana 104.

Pozivaju se članovi seminara, studenti diplomskih studija, kao i ostali zainteresirani da se pridruže.

Lijep pozdrav, Robert Manger.

[Robert Manger]

Dragi kolege,

U okviru Seminara za teorijsko računarstvo, u ponedjeljak 24. listopada 2022. u 15 sati, profesorica Antoaneta Klobučar (Ekonomski fakultet Osijek) održat će predavanje pod naslovom:

"Total and double total dominations in some chemical graphs".

Sažetak: Let G be a graph with the vertex set V(G). A set D⊆V(G) is a total dominating set if every vertex v∈V(G) has a neighbor in D. The total domination number γt(G) is the cardinality of the smallest total dominating set. Further, a set D⊆ V(G) is a total k-dominating set if every vertex v∈V(G) has at least k neighbors in D. The total k-domination number γkt(G) is the cardinality of the smallest total k-dominating set. For k= 2 the total 2-dominating set is a called double total dominating set. In this work, we study total and double total dominations on different chemical graphs such as hexagonal grid, pyrene network and hexabenzocoronene. We give the lower and the upper bound for total and double total numbers on mentioned graphs. All mentioned graphs are obtained by arranging congruent regular hexagons in a plane. They are of significant importance in theoretical chemistry as a natural graph representation of benzenoid hydrocarbons.

Predavanje će se održati u obliku telekonferencije (on-line) na platformi Zoom. Podaci za spajanje:

Join Zoom Meeting
https://zoom.us/j/91306796811?pwd=WEcvU3o1SU1DQmg1ZXRnWXNxK1lZQT09

Meeting ID: 913 0679 6811
Passcode: 745898

[Robert Manger]

Dragi kolege,

U okviru Seminara za teorijsko računarstvo, u ponedjeljak 14. studenog 2022. u 15 sati, Matej Mihelčić (PMF-Matematički odsjek, Zagreb) održat će predavanje pod naslovom:

"Varijante problema traženja redeskripcija i njihove klase složenosti".

Sažetak: Predavač će formalno definirati nekoliko varijanti problema traženja redeskripcija, formuliranih kao problem odluke, te predstaviti dokaze njihovih pripadnosti u odgovarajuće klase složenosti. Analizirat će se svi važniji parametri problema kao što su točnost redeskripcija (Jaccard index), značajnost, veličina pravila koja tvore redeskripciju itd. Doprinos je nastao u suradnji s kolegom Adrianom Satjom Kurdijom.

[Robert Manger]

Dragi kolege,

Na zajedničkom sastanku Seminara za matematičku logiku i Seminara za teorijsko računarstvo, u ponedjeljak 5. prosinca 2022. u 17 sati, Sandro Lovnički (tvrtka Friendly Fire) održat će predavanje pod naslovom:

"Kako smo se našli ovdje? Od paradoksa do strojeva".

Sažetak: Rano 20. stoljeće je razdoblje potrage za konzistentnim temeljima matematike. Istražit ćemo glavne aktere i događaje koji su nas od jednostavnih pitanja odluke doveli do presudnih teorema nepotpunosti i formalizacije pojma izračunljivosti.

Predavanje će se održati UŽIVO u zgradi PMF-Matematičkog odsjeka, dvorana 105.

Predavanje će se također moći pratiti online preko Zoom linka: https://zoom.us/j/97325200710?pwd=b2g1ZCtSTjk1dmRQZVVYWTUwOFdMZz09

Pozivaju se članovi oba seminara, studenti diplomskih studija, kao i ostali zainteresirani da se pridruže. Molim vas, primijetite da je vrijeme održavanja drukčije nego što je uobičajeno.

Lijep pozdrav, Robert Manger.

[Robert Manger]

Dragi kolege,

U okviru Seminara za teorijsko računarstvo, u ponedjeljak 20. ožujka 2023. u 15 sati, Davor Runje (airt, Zagreb) održat će predavanje pod naslovom:

"Constrained Monotonic Neural Networks".

Sažetak: Deep neural networks are becoming increasingly popular in approximating arbitrary functions from noisy data. But wider adoption is being hindered by the need to explain such models and to impose additional constraints on them. Monotonicity constraint is one of the most requested properties in real-world scenarios and is the focus of this paper. One of the oldest ways to construct a monotonic fully connected neural network is to constrain its weights to be non-negative while employing a monotonic activation function. Unfortunately, this construction does not work with popular non-saturated activation functions such as ReLU, ELU, SELU etc, as it can only approximate convex functions. We show this shortcoming can be fixed by employing the original activation function for a part of the neurons in the layer and employing its point reflection for the other part. Our experiments show this approach of building monotonic deep neural networks has matching or better accuracy when compared to other state-of-the-art methods such as deep lattice networks or monotonic networks obtained by heuristic regularization. This method is the simplest one in the sense of having the least number of parameters and does not require any modifications to the learning procedure or steps post-learning steps.

Predavanje će se održati UŽIVO u zgradi PMF-Matematičkog odsjeka, dvorana 104.

Pozivaju se članovi seminara, studenti diplomskih studija, kao i ostali zainteresirani da se pridruže.

Lijep pozdrav, Robert Manger.

[Robert Manger]

Dragi kolege,

U okviru Seminara za teorijsko računarstvo, u ponedjeljak 17. travnja 2023. u 15 sati, Dora Raštegorac (Hrvatska narodna banka) održat će predavanje pod naslovom:

"Analiza i vizualizacija podataka pomoću softvera Tableau".

Sažetak: Softver Tableau je alat za vizualizaciju podataka i interakciju s njima. Interakcija se ostvaruje kroz VizQL (engl. Visual Query Language) koji povuci-i-ispusti (engl. drag-and-drop) poteze pretvara u podatkovne upite. Već šest godina Tableau je jedan od najpopularnijih alata za vizualizaciju podataka, no ima i neka ograničenja. S njima ćemo se upoznati na ovom izlaganju. Također, dat ćemo usporedbu Tableaua i drugih, sličnih alata te ćemo njegove razne mogućnosti ilustrirati nizom primjera.

[Robert Manger]

Dragi kolege,

U okviru Seminara za teorijsko računarstvo, u ponedjeljak 8. svibnja 2023. u 15 sati, Katarina Kozina (tvrtka Syntio) održat će predavanje pod naslovom:

"Objektno-relacijske baze podataka".

Sažetak: Većina baza podataka zasniva se na relacijskom modelu. No već godinama razvija se i objektni model, koji je inspiriran objektno-orijentiranim programskim jezicima. U ovom predavanju opisuju se objektno-relacijske baze podataka. One su nastale su kao kompromis između relacijskih i objektno-orijentiranih baza i kao takve imaju značajke oba modela. U predavanju se također prikazuje studijski primjer oblikovanja i testiranja konkretne objektno-relacijske baze podataka.

[Robert Manger]

Dragi kolege,

Na zajedničkom sastanku Seminara za teorijsko računarstvo te Seminara za matematičku logiku i osnove matematike, u ponedjeljak 13. studenoga 2023. godine u 17:15 sati, u predavaonici 201 na PMF-MO, Juraj Brigljević će održati predavanje pod naslovom:

Rješavanje problema maksimalnog težinskog nezavisnog skupa

Sažetak: Problem maksimalnog težinskog nezavisnog skupa (MWIS) spada u područje diskretne optimizacije na grafovima. S obzirom da je riječ o NP-teškom problemu, opravdano je korištenje heuristika za njegovo rješavanje u općenitom slučaju. Heuristika koju smo proučili utemeljena je na dvjema paradigmama: ponavljanom lokalnom pretraživanju (ILS) odnosno varijabilnom spustu uz korištenje susjedstava (VND). Testiranjem na bazama podataka BHOSLIB i DIMACS uvjerili smo se da navedena heuristika može izrazito brzo pronaći dobra rješenja, a vrlo često i optimalna odnosno najbolja poznata rješenja. Osim heuristike ILS-VND, koja radi na općenitim grafovima, proučili smo postoji li bolje rješenje za jednu posebnu vrstu grafova, a to su stabla. Pokazalo se da se pomoću paradigme dinamičkog programiranja može definirati egzaktni algoritam koji rješava MWIS problem na stablima u linearnom vremenu s obzirom na broj vrhova.

Molim vas obratite pažnju na promjenu termina i dvorane.

Osim uživo, predavanje se također može pratiti preko sljedećeg Zoom linka: https://zoom.us/j/97325200710?pwd=b2g1ZCtSTjk1dmRQZVVYWTUwOFdMZz09

Pozivaju se članovi oba seminara, studenti diplomskih studija, kao i ostali zainteresirani da se pridruže.

Lijep pozdrav, Robert Manger.

[Robert Manger]

Dragi kolege,

Na zajedničkom sastanku Seminara za teorijsko računarstvo te Seminara za matematičku logiku i osnove matematike, u ponedjeljak 15. siječnja 2024. godine u 17:15 sati, u predavaonici 201 na PMF-MO, Marin Jezidžić (tvrtka P3 Mobility) održati će predavanje pod naslovom:

Metode kombiniranja klasifikatora te primjena na problem prepoznavanja govora

Sažetak: U ovome predavanju proučavat će se metode kombiniranja klasifikatora. Prvo će se uvesti najosnovnija terminologija, opisati najčešće korišteni algoritmi poput Boosting, Random Forests i Mixture of Experts te će se na primjeru prepoznavanja govora iskoristiti opisane tehnike. Naglasak će biti na naprednim Transformerskim arhitekturama i njihovim nasljednicima poput Conformera i Branchformera.

[Robert Manger]

Dragi kolege,

Na zajedničkom sastanku Seminara za teorijsko računarstvo te Seminara za matematičku logiku i osnove matematike, u ponedjeljak 15. travnja 2024. godine u 17:15 sati, u predavaonici 201 na PMF-MO, Dora Raštegorac (Hrvatska narodna banka) održati će predavanje pod naslovom:

Detaljan prikaz mogućnosti softvera Tableau

Sažetak: Vizualizacija podataka je grafički prikaz informacija i podataka. Koristeći tablice, grafove i mape, alati za vizualizaciju podataka omogućuju razumijevanje trendova i obrazaca u podacima. Jedan od takvih alata je Tableau koji je već više godina za redom među najboljim alatima za analizu i vizualizaciju podataka. U ovom izlaganju uvjerit ćemo se u važnost vizualizacije podataka u svakodnevnom životu. Također, predstavit ćemo alat Tableau, od mogućih načina pripreme podataka, do prikaza grafova, mapa i izrade interaktivnih prezentacija.

Osim uživo, predavanje će se također moći pratiti i preko platforme Zoom na sljedećem linku:

https://zoom.us/j/92097695820?pwd=c0cyS05zV1NFWWRXL2I4NHVQRFZRZz09

[Robert Manger]

Dragi kolege,

Na zajedničkom sastanku Seminara za teorijsko računarstvo te Seminara za matematičku logiku i osnove matematike, u ponedjeljak 20. svibnja 2024. godine u 17:15 sati, u predavaonici 201 na PMF-MO, Robert Manger će održati predavanje pod naslovom:

Rješavanje problema dvostruke rimske dominacije s minimalnom cijenom

Sažetak: Dvostruka rimska dominacija (DRD) je optimizacijski problem koji se zadaje na neusmjerenom grafu. Formalno se opisuje kao pridruživanje težina vrhovima grafa u skladu s određenim pravilima. Neformalno, problem se može interpretirati kao raspoređivanje davatelja usluge (npr. vojnih jedinica, vatrogasnih brigada ili bolničkih kola) po odabranim lokacijama unutar nekog geografskog područja. Pritom cjelokupna usluga (tj. odgovor na neprijateljske napade, požare ili hitne medicinske slučajeve) treba biti uspostavljena na najjeftiniji način, s time da još uvijek bude osigurana tzv. "dvostruko-rimska" razina njezine dostupnosti i pouzdanosti. Standardna verzija DRD iz postojeće literature poistovjećuje ukupan trošak s ukupnim brojem potrebnih davatelja usluge. U ovom radu razmatra se nova verzija DRD zasnovana na minimalnoj cijeni, koja je općenitija i realističnija od standardne verzije. Polazi se od pretpostavke da se stvarni troškovi davanja usluge mogu razlikovati od lokacije do lokacije. Dakle, formalno govoreći, svakom vrhu u grafu zadana je cijena koja se interpretira kao cijena držanja jednog davatelja usluge na odgovarajućoj lokaciji. U radu se najprije primjećuje da je razmatrani DRD problem s minimalnom cijenom NP-težak, i to ne samo za općenite grafove nego također i za mnoge posebne klase grafova. Dalje, konstruira se algoritam dinamičkog programiranja koji pokazuje da se problem ipak može riješiti u linearnom vremenu ako razmatrani graf ima oblik stabla. Na kraju, kao rješenje za općenite grafove, predlaže se heuristika zasnovana na pohlepnom pristupu i lokalnom traženju.

Osim uživo, predavanje će se također moći pratiti i preko platforme Zoom na sljedećem linku:

https://zoom.us/j/91249923788?pwd=NmlLcVVuNU5LZDhXMGhEYjd1VXEvQT09