Wydział Matematyki i Informatyki (WMiI)/Faculty of Mathematics and Computer Science
Permanent URI for this community
Browse
Browsing Wydział Matematyki i Informatyki (WMiI)/Faculty of Mathematics and Computer Science by Issue Date
Now showing 1 - 20 of 120
Results Per Page
Sort Options
Item Every infinite-dimensional non-archimedean Frechet space has an orthogonal basic sequence(Royal Netherlands Academy of Arts and Sciences, 2000-09) Śliwa, WiesławIt is proved that any infinite-dimensional non-archimedean metrizable locally convex space has an orthogonal basic sequence.Item Examples of non-archimedean nuclear Frechet spaces without a Schauder basis(Royal Netherlands Academy of Arts and Sciences, 2000-12) Śliwa, WiesławWe solve the problem of the existence of a Schauder basis in non-archimedean Frechet spaces of countable type. Using examples of real nuclear Frechet spaces without a Schauder basis we construct examples of non-archimedean nuclear Frechet spaces without a Schauder basis (even without the bounded approximation property).Item On the stability of orthogonal bases in non-archimedean metrizable locally convex spaces(The Belgian Mathematical Society, 2001) Śliwa, WiesławIt is proved that an orthogonal basis in a non-archimedean metrizable locally convex space E (in particular, a Schauder basis in a non-archimedean Frechet space E) is stable if and only if there is a continuous norm on E. Many others results are also obtained.Item Closed subspaces without Schauder bases in non-archimedean Frechet spaces(Royal Netherlands Academy of Arts and Sciences, 2001-06) Śliwa, WiesławLet E be an infinite-dimensional non-archimedean Frechet space which is not isomorphic to any of the following spaces: $c_0,c_0 x K^N,K^N$. It is proved that E contains a closed subspace without a Schauder basis (even without a strongly finite-dimensional Schauder decomposition). Conversely, it is shown that any closed subspace of $c_0 x K^N$ has a Schauder basis.Item On closed subspaces with Schauder bases in non-archimedean Frechet spaces(Royal Netherlands Academy of Arts and Sciences, 2001-12) Śliwa, WiesławThe main purpose of this paper is to prove that a non-archimedean Frechet space of countable type is normable (respectively nuclear; reflexive; a Monte1 space) if and only if any its closed subspace with a Schauder basis is normable (respectively nuclear; reflexive; a Monte1 space). It is also shown that any Schauder basis in a non-normable non-archimedean Frechet space has a block basic sequence whose closed linear span is nuclear. It follows that any non-normable non-archimedean Frechet space contains an infinite-dimensional nuclear closed subspace with a Schauder basis. Moreover, it is proved that a non-archimedean Frechet space E with a Schauder basis contains an infinite-dimensional complemented nuclear closed subspace with a Schauder basis if and only if any Schauder basis in E has a subsequence whose closed linear span is nuclear.Item On the quasi-equivalence of orthogonal bases in non-archimedean metrizable locally convex spaces(The Belgian Mathematical Society, 2002) Śliwa, WiesławWe prove that any non-archimedean metrizable locally convex space E with a regular orthogonal basis has the quasi-equivalence property, i.e. any two orthogonal bases in E are quasi-equivalent. In particular, the power series spaces, the most known and important examples of non-archimedean nuclear Frechet spaces, have the quasi-equivalence property. We also show that the Frechet spaces: K^N, c_0xK^N, c_0^N have the quasi-equivalence property.Item On the selection of basic orthogonal sequences in non-archimedean metrizable locally convex spaces(The Belgian Mathematical Society, 2002) Śliwa, WiesławOur main result follows that any infinite-dimensional sub-space F of a non-archimedean metrizable locally convex space E with an or- thogonal basis (e_n) contains a basic orthogonal sequence equivalent to a block basic orthogonal sequence relative to (e_n). Hence any infinite-dimensional non-archimedean metrizable locally convex space F has a basic orthogonal sequence equivalent to a block basic orthogonal sequence relative to an orthogonal basis in c_0^N.Item On Universal Schauder Bases in Non-Archimedean Frechet Spaces(Canadian Mathematical Society, 2004) Śliwa, WiesławWe prove that there exists a non-archimedean Frechet space U with a basis $(u_n)$ such that any basis $(x_n)$ in a non-archimedean Frechet space X is equivalent to a subbasis $(u_k_n)$ of $(u_n)$. Then any non-archimedean Frechet space with a basis is isomorphic to a complemented subspace of U. Next we prove that there is no nuclear non-archimedean Frechet space H with a basis $(h_n)$ such that any basis $(y_n)$ in a nuclear non-archimedean Frechet space Y is equivalent to a subbasis $(h_k_n)$ of $(h_n)$.Item On Quotients of Non-Archimedean Kothe Spaces(Canadian Mathematical Society, 2007) Śliwa, WiesławWe show that there exists a non-archimedean Frechet-Montel space W with a basis and with a continuous norm such that any non-archimedean Frechet space of countable type is isomorphic to a quotient of W. We also prove that any non-archimedean nuclear Frechet space is isomorphic to a quotient of some non-archimedean nuclear Frechet space with a basis and with a continuous norm.Item On metrizability of compactoid sets in non-archimedean locally convex spaces(2008) Kakol, Jerzy; Śliwa, WiesławIn 2003 N. De Grande-De Kimpe, J. Kakol and C.Perez-Garcia using t-frames and some machinery concerning tensor products proved that compactoid sets in (LM)-spaces are metrizable. In this presentation we show a similar result for locally convex spaces with a L-base. This extends the first mentioned result since every (LM)-space has a L-base. We show that any compactoid subset of a non-archimedean locally convex space E is metrizable if and only if the dual of E with the topology of the uniform convergence on compactoid subsets of E is of countable type.Item The Invariant Subspace Problem for Non-Archimedean Banach Spaces(Canadian Mathematical Society, 2008) Śliwa, WiesławIt is proved that every infinite-dimensional non-archimedean Banach space of countable type admits a linear continuous operator without a non-trivial closed invariant subspace. This solves a problem stated by A. C. M. van Rooij and W. H. Schikhof in 1992.Item An explicit example concernig the invariant subspace problem for Banach spaces(Rocky Mountain Mathematics Consortium, 2010-04) Śliwa, WiesławWe simplify the negative solution to the invariant subspace problem for Banach spaces. Developing the ideas of Read we give an explicit example of a continuous linear operator on the Banach space of all absolute summable scalar sequences without nontrivial closed invariant subspacesItem Losowe grafy przecięć. Modelowanie sieci i ich analiza(2010-05-28T11:04:59Z) Rybarczyk-Krzywdzińska, Katarzyna; Jaworski, Jerzy. PromotorPrzedmiotem rozprawy jest badanie sieci przy pomocy ich teoretycznych modeli grafowych. W tym celu analizowane były interesujące własności grafu losowego zwanego losowym grafem przecięć. Pod kątem analizy sieci złożonych (np. sieci stron WWW i sieci internetowych) badany był stopień wierzchołków. Zostały też otrzymane wyniki dotyczące współczynnika skupienia i związanego z nim rozkładu liczby klik w grafie. Badania podjęte w rozprawie dotyczyły także własności związanych ze spójnością, przejściem fazowym, długością średnicy i liczbą wierzchołków izolowanych w losowym grafie przecięć. Wyniki te przydatne są do analizy struktury sieci sensorowych z losową predystrybucją kluczy.Item On non-archimedean Frechet spaces with nuclear Kothe spaces(The American Mathematical Society, 2010-06) Śliwa, WiesławAssume that K is a complete non-archimedean valued field. We prove that every Frechet-Montel space over K which is not of finite type has a nuclear Kothe quotient.Item Arytmetyka Grupy Mordella-Weila na rozmaitości abelowej nad ciałem skończenie generowanym nad Q(2010-06-07T08:48:40Z) Rzonsowski, Piotr; Banaszak, Grzegorz. PromotorNiniejsza rozprawa jest poświęcona rozwiązaniu dwóch problemów. Pierwszym zagadnieniem jakie jest rozważany w rozprawie jest problem nośnika. Jako pierwszy sformułował go P. Erdös w następujący sposób: Załóżmy, że dla pewnych liczb całkowitych x, y następujący warunek jest spełniony:Supp(xn − 1) implikuje Supp(yn − 1),dla wszystkich liczb naturalnych n. Czy z tego wynika, że x = y.Problem ten został rozwiązany przez C. Corrales-Rodrigáñez i R. Schoof. Następnie problem ten został uogólniony na rozmaitości abelowe nad ciałem liczbowym i był rozwiązany dla szczególnych klas rozmaitości abelowych przez Banaszaka, Gajdę, Krasonia, Khare, Prasada i innych.W swojej rozprawie rozszerzam ten wynik dla abelowych rozmaitości nad ciałem skończenie generowanym nad Q.Drugi problem dotyczy liniowej zależności punktów na rozmaitości abelowej. Pytanie to sformułował W. Gajda w 2002 r. w następujący sposób:Czy dla rozmaitości abelowej A i jej podgrupy G następujące warunki są równoważne:· P należy do podgrupy G;· rv(P) należy do rv(G), dla prawie wszystkich v z pierścienia OFProblematyka ta była rozważana w przeciągu kilku następnych lat. Jednakże wszystkie wyniki uzyskiwane w tych pracach były dla rozmaitości abelowych nad ciałem liczbowym. W rozprawie rozszerzam ten problem na ciała skończenie generowane nad Q.Item Zagadnienia algorytmiczne dla gramatyk pregrupowych(2010-06-11T07:57:10Z) Moroz, Katarzyna; Buszkowski, Wojciech. PromotorW pracy rozważamy zagadnienia algorytmiczne dla gramatyk pregrupowych w ich podstawowej formie oraz dla pewnych rozszerzeń gramatyk pregrupowych. Gramatyki pregrupowe zostały wprowadzone przez Lambeka w 1999 jako nowe, algebraiczne narzędzie analizy syntaktycznej języków naturalnych. Formalizm pregrup należy do tradycji gramatyk kategorialnych (gramatyk typów). Każdemu słowu przypisuję się jeden lub więcej typów. Typy odpowiadają pewnym własnościom słów. Wszystkie informacje lingwistyczne zawarte są w leksykonie. Reguły są sekwentami dowodliwymi w pewnej logice typów. Gramatyki pregrupowe zostały zastosowane do wielu różnorodnych języków naturalnych. Najpierw rozważamy równoważność gramatyk pregrupowych i bezkontekstowych. Proponujemy bezpośrednią wielomianową konstrukcję gramatyki bezkontekstowej oraz automatu ze stosem równoważnych danej gramatyce pregrupowej. Następnie podajemy wielomianowy dynamiczny algorytm parsingu dla gramatyk pregrupowych i gramatyk pregrupowych z promocjami. Następnie pokazujemy, że problem promocji dla gramatyk pregrupowych z promocjami z 1 jest rozwiązywalny w czasie wielomianowym oraz podajemy algorytm parsingu dla gramatyk pregrupowych z promocjami z 1. Na zakończenie przedstawiamy implementację w języku Java algorytmu parsingu dla gramatyk pregrupowych i prezentujemy leksykon typów dla języka angielskiego (oparty na pracy J. Lambeka).Item Algorytmy multikolorowania grafów w modelu rozproszonym(2010-06-11T09:02:26Z) Witkowski, Rafał; Karoński, Michał. PromotorPraca traktuje o problemie multikolorowania grafów, motywacji do rozpatrywania tego zagadnienia oraz jego zastosowaniach w metodach przydziału częstotliwości w sieciach komórkowych. Powstała na podstawie kilku prac, w których zostały przedstawione nowe algorytmy multikolorowania grafów lub lepsze oszacowania liczby multichromatycznej.Pierwszy rozdział zawiera genezę problemu. Zostały w nim opisane motywacje do rozpatrywania problemu multikolorowania grafów oraz to, jak algorytmy rozwiązujące ten problem znalazły zastosowanie w zagadnieniu przydziału częstotliwości w sieciach komórkowych, bardzo silnie rozwijającym się na przełomie tysiącleci. Drugi rozdział zawiera definicję modelu obliczeń dla algorytmów wykorzystywanych w przydziale częstotliwości w sieciach komórkowych, a więc także multikolorowania grafów heksagonalnych. Przedstawione są w nim algorytmy multikolorowania we wszystkich możliwych modelach k-lokalnych.Trzeci rozdział zawiera algorytmy multikolorowania grafów heksagonalnych bez trójkątów. Przedstawione są w nim algorytmy liniowego multikolorowania takich grafów oraz częściowe rozwiązanie najważniejszego problemu otwartego w dziedzinie multikolorowania grafów heksagonalnych, hipotezy McDiarmida-Reeda.Item Metody Algorytmiczne w Badaniach Siły Nieregularności Grafów(2010-06-11T12:13:03Z) Kalkowski, Maciej; Karoński, Michał. PromotorCelem rozprawy jest przedstawienie nowych metod rozwiązywania problemów globalnej i lokalnej siły nieregularności grafów. Powyższe dwa zagadnienia są rozpatrzone zarówno dla grafów ważonych, jak i totalnie ważonych. Wszystkie przedstawione metody i dowody mają charakter algorytmów wyznaczających wartości funkcji ważących. Rozdział drugi składa się z dwóch części i dotyczy lokalnego rozróżniania wierzchołków. W pierwszej, zagadnienie omówione jest dla totalnego ważenia. Wprowadzone są dwa twierdzenia, dowodzące, że istnieją lokalnie nieregularne 5-totalne-ważenie oraz 3-totalne-ważenie. W drugiej części rozdziału rozważony jest problem rozróżniania wierzchołków dla ważenia krawędzi nawiązujący do hipotezy 1-2-3. Wprowadzone są trzy nowe metody rozwiązania problemu, które wykazują, że możliwe są konstrukcje lokalnie nieregularnych 10-ważenia, 6-ważenia i 5-ważenia grafu. Rozdział trzeci dotyczy globalnego rozróżniania wierzchołków i również składa się z dwóch części. W pierwszej, zagadnienie rozpatrzone jest dla ważenia krawędzi grafu. Opisana jest metoda konstrukcji globalnie nieregularnego 6 ⌈n/δ⌉ -ważenia grafu. W drugiej części rozdziału omówione jest globalne rozróżnianie wierzchołków dla totalnego ważenia grafów. Wykazana jest konstrukcja globalnie nieregularnego (3⌈n/δ ⌉+1)-totalnego-ważenia. W ostatnim rozdziale przedstawione są pokrewne problemy rozróżniania wierzchołków.Item Rozproszone algorytmy aproksymacyjne dla grafów dyskowych(2010-06-11T12:33:49Z) Krzywdziński, Krzysztof; Karoński, Michał. PromotorCelem rozprawy jest przedstawienie szybkich algorytmów aproksymacyjnych rozwiązujących w modelu rozproszonym niektóre z istotnych ze względu na zastosowania problemów. Rozważania skupiają się na zagadnieniach związanych z sieciami zdecentralizowanymi, w których komunikacja odbywa się drogą radiową. Ich teoretycznym modelem są jednostkowe grafy dyskowe, w których wierzchołki są punktami na płaszczyźnie a połączenia powstają między wierzchołkami w odległości co najwyżej 1. Rozważania dotyczyć będą trzech istotnych klas problemów związanych z działaniem i strukturą sieci radiowych. Pierwszą z nich są zagadnienia związane ze znalezieniem optymalnej struktury komunikacyjnej i z bezkolizyjnym rozsyłaniem informacji. Przedstawiony jest algorytm konstruujący aproksymację minimalnego drzewa rozpinającego, czyli strukturę minimalizującą sumaryczny koszt rozesłania informacji w całej sieci. Kolejnym z problemów jest konstrukcja podziału grafu na klastry (fragmenty). Rozważamy także zagadnienie kolorowania i związany z nim problem przydziału częstotliwości w sieciach radiowych.Item Rozproszone algorytmy aproksymacyjne w analizie własności grafowych(2010-06-14T09:53:39Z) Wawrzyniak, Wojciech; Karoński, Michał. PromotorPrzez ostatnie kilkanaście lat zauważyć można znaczący wzrost zainteresowania algorytmami rozproszonymi. Powodem jest zastosowanie ich w wielu praktycznych zagadnieniach informatyki. Celem rozprawy doktorskiej jest przedstawienie i omówienie deterministycznych rozproszonych algorytmów aproksymacyjnych rozwiązujących podstawowe problemy grafowe, takie jak konstrukcja: minimalnego zbioru dominującego, największego zbioru niezależnego, minimalnego pokrycia wierzchołkowego, największego skojarzenia oraz pakowania grafów. Modelem obliczeń przeze mnie rozważanym jest tzw. model Local. W Rozdziale 2 opisany jest algorytm rozwiązujący problem pakowania grafu G=(V,E) w planarnym grafie H. Zwracane rozwiązanie jest dowolnie dobrą aproksymacją problemu, a złożoność czasowa algorytmu wynosi O(logk|V|). Z praktycznego punktu widzenia zastosowanie znajdują również algorytmy działające w znacząco krótszym czasie, jednak o dużo gorszym współczynniku aproksymacji. Podejście to przedstawiono w Rozdziale 3, gdzie opisane zostały algorytmy działające w czasie O(1). Konstruują one (2 + ε)-aproksymację minimalnego pokrycia wierzchołkowego, w grafach o ograniczonym stopniu, o ograniczonej lesistości. W Rozdziale 4 opisane zostały algorytmy działające w czasie O(log*n). Zwracają one przybliżone rozwiązanie problemów: minimalnego zbioru dominującego, największego skojarzenia oraz największego ważonego zbioru niezależnego w grafach planarnych. Współczynnik aproksymacji wynosi (1 ± ε). Ponadto z twierdzenia udowodnionego w ostatnim Rozdziale 5 wynika, że algorytmy te są optymalne.