Formal power series: Theory and applications 1000-2M26FPS
1. Klasy szeregów potęgowych w zmiennych przemiennych (np. wymierne, algebraiczne, D-skończone, CDA, różniczkowo-algebraiczne itd.). Własności domknięcia i problem zerowości. Związek z odpowiadającymi klasami ciągów liczbowych (np. LRS).
2. Twierdzenie Chomsky'ego-Schützenbergera (generowanie szeregów potęgowych jednoznacznych gramatyk bezkontekstowych są algebraiczne)
3. Zastosowania do liczenia oznaczonych i nieoznaczonych w kombinatoryce.
4. Twierdzenie Christola (algebraiczne szeregi potęgowe = ciągi automatyczne, w dodatnich charakterystykach)
5. Rozwiązywalność w szeregach potęgowych układów równań algebraicznych i różniczkowo-algebraicznych
6. Klasy szeregów o zmiennych nieprzemiennych (wymiernych, algebraicznych itp.) i odpowiadające im modele automatów (automaty ważone, ważone gramatyki bezkontekstowe itp.)
7. Uniwersalność jednoznacznych automatów Parikha poprzez D-skończone szeregi potęgowe
8. Zerowość ważonych wielotaśmowych automatów skończonych poprzez pola skośne
9. Szereg Chen-Fliessa i twierdzenie Fliessa w teorii sterowania
10. Szereg o skończonej randze Hankela. Ranga Liego.
Kierunek podstawowy MISMaP
Koordynatorzy przedmiotu
Rodzaj przedmiotu
Tryb prowadzenia
Efekty kształcenia
Wiedza: absolwent zna i rozumie
• w pogłębionym stopniu - wiedzę z działów matematyki niezbędnych do studiowania informatyki (K_W01)
• w pogłębionym stopniu - rolę i znaczenie konstrukcji rozumowań matematycznych (K_W02)
Umiejętności: absolwent potrafi
• konstruować rozumowania matematyczne (K_U01)
• wyrażać problemy obliczeniowe w języku matematyki (K_U02)
• analizować pojęcia sformalizowane w wybranych systemach logicznych o znaczeniu informatycznym, tworzyć w nich formalizacje zadanych pojęć bądź też dowodzić niemożności takiej formalizacji (K_U07)
Kryteria oceniania
Ocena na podstawie prac domowych wykonywanych w trakcie kursu oraz końcowego egzaminu ustnego.
Doktoranci: zadanie badawcze 50%, egzamin 50%.
Literatura
Slajdy z wykładu oraz wybrane rozdziały następujących podręczników:
• Berstel, Reutenauer: “Noncommutative series with applications”
• Gray: “Formal power series methods in nonlinear control theory”
• Salomaa, Soittola: “Automata-theoretic aspects of formal power series”
• Kuich, Salomaa: “Semirings, automata, languages”
• Sakarovitch: “Elements of automata theory”
• Kauers, Paule: “The concrete tetrahedron”
• Kauers: “D-finite functions”
• Petkovsek, Wilf, Zeilberger: “A=B”
• Wilf: “Generatingfunctionology”
• Stanley: “Enumerative combinatorics”
• Bergeron, Labelle, Leroux: “Combinatorial species and treelike structures”
Więcej informacji
Więcej informacji o poziomie przedmiotu, roku studiów (i/lub semestrze) w którym się odbywa, o rodzaju i liczbie godzin zajęć - szukaj w planach studiów odpowiednich programów. Ten przedmiot jest związany z programami: