Uniwersytet Warszawski - Centralny System Uwierzytelniania
Strona główna

Wnioskowanie i obliczenia aproksymacyjne

Informacje ogólne

Kod przedmiotu: 1000-1M00WA
Kod Erasmus / ISCED: 11.414 Kod klasyfikacyjny przedmiotu składa się z trzech do pięciu cyfr, przy czym trzy pierwsze oznaczają klasyfikację dziedziny wg. Listy kodów dziedzin obowiązującej w programie Socrates/Erasmus, czwarta (dotąd na ogół 0) – ewentualne uszczegółowienie informacji o dyscyplinie, piąta – stopień zaawansowania przedmiotu ustalony na podstawie roku studiów, dla którego przedmiot jest przeznaczony. / (0613) Tworzenie i analiza oprogramowania i aplikacji Kod ISCED - Międzynarodowa Standardowa Klasyfikacja Kształcenia (International Standard Classification of Education) została opracowana przez UNESCO.
Nazwa przedmiotu: Wnioskowanie i obliczenia aproksymacyjne
Jednostka: Wydział Matematyki, Informatyki i Mechaniki
Grupy: Przedmioty monograficzne dla matematyki 2 stopnia
Przedmioty obieralne na studiach drugiego stopnia na kierunku bioinformatyka
Punkty ECTS i inne: 6.00 Podstawowe informacje o zasadach przyporządkowania punktów ECTS:
  • roczny wymiar godzinowy nakładu pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się dla danego etapu studiów wynosi 1500-1800 h, co odpowiada 60 ECTS;
  • tygodniowy wymiar godzinowy nakładu pracy studenta wynosi 45 h;
  • 1 punkt ECTS odpowiada 25-30 godzinom pracy studenta potrzebnej do osiągnięcia zakładanych efektów uczenia się;
  • tygodniowy nakład pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się pozwala uzyskać 1,5 ECTS;
  • nakład pracy potrzebny do zaliczenia przedmiotu, któremu przypisano 3 ECTS, stanowi 10% semestralnego obciążenia studenta.

zobacz reguły punktacji
Język prowadzenia: angielski
Kierunek podstawowy MISMaP:

informatyka
matematyka

Rodzaj przedmiotu:

monograficzne

Tryb prowadzenia:

w sali

Skrócony opis:

Wykład został przygotowany zarówno dla studentów matematyki jak i dla studentów informatyki, interesujących się aspektami teoretycznymi oraz zastosowaniami praktycznymi wnioskowania aproksymacyjnego. Wykład poświęcony jest zagadnieniom i problemom, które w opinii wybitnych matematyków i informatyków należą do centralnych problemów matematyki obecnego stulecia, tak ważnych jak w XX wieku centralnym dla nauki był problem rozszyfrowania genomu ludzkiego. W wykładzie analizowane będą problemy o zasadniczym znaczeniu dla dokonania postępu w licznych zastosowaniach informatyki, w szczególności w wielu interdyscyplinarnych projektach łączących zespoły matematyków, informatyków oraz specjalistów z wielu innych dziedzin (np. neuroscience, bioinformatyka, psychologia, socjologia, ekonomia, modelowanie systemów złożonych). W wykładzie przedstawione zostaną różne teoretyczne i praktyczne aspekty metod aproksymacji pojęć z danych eksperymentalnych i wiedzy dziedzinowej.

Pełny opis:

1. Problematyka wnioskowań aproksymacyjnych i jej związek z różnymi dziedzinami zastosowań takimi jak:

-maszynowe uczenie (ang. machine learning),

-wykrywanie wzorców (ang. pattern recognition),

-eksploracja danych i wykrywanie z nich wiedzy (ang. data mining and knowledge discovery),

-wnioskowanie o wiedzy (ang. reasoning about knowledge),

-przetwarzanie obrazów (ang. image processing).

2. Metody wnioskowania w oparciu o pojęcia nieostre (ang. soft computing).

3. Teoretyczne podstawy maszynowego uczenia: wymiar Vapnika-Czerwonenkisa, związki wnioskowań aproksymacyjnych z wnioskowaniami statystycznymi, rola entropii w indukcyjnym uczeniu się pojęć.

4. Problemy logiczne wnioskowań aproksymacyjnych:

-wnioskowania boolowskie,

-problem SAT i strategie poszukiwania wartościowań spełniających formuły,

-zastosowania,

-wnioskowania niemonotoniczne,

-systemy adaptacyjne,

-rewizja przekonań,

-wnioskowania o wiedzy w systemach rozproszonych,

-problemy negocjacji.

5. Metody algorytmiczne wykrywania praw i schematów wnioskowań aproksymacyjnych z danych:

-metody wykrywania nowych własności,

-metody algorytmiczne wykrywania reguł domniemań (ang. defaultowych) z danych,

-sieci bayesowskie, wykrywanie i reprezentacja zależności aproksymacyjnych, problemy dekompozycji dużych zbiorów danych.

6. Problemy złożoności obliczeniowej wnioskowań aproksymacyjnych:

-oszacowania złożoności wybranych problemów,

-heurystyki ich rozwiązań.

-zasada minimalnego opisu (ang. minimum description length) i związki z teorią złożoności Kołmogorowa,

-złożoność problemów kompresji informacji.

7. Metody oparte o niekonwencjonalne modele obliczeń (w szczególności algorytmy genetyczne i programowanie ewolucyjne, sieci neuronowe, rozwiązania hybrydowe) dla rozwiązywania problemów wnioskowania aproksymacyjnego.

Literatura:

1. T. Baeck: Evolutionary Algorithms in Theory and Practice, Oxford University Press 1996.

2. J. Barwise, J. Seligman: Information flow: The logic of distributed systems, Cambridge University Press 1997.

3. T. Hastie, R. Tibshirani, J. Friedman: The elements of statistical learning. Data mining, inference, and prediction. (2nd edition), Springer 2009.

4. D.S. Hochbaum: Approximation algorithms for NP-hard problems. PWS 1997.

5. A. Skowron: Wnioskowanie aproksymacyjne, notatki do wykładu, 2013.

6. V. Vapnik: Statistical learning theory. Wiley 1998.

Efekty uczenia się:

W zakresie podstaw teoretycznych wnioskowań aproksymacyjnych student:

1. zna podstawowe pojęcia i twierdzenia z teorii uczenia się pojęć (PAC-algorytm, wymiar Vapnika-Chervonenkisa (VC), twierdzenia zwane kamieniami milowymi);

2. zna podstawowe pojęcia i twierdzenia o aproksymacji problemów NP-trudnych (algorytm aproksymacyjny w danym stopniu, schemat aproksymacyjny, przykłady problemów "dobrze" i "źle" aproksymujących się, charakteryzacja klasy NP za pomocą klasy języków rozpoznawalnych przez weryfikatory probabilistyczne , twierdzenia o nieistnieniu schematu aproksymacyjnego dla wybranych problemów); (c) podstawy logiki systemów rozproszonych w teorii przepływu informacji (klasyfikacja, infomorfizm, teoria, logika lokalna, twierdzenia o reprezentacji sieci przez kanał informacyjny oraz sieci logik lokalnych) .

3. umie wyznaczać wymiar VC dla prostych przestrzeni pojęć;

4, umie dowodzić NP-trudności wybranych problemów;

5. umie dowodzić aproksymowalność w stopniu dla wybranych problemów;

6. umie dowodzić NP-trudność istnienia schematów aproksymacyjnych dla wybranych problemów; 7. interpretować pojęcia z systemów decyzyjnych w teorii przepływu informacji;

8. potrafi formułować i dowodzić twierdzenia o reprezentacji w teorii przepływu informacji.

W zakresie wnioskowań aproksymacyjnych dotyczących wybranych zagadnień praktycznych student:

1. zna wybrane metody selekcji i wykrywania nowych cech, metody modelowania obliczeń interakcyjnych, wybrane problemy systemów samoorganizujących się i metody ich rozwiązywania oraz wybrane problemy ewolucji języka komunikacji;

2. umie konstruować heurystyki selekcji cech i zbiorów cech;

3. umie konstruować heurystyki dla poszukiwania nowych cech;

4. umie modelować interakcyjne obliczenia dla rozwiązywania problemów hierarchicznego uczenia się złożonych pojęć nieostrych;

5. potrafi konstruować strategie dla wyznaczania koalicji w wybranych problemach hierarchicznych obliczeń interakcyjnych.

Metody i kryteria oceniania:

Ocena końcowa: 50% - egzamin ustny (25% - materiał wykładu i ćwiczeń, 25% - literatura stanowiąca rozszerzenie wybranej części wykładu), 50% - przygotowanie i wygłoszenie referatu na ćwiczeniach na podstawie wybranych prac.

Zajęcia w cyklu "Semestr zimowy 2023/24" (zakończony)

Okres: 2023-10-01 - 2024-01-28
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Ćwiczenia, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Dominik Ślęzak
Prowadzący grup: Marcin Szczuka, Dominik Ślęzak
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Warszawski.
ul. Banacha 2
02-097 Warszawa
tel: +48 22 55 44 214 https://www.mimuw.edu.pl/
kontakt deklaracja dostępności USOSweb 7.0.3.0-2b06adb1e (2024-03-27)