Testowanie własności

Speaker(s)

Krzysztof Onak

Affiliation

Uniwersytet Warszawski

Date

Jan. 5, 2006, 12:15 p.m.

Room

room 5870

Seminar

Seminar Algorithms

---

W sytuacji, gdy dysponujemy ograniczoną ilością czasu, może nie być możliwe sprawdzenie, czy dany obiekt (kombinatoryczny) posiada, pewną ustaloną własność. Tym niemniej nie jesteśmy całkowicie bezradni. Okazuje się, że w wielu przypadkach, odczytując jedynie niewielki fragment danych opisujących obiekt, możemy z dużym prawdopodobieństwem rozróżnić obiekty posiadające zadaną własność od tych, które należałoby znacznie zmodyfikować, aby tę własność posiadły. Takie podejście nazywa się zwyczajowo "testowaniem własności" (ang. property testing). Skupię się na przykładach związanych z testowaniem wymiarowości danych, ale nie zapomnę o hołubionych na Uniwersytecie Warszawskim grafach i zaprezentuję przykładowe, bardzo ogólne twierdzenia dotyczące testowania własności grafowych. Testowanie własności znajduje zastosowania w obszarach takich jak algorytmy aproksymacyjne, teoria kodów, uczenie maszynowe. Przy okazji opowiem również, jak wygląda, z krótkiej półrocznej perspektywy czasu, studiowanie na MIT, czym tam się ludzie zajmują, a także z przyjemnością odpowiem na wszelkie inne pytania.

---