Zakład Inżynierii Oprogramowania

Zakład Inżynierii Oprogramowania prowadzi badania naukowe zarówno w zakresie teoretycznych podstaw inżynierii oraz jej praktycznych aspektów. W szczególności badania dotyczą:

  • teorii kodów
  • teorii grafów
  • teorii języków formalnych
  • testowania oprogramowania
  • inżynierii jakości oprogramowania

Projekty realizowane w Zakładzie Inżynierii Oprogramowania:

  • skalowalny, rozproszony, samoadaptacyjny system do optymalizowania i przeprowadzania testów mutacyjnych
  • model TDD+M (Test-Driven Development + Mutation) oraz jego skuteczność w zakresie jakości tworzonego kodu przy użyciu tej metodyki
  • nowe metryki statyczne przepływu danych i ich zdolność predykcji defektów
  • model TQED wspomagający kreatywność projektowania testów oprogramowania
  • korpus wysokiej jakości danych z rzeczywistych projektów open-source’owych zawierający pomiar metryk oprogramowania oraz informacje o znalezionych defektach
  • wykorzystanie metod nauczania maszynowego do automatycznej predykcji defektów w trybie "just-in-time" (system ADePT)
  • metodyka zapewniania jakości oparta na predykcji defektów w oprogramowaniu w zastosowaniu do systemów krytycznych w przemyśle
  • synchronizacja automatów skończonych
  • teoria kodów (w tym kody wielowymiarowe) oraz własności rozstrzygalności bycia kodem dla różnych rodzin kodów

Seminarium zakładowe

Semestr letni 2020/21

Seminarium odbywa się w czwartki w godz. 10:30-12:00, w sali 1086 (w związku z epidemią - aktualnie na MS Teams, do zespołu można dołączyć przez kod: d70ru5i). Tematyka seminarium: testowanie i jakość oprogramowania, teoria języków formalnych, teoria grafów.

 

10 VI 2020

Prelegent: Maciej Brzeski

Temat: Wyszukiwanie podobnych podgrafów przy pomocy statystyki chi-kwadrat

Opis: Grafy etykietowane dostarczają naturalną drogę do reprezentowania różnych danych czy relacji. Mając zadany graf chcemy znaleźć najbardziej podobne w danym zbiorze grafów (lub najbardziej podobne podgrafy w wielkim grafie). Podejścia bazujące na izomorfizmie lub dopasowaniu grafów (tzw. graph matching) są NP-zupełne, co uniemożliwia stosowanie ich dla większych zbiorów danych. Jako alternatywę zaczęto rozważać algorytmy aproksymujące. W referacie przedstawię podejście, gdzie graf jest opisywany przez rozkład etykiet w sąsiednich wierzchołkach, a charakterystyka podobieństwa grafu jest oparta na istotności statystycznej uchwyconej przez statystykę chi-kwadrat. Referat na podstawie pracy Sourav Dutta i in., "Neighbor-Aware Search for Approximate Labeled Graph Matching using the Chi-Square Statistics". 

 

27 V 2021

Prelegent: Jakub Ruszil

Temat: Problem podziału na zbiory dominujące dla grafów skierowanych

Opis: W referacie pochylę się nad problemem podziału wierzchołków skierowanego grafu na zbiory dominujące. Udowodnię NP-zupełność tego problemu w ogólnym przypadku, a następnie przedstawię liniowy algorytm rozwiązujący ten problem w przypadku zorientowanych drzew. Referat na podstawie pracy Partitioning vertices into in- and out- dominating sets in digraphs - Kosuke Nakamura Toru Araki.

 

20 V 2021

Prelegent: Małgorzata Dymek

Temat: Acykliczne kolorowanie grafów i metoda kompresji entropii

Opis: Przedstawię zagadnienie acyklicznego kolorowania grafów oraz metodę kompresji entropii. Pokażę, jak może być użyta przy dowodzeniu ograniczoności acyklicznej liczby chromatycznej, poprzez przedstawienie dowodów dwóch takich ograniczeń dla pewnych rodzin grafów.

Prezentacja

 

13 V 2021

Prelegent: Tomasz Homoncik

Temat: Problem 4-ścieżkowego pokrycia wierzchołkowego

Opis: Podczas referatu przedstawię algorytm rozwiązujący problem 4-ścieżkowego pokrycia wierzchołkowego oraz omówię jego złożoność parametryczną.

 

6 V 2021

Prelegent: Mikołaj Kondratek

Temat: Grafy "wieżowe"

Opis: Podczas seminarium przedstawię pewne własności symplicjalnych grafów "wieżowych" (grafów nie-atakujących się wież na wielowymiarowej szachownicy).
W szczególności przyjrzę się zbiorom wierzchołków dominujących i niezależnych.
Rozważę również niektóre własności cyklicznych symplicjalnych grafów "wieżowych".

Prezentacja

 

29 IV 2021

Prelegent: Jakub Zygadło

Temat: Wprowadzenie do złożoności parametrycznej

Opis: W referacie omówię podstawy złożoności parametrycznej, która stanowi próbę dokładniejszej analizy problemów trudnych obliczeniowo - w szczególności w niektórych przypadkach metoda ta odpowiada na pytanie, kiedy problemy trudne mogą być uznane za możliwe do efektywnego rozwiązania i "z czego wynika" ich trudność. Złożoność algorytmu rozwiązującego dany problem jest  tutaj podawana jako funkcja zależna nie tylko od rozmiaru danych wejściowych, ale także od wartości pewnego parametru. Przedstawię kilka klasycznych problemów uznawanych za trudne wraz z ich "naturalnymi" parametrami oraz przykłady najczęściej stosowanych technik (przeszukiwanie drzewa, kernelizacja).

 

22 IV 2021

Prelegent: Maciej Brzeski

Temat: Metody kernelowe na grafach

Opis: Wprowadzę w temat metod kernelowych na grafach na podstawie pracy S.V.N. Vishwanathan i in. - "Graph Kernels". Pokażę ich własności, zastosowanie oraz najpopularniejsze kernele. Następnie skupię się na kernelu: "random walk" - pokażę jak poprzez redukcję do równania Sylvestera policzyć go efektywnie, oraz jego związki z innymi kernelami.

Prezentacja

 

15 IV 2021

Prelegent: Jakub Ruszil

Temat: Metody algebry liniowej w synchronizacji automatów

Opis: Referat na podstawie pracy B. Steinberga "The Černý conjecture for one-cluster automata with prime length cycle". Omówię sposoby aplikacji metod algebry liniowej w teorii synchronizacji automatów. W pracy tej zawary jest dowód hipotezy Cerny'ego dla automatów jednoklastrowych z długością cyklu będącą liczba pierwszą.

 

8 IV 2021

Prelegent: Tomasz Homoncik

Temat: Algorytm online wyznaczający 3-ścieżkowe pokrycie wierzchołkowe grafu

Opis: Zaprezentuję algorytm online wyznaczający 3-ścieżkowe pokrycie wierzchołkowe.
Następnie pokażę, że współczynnik konkurencyjności tego algorytmu jest równy co najwyżej stopniowi zadanego grafu.
 
 

25 III 2021

Prelegent: Małgorzata Dymek

Temat: Wielomianowy algorytm wyznaczania morfizmu dla podanego punktu stałego

Opis: Słowo skończone jest punktem stałym pewnego morfizmu niebędącego identycznością, jeśli nie zmienia się pod wpływem jego działania (h(w) = w). Czy mając dane słowo możemy stwierdzić, że jest ono punktem stałym jakiegoś nietrywialnego morfizmu? Przedstawione zostaną pojęcia związane z punktami stałymi, ich konstrukcją i charakterystyką budowy, a także wielomianowy algorytm, który nie tylko odpowiada na powyższe pytanie, lecz również konstruuje odpowiedni morfizm.

Prezentacja

 

18 III 2021

Prelegent: Mikołaj Kondratek

Temat: Rikudo jest NP-zupełne

Rikudo to gra polegająca na znalezieniu ścieżki Hamiltona w grafie zbudowanym na komórkach hexagonalnej siatki. Przybliżę problem cyklów Hamiltona w grafach zbudowanych na krawędziach hexagonalnej siatki. Stosując odpowiednie redukcje pokażę, że gra jest NP-zupełna. Rozpatrzę również trudność łamigłówki dla zadanych już wartości o szczególnych postaciach.

Prezentacja

 

11 III 2021

Prelegent: Eryk Lipka

Temat: Złożoność Liego

W ramach referatu wprowadzimy pojęcie złożoności Liego dla nieskończonych słów nad skończonym alfabetem; jest to kolejny sposób opisywania ilości różnych skończonych czynników danego słowa. Pojęcie to posiada pewną interpretację algebraiczną, przez którą zostało nazwane tak a nie inaczej. Przy pomocy tego narzędzia udowodnimy kilka faktów o słowach, których złożoność (factor complexity) jest liniowa. Referat bazowany na niedawnej pracy Bell, Shallit "Lie complexity of words".

 

 

Semestr zimowy 2020/21

28 I 2021

Prelegent: Adam Roman

Temat: Data Flow Analysis

Omówię podstawowe zagadnienia związane z analizą przepływu danych, pokażę historyczny rozwój technik tej analizy związanej z wyznaczaniem osiągalności bądź żywotności zmiennych w kodzie oraz przedyskutuję kwestie zastosowania DFA do pomiaru i konstrukcji metryk przepływu danych; omówię w szczególności metrykę dep-degree i jej ciekawe własności.

 

21 I 2021

Prelegent: Sławomir Bakalarski

Temat: Dywizory na grafach - kontynuacja

 

14 I 2021

Prelegent: Mateusz Piątkowski

Temat: Krzywe eliptyczne w kryptografii - kontynuacja

Prelegent: Sławomir Bakalarski

Temat: Dywizory na grafach

Celem referatu jest zaznajomienie słuchaczy z teorią dywizorów na grafach. Referat będzie miał charakter czysto kombinatoryczny, żadna wcześniejsza wiedza z geometrii algebraicznej nie jest wymagana. Oprócz podstawowych pojęć omówimy m.in. twierdzenie Riemanna - Rocha dla grafów (udowodnione w 2007 przez Bakera i Norine'a), a także pokażemy jego wykorzystanie do rozwiązania problemu strategii wygrywającej w tzw. "chip - firing game". W drugiej części referatu omówimy obliczeniowe wyznaczanie grupy Picarda grafu (oraz jego jakobianu). W części trzeciej przejdziemy zaś do prezentacji twierdzenia Riemanna-Hurwitza w wersji grafowej (również udowodnionego przez wspomnianych wyżej autorów). Referat na podstawie wybranych pozycji z literatury, w szczególności prac Bakera i Norine'a.

Link do spotkania

 

7 I 2021

Prelegent: Mateusz Piątkowski

Temat: Krzywe eliptyczne w kryptografii

Na najbliższym spotkaniu zajmiemy się tematyką krzywych eliptycznych w kryptografii, a w szczególności zagadnieniu skręconych krzywych Edwardsa. Ponadto, będziemy porównywać wykorzystanie tradycyjnych krzywych Weierstrassa ze skręconymi krzywymi na przykładzie algorytmu faktoryzacji (Lenstry) w celu obserwacji optymalizacji czasu. Dla niewtajemniczonych - zrobimy odpowiednie wprowadzenie w meritum (ciała Galois + podstawy konstrukcji krzywych na ciałach Galois).

Link do spotkania

 

10 XII 2020

Prelegent: Tomasz Homoncik

Temat: Hunters and Rabbits

Opis: Przedstawię grę Hunters and Rabbits (wariant gry Cops and Robbers).
Omówię przypadek gry toczonej na hiperkostce oraz dla grafów z własnością zagnieźdżania izoperymetrycznego. Na koniec skupię się na wariancie gry, w którym królik nie jest zmuszony do ruchu pomiędzy strzałami.

Link do spotkania

 

 

3 XII 2020

Prelegent: Adam Ćwiertnia

Temat: Wykładnicze polepszenie wartości dolnych granic dla liczb Ramsey'a

Opis: Przedstawiona zostanie historia kolejnych poprawek dla wartości granic dolnych i górnych liczb Ramsey'a, między innymi probalistyczna metoda Erdős'a. Następnie pokazane zostanie wykładnicze polepszenie dla dotychczas znanych wartości dolnych z tych granic, przy trzy i więcej kolorowań grafów.
 

Link do spotkania

 

26 XI 2020

Prelegent: Eryk Lipka

Temat: Ograniczenie górne w problemie Grahama- Rothschilda

Opis: Na początku referatu wprowadzimy tematykę Teorii Ramseya oraz klasyczne problemy tej teorii. W drugiej części rozważymy zagadnienie znane jako problem Grahama-Rothschilda. Budujemy klikę, której wierzchołki są wierzchołkami kostki n-wymiarowej, a następnie dwukolorujemy jej krawędzie. Należy znaleźć najmniejsze takie n, że niezależnie od kolorowania w grafie tym można znaleźć cztery punkty leżące na jednej płaszczyźnie tworzące monochromatyczną klikę. Początkowe oszacowania na ten wymiar dają się w sposób zwarty opisać dopiero przy użyciu funkcji typu Ackermana, natomiast my zaprezentujemy najnowsze wyniki które dają ograniczenie przy użyciu zaledwie tetracji.

Link do spotkania | Prezentacja

 

19 XI 2020

Prelegent: Edward Szczypka

Temat: Metody kompresji w matematyce dyskretnej i algorytmice (cz. II)

Opis: Przedstawiona zostanie idea wykorzystania mocno niedocenianej metody kompresji w różnych problemach z matematyki dyskretnej, języków formalnych czy algorytmiki. Jako jedno z rozwinięć, tej metody można traktować tzw. złożoność Kołmogorowa, dzięki której rozwiązano szereg problemów, atakowanych bez powodzenia od wielu lat.

Link do spotkania

 

12 XI 2020

Prelegent: Edward Szczypka

Temat: Metody kompresji w matematyce dyskretnej i algorytmice

Opis: Przedstawiona zostanie idea wykorzystania mocno niedocenianej metody kompresji w różnych problemach z matematyki dyskretnej, języków formalnych czy algorytmiki. Jako jedno z rozwinięć, tej metody można traktować tzw. złożoność Kołmogorowa, dzięki której rozwiązano szereg problemów, atakowanych bez powodzenia od wielu lat.

Link do spotkania

 

5 XI 2020

Prelegent: Maciej Brzeski

Temat: Odległość edycyjna dla drzew

Opis: O podobieństwie dwóch grafów można myśleć bardzo różnie - najczęściej rozważane jest podobieństwo oparte na strukturze bądź etykietach. Na seminarium wprowadzę problem "graph matching" na grafach etykietowanych, gdzie istotne jest wyznaczenie odpowiadających sobie wierzchołków. Omówię pracę wprowadzającą pojęcie odległości edycyjnej dla drzew oraz algorytm znajdujący minimalną odległość, a następnie jej związek z powyższym problemem. Na koniec krótko omówię trudności przy rozszerzeniu powyższego problemu na szerszą klasę grafów.

Link do spotkania  |  Prezentacja

 

29 X 2020

Prelegent: Mikołaj Kondratek

Temat: Współczynniki w nieskończonym produkcie (1-x^(F_n))

Opis: Przedstawię dowód faktu, że współczynniki w nieskończonym produkcie (1-x^(F_n)) wynoszą zawsze -1, 0 albo 1 (gdzie F_n to n-ty wyraz ciągu Fibonacciego).
Celem wprowadzenia zaprezentuję zostanie liczbowy system Fibonacciego.
Dowód opiera się o 4-stanowy deterministyczny automat skończony.
Poruszę zagadnienie reprezentacji liniowej powiązanej z automatem.
Finalnie przedłożę automat obliczający współczynnik przy x^F_n.

Link do spotkania | Prezentacja

 

22 X 2020

Prelegent: Artur Polański

Temat: Wykrywanie pojedynczej wady w DFA

Opis: Omówienie znanego wyniku dotyczącego algorytmu heurestycznego wykrywania pojedynczej wady w deterministycznym automacie skończonym wraz z możliwościami ulepszenia go oraz występującymi problemami.

 

15 X 2020

Prelegent: Jakub Ruszil

Temat: Synchronizacja automatów o częściowej funkcji przejść

Opis: Automat nazywamy synchronizującym, gdy istnieje słowo, które każdy stan tego automatu przeprowadza w jeden ustalony stan. W referacie przedstawię wyniki dotyczące synchronizacji automatów o częściowej funkcji przejść, w szczególności opiszę konstrukcję nieskończonej rodziny automatów, dla której słowa synchronizujące mają długość wykładniczą w zależności od liczby stanów.

Dydaktyka

Pracownicy Zakładu Inżynierii Oprogramowania prowadzą następujące wykłady na kierunku informatyka:

Podstawy teoretyczne i matematyczne inżynierii oprogramowania

  • matematyka dyskretna
  • kryptografia
  • kody i kaflowania
  • teoria języków i automatów

Inżynieria systemów i inżynieria oprogramowania

  • systemy operacyjne
  • testowanie oprogramowania
  • programowanie funkcyjne
  • zaawansowane programowanie funkcyjne
  • zarządzanie projektami IT

Prace licencjackie, magisterskie i doktorskie

Zakład oferuje możliwość pisania prac licencjackich, magisterskich i doktorskich w zakresie:

  • szeroko pojętej inżynierii oprogramowania (projektowanie i implementacja systemów)
  • teorii kodów
  • matematyki dyskretnej (np. teoria grafów)
  • teorii języków formalnych (np. synchronizacja automatów)
  • testowania oprogramowania (np. testowanie oparte na modelu, testowanie mutacyjne)
  • inżynierii jakości (np. predykcja defektów, metryki oprogramowania, pomiar jakości)

Osoby zainteresowane pisaniem prac z w/w obszarów proszone są o kontakt z pracownikami Zakładu.

Zobacz również Zobacz również