Skocz do zawartości

Hakken

[Ekspert] Programowanie
 Wyświetl profil  Zobacz jego aktywność

  • Zawartość

    3496

  • Rejestracja

  • Ostatnio

  • Wygrane dni

    5

 Typ zawartości 

Wpisy blogu napisane przez Hakken

  1. Hakken
    Wstęp
    Częstym problemem kombinatorycznym z którym mierzą się uczniowie szkół już nawet gimnazjalnych jest pytanie "na ile sposobów można pokolorować cośtam?". Dzisiaj zajmiemy się problemami tego typu... oraz wieloma innymi, bo teoria którą przedstawię jest bardzo poważna i mocna. Ze względu na to ścisłe podejście do problemu umieszczę na końcu, może uda się uniknąć omdleń.
    Weźmy przykładowy problem którym będziemy się zajmować: mamy naszyjnik, czyli sznureczek na który można nawlekać kolorowe kamyczki. Ile różnych naszyjników można stworzyć jeżeli chcemy nawlec 6 kamyczków, a mamy kamyczki w dwóch kolorach (powiedzmy, że w obu kolorach mamy do dyspozycji 6 kamyczków).
    Podejście naiwne
    Można by powiedzieć tak: narysujmy sobie taki naszyjnik:

    Teraz powiedzielibyśmy tak: każdy z sześciu kamyczków może zostać wybrany na jeden z dwóch sposobów. Można więc stworzyć 2^6 (czyli 64) różnych naszyjników. Zapamiętajmy ten wynik.
    Refleksja
    Wydawać by się mogło, że problem jest rozwiązany. Jednak w zależności od wyobraźni możemy szybciej lub wolniej zauważyć pewien problem.
    Według powyższego rozumowania poniższe dwa naszyjniki są różne:


    A przecież zamiana jednego w drugi to lekki obrót naszyjnika. Nikt w realnym świecie nie dałby sobie wmówić, że są to dwa odmienne wzory. To oznacza, że do naszego problemu zliczania naszyjników trzeba podejść inaczej...
    Podejście Burnside'a
    Żeby policzyć ile jest istotnie różnych naszyjników użyjemy lematu Burnside'a.
    Najpierw zastanówmy się, co można z takim naszyjnikiem zrobić? Wypiszmy:
    Zostawić jak leży, nie robić nic.
    Obrócić w lewo o jeden kamyczek
    Obrócić w lewo o dwa kamyczki
    Obrócić w lewo o trzy kamyczki
    Obrócić w lewo o cztery kamyczki
    Obrócić w lewo o pięć kamyczków

    Możemy przyjąć, że kamyki są kolorowe tylko z jednej strony, przez co odchodzą operacje odwracania naszyjnika na drugą stronę (tak, że to co teraz jest na wierzchu byłoby pod spodem). Robimy to dla ułatwienia obliczeń.
    Teraz po kolei będziemy się zastanawiać dla każdej z powyższych czynności ile jest takich naszyjników, że przed i po danej operacji nic w wyglądzie naszyjnika się nie zmieni.
    Jeżeli nic nie będziemy z naszyjnikiem robić, to każdy jest inny - czyli mamy 2^6 takich naszyjników.
    Jeżeli obrócimy o jeden kamyk, to każdy kamień musi być tego samego koloru. Takich naszyjników nie jest wiele, bo tylko 2.
    Przy obrocie o dwa mamy cztery możliwości: zauważmy, że tworzą się dwa niejako trójkąty, wszystkie kamyki w trójkącie muszą być tego samego koloru, a więc albo oba są tego samego koloru (2 możliwości), albo są innych kolorów (znowu dwie możliwości). Widać to na rysunku niżej

    Obrót o trzy: widzimy, że stworzą się trzy pary. W każdej parze oba kamienie muszą być tego samego koloru, czyli mamy 2^3 (czyli osiem) możliwości.
    Obrót o cztery jest taki sam jak obrót o dwa, więc znowu 4.
    Obrót o pięć jest taki sam jak obrót o 1, czyli znowu 2.
    Dwa ostatnie przypadki były łatwe, bo obrót o 5 w lewo to to samo, co obrót o 1 w prawo, analogicznie jest z 4 i 2.
    Teraz musimy dodać wszystkie te wartości i podzielić przez liczbę ruchów jakie były dozwolone (czyli te, które są wypisane w liście powyżej).
    Liczymy:
    Jak widać, otrzymany wynik jest istotnie różny niż ten, który dostaliśmy stosując podejście naiwne!
    Ogólny schemat działania
    Można się zastanowić, czy ta sztuczka działa tylko dla koralików. Otóż nie, jest to bardzo uniwersalna metoda działania. Niezależnie czy rozważamy koraliki, kolorowanie grafów, figur w płaszczyźnie bądź przestrzeni postępowanie jest to samo: wypisujemy możliwe operacje i dla każdej szukamy takich obiektów, że przed i po tej operacji są dokładnie takie same. Potem dodajemy, dzielimy przez liczbę działań i mamy wynik.
    Ścisłe wyjaśnienie algebraicznej teorii - nie dla ludzi o słabych nerwach!
    Zacznijmy od tego, że operacje (powyższe obroty) stanowią grupę G działającą na zbiór obiektów kombinatorycznych (w naszym przykładzie naszyjniki, czyli mówiąc ściślej cykl o sześciu wierzchołkach). Grupę którą określiliśmy można rozważać geometrycznie (jak to robiliśmy wyżej) lub jako - liczby od 0 do 5 z działaniem dodawania modulo 6.
    Rozważmy teraz zbiór zwany orbitą elementu x:. Jest to więc zbiór różnych elementów które powstają na wskutek działania grupy G.
    Stabilizator elementu x to taki zbiór działań (czyli elementów z G), że .
    x jest punktem stałym jeżeli . Zbiór punktów stałych wyznaczonych przez element g oznaczamy .
    Zbiór wszystkich orbit oznaczamy .
    Lemat Burnside'a mówi, że (dla skończonych zbiorów działań i elementów) liczba orbit jest równa średniej liczbie punktów stałych, czyli
    Jak widać ten lemat można stosować do przeróżnych obiektów i grup wymyślając przeróżne warunki utożsamiania dwóch obiektów.
    Jeżeli ktoś chce poćwiczyć, to może np. policzyć ile jest istotnie różnych sposobów pokolorowania ścian sześciościanu foremnego przy użyciu dwóch kolorów, jeżeli utożsamiamy takie pokolorowania, że jedno przechodzi na drugie przy pewnym obrocie w
    Jak zawsze zachęcam do zadawania pytań, dyskutowania i komentowania!
  2. Hakken
    Wprowadzenie
    Witam ponownie, dzisiaj będziemy kontynuować naszą przygodę z grafami. Ponieważ jest to kontynuacja zapraszam do zapoznania się z pierwszym, wprowadzającym wpisem traktującym o teorii grafów.
    Tym razem, skoro już wiemy z czym mamy do czynienia, zajmiemy się podstawowymi własnościami i typami grafów.
    Grafy pełne
    Pierwszy typ grafu z jakim się spotkamy to klika. Jest to po prostu taki graf nieskierowany, że każde dwa wierzchołki są połączone krawędzią.
    Skierowaną odmianą kliki jest turniej, czyli taki graf skierowany, że każde dwa wierzchołki są połączone krawędzią. Nie ma jednak znaczenia skierowanie tej krawędzi.
    Nazwa "graf pełny" bierze się więc stąd, że do pełnego grafu nie da się dodać nowej krawędzi (o ile nie dodamy oczywiście jakiegoś wierzchołka).
    Przykład: klika o pięciu wierzchołkach

    Grafy dwudzielne
    Graf nazwiemy dwudzielnym, jeżeli jego zbiór wierzchołków możemy podzielić na dokładnie dwa rozłączne zbiory, takie, że w obrębie tych zbiorów żadne dwa wierzchołki nie są połączone krawędzią.
    Dla wygody grafy te rysujemy tak, że oba zbiory wierzchołków rysujemy w rzędach, obok siebie.
    Przykład:

    Pełny graf dwudzielny to taki graf, że każdy wierzchołek z pierwszego zbioru jest połączony krawędzią z każdym wierzchołkiem drugiego zbioru.
    Analogicznie możemy mówić o grafach trójdzielnych, czworodzielnych itd, wtedy zamiast dwóch zbiorów wierzchołków mamy ich odpowiednio więcej.
    Eulerowskość i Hamiltonowskość
    Zastanawialiście się kiedyś, czy można tak przejść po jakimś grafie, żeby użyć każdej krawędzi dokładnie raz? A może dodatkowo uda się wrócić do wierzchołka z którego zaczęliśmy?
    Euler się zastanawiał. Stąd też graf, który da się w ten sposób obejść (zaczynając z pewnego wierzchołka obchodzimy go tak, żeby każdej krawędzi użyć dokładnie raz i wrócić do wierzchołka początkowego) nazywamy grafem Eulerowskim, a cykl który powstanie na skutek tego obejścia cyklem Eulera.
    Jeżeli użyjemy każdej krawędzi raz, ale nie wrócimy do wierzchołka początkowego, to droga taka będzie ścieżką Eulerowską, a graf pół-Eulerowski.
    Podobnie sytuacja ma się z grafami Hamiltonowskimi, tutaj jednak interesuje nas odwiedzenie dokładnie raz każdego wierzchołka.
    Mogłoby się wydawać, że to czy dany graf ma cykl Eulera jest w jakiś sposób powiązane z posiadaniem cyklu Hamiltona (lub w drugą stronę). Niestety nic nie wiadomo o takich powiązaniach.
    Planarność
    Graf jest planarny jeżeli można go narysować na płaszczyźnie tak, żeby krzywe reprezentujące krawędzie się nie przecinały. Takie narysowanie które spełnia nasz warunek nazywamy płaskim włożeniem grafu.
    Lemat o uściskach dłoni
    Jest to bardzo podstawowe i ważne twierdzenie w teorii grafów, brzmi następująco: w dowolnym nieskierowanym, skończonym grafie zachodzi równość: , gdzie |E| to liczba krawędzi a deg(v) to stopień wierzchołka v.
    Na pierwszy rzut oka twierdzenie wydaje się dość mało przydatne, ale wniosek który z niego wysuniemy jest bardzo użyteczny: liczba wierzchołków nieparzystego stopnia jest parzysta.
    Warunek Eulerowskości
    Okazuje się, że sprawdzenie czy graf posiada cykl Eulera jest bardzo proste. Graf nieskierowany jest Eulerowski wtedy, i tylko wtedy gdy każdy wierzchołek ma parzysty stopień.
    Dla grafów skierowanych warunek konieczny i dostateczny jest równie prosty: graf skierowany jest Eulerowski wtedy i tylko wtedy gdy do każdego wierzchołka wchodzi tyle samo krawędzi, co z niego wychodzi.
    Warunki Hamiltonowości
    Niestety z cyklem Hamiltona nie jest tak łatwo jak z Eulerowością.
    Istnieje kilka twierdzeń, żadne jednak nie jest równie wygodne co powyższe dotyczące Eulerowości.
    Twierdzenie Orego mówi, że jeżeli w grafie prostym o więcej niż dwóch wierzchołkach zachodzi (n to liczba wierzchołków) dla każdej pary wierzchołków niepołączonych bezpośrednio krawędzią to graf ten posiada cykl Hamiltona.
    Inne przydatne twierdzenie (będące wariacją twierdzenia Orego) to twierdzenie o liczbie krawędzi. Mówi ono, że jeśli graf prosty o n wierzchołkach ma przynajmniej m krawędzi, gdzie , to jest hamiltonowski.
    Powyższe twierdzenia mówią o warunkach wystarczających, ale nie koniecznych. Niespełnienie tych warunków nie oznacza, że graf nie jest hamiltonowski!
    Istnieje też twierdzenie o warunku koniecznym, ale niewystarczającym: jeśli graf jest hamiltonowski, to po usunięciu dowolnych k wierzchołków graf rozpada się na co najwyżej k spójnych składowych.
    Jako proste ćwiczenie polecam wymyślić cztery grafy - jeden bez cyklu hamiltona ani eulera, drugi z cyklem eulera ale bez cyklu hamiltona, trzeci odwrotnie do drugiego - z hamiltonem ale bez eulera, a czwarty zarówno z cyklem eulera jak i hamiltona.
    Wydaje mi się, że na jeden wpis starczy. Przy następnych odwiedzinach teorii grafów pewnie zajmiemy się kolorowankami .
    Jak zawsze zachęcam do komentowania i zadawania pytań.
  3. Hakken
    Wstęp
    Teoria liczb zajmuje się (tutaj bez niespodzianek) badaniem właściwości zbioru liczb całkowitych (i tylko tymi liczbami będziemy się w tym wpisie zajmować!).
    Najpopularniejsze zagadnienia to badanie pierwszości liczby, rozwiązywanie kongruencji a także szybkie sposoby na wykonywanie obliczeń. Pojawiają się też elementy kryptologii.
    Dzielenie z resztą i podstawowe nazwy
    Jednym z fundamentalnych twierdzeń jest własność dzielenia z resztą. Własność ta brzmi następująco:
    Dla b > 0 i dowolnego a istnieją jednoznacznie wyznaczone q (iloraz) oraz r z przedziału od 0 do b (reszta, oznaczana a mod b) takie, że a = bq + r.
    Jeśli b nie jest zerem oraz a = bc, to a jest wielokrotnością b.
    Jeśli przy tym b jest większe niż zero, to b jest dzielnikiem a (oznaczamy b|a).
    Jeśli jedynymi dzielnikami a jest jedynka i a, to a jest liczbą pierwszą.
    Największy wspólny dzielnik
    Największy wspólny dzielnik (oznaczamy NWD) dwóch liczb (nierównych zeru) to taka liczba, że dzieli ona obie te liczby i nie ma większej liczby takiej, która dzieli obie te liczby.
    Jeśli NWD(a,b)=1, to mówimy, że a i b są względnie pierwsze i oznaczamy .
    Przykłady
    6 jest względnie pierwsze z 35 (bo dzielnikami 6 jest 1, 2 i 3, a dzielniki 35 to 1, 5 i 7, więc NWD(6,35)=1 czyli są to liczby względnie pierwsze).
    NWD(6,27)=3, bo dzielniki 6 są jak wyżej a dzielniki 27 to 1 i 3).
    Algorytm Euklidesa
    Algorytm Euklidesa służy do szybkiego wyznaczania NWD dwóch liczb.
    Pominę formalny opis i przedstawię jak to liczyć:
    Robimy tabelkę o szerokości dwóch kolumn, wpisujemy w jednej kolumnie pierwszą liczbę, a w drugiej drugą.
    Pod lewą liczbą zapisujemy tę po prawej, a pod prawą zapisujemy resztę z dzielenia przez siebie liczb na górze.
    Powtarzamy aż dojdziemy do zera.
    Przykład:
    Dla 3575 i 462 mamy:

    A więc NWD tych liczb to 11.
    Podstawowe twierdzenie arytmetyki
    Każda liczba a>0 ma jednoznaczny z dokładnością do kolejności czynników rozkład , gdzie liczby są pierwsze.
    To twierdzenie (jak wskazuje nazwa ) jest dość ważne, żyjemy z nim od szkoły podstawowej i pewnie dla wszystkich jest dość oczywiste, że jest prawdziwe. Prawdziwe jest, ale (po głębszym zastanowieniu) wcale nie jest takie oczywiste .
    Dowód jednak pominiemy, i przejdziemy do...
    Kongruencje
    Dla dodatniej liczby n mówimy, że a przystaje do b modulo n (zapisujemy ), jeżeli n|(a-b), czyli jeżeli po prostu a i b dają taką samą resztę z dzielenia przez n.
    Liczbę n nazywamy modułem kongruencji.
    Przykładowo .
    Podstawowe własności kongruencji
    Jest to relacja równoważności - o tym nie pisałem, może kiedyś napiszę. Oznacza to tyle, że:
    - jeżeli a przystaje do b, to b przystaje a.
    - jeżeli a przystaje do b, b przystaje do c, to a przystaje do c.
    - a przystaje do a.
    (wszystko oczywiście mod n).
    Jeśli a przystaje do b i c przystaje do d, oraz moduł tych kongruencji jest taki sam, to .
    .

    Odwrotność modulo
    Jest to taka liczba x, że dla ustalonego a i b.
    Jak obliczać odwrotność modulo (zwaną też odwrotnością multiplikatywną)?
    Otóż posłuży nam do tego rozszerzony algorytm Euklidesa.
    Do początkowej tabelki dopisujemy dwie kolumny (nazwijmy je p i q) i po obliczeniu NWD (czyli po wykonaniu standardowego algorytmu Euklidesa) będziemy uzupełniać od dołu wartości p i q.
    Wartość z q będzie szła do góry (do p), natomiast nowe q będziemy obliczać tak, żeby w każdym wierszu zachodziła równość ap + bq = 1.
    Początkową wartością p jest 1, a q 0.
    Wynikiem jest q z pierwszego wiersza.
    Przykład
    Dla

    Teraz przedstawię kilka twierdzeń, które pozwalają na dość efektywne rozwiązywanie problemów dotyczących kongruencji.
    Chińskie twierdzenie o resztach
    Niech , gdzie liczby w ilorazie są parami względnie pierwsze. Wtedy dla dowolnych istnieje dokładnie jedno a z przedziału od 0 do n-1, takie, że dla i od 1 do k.
    W szczególności taki układ kongruencji jest równoważny jednej kongruencji (dla modułu kongruencji równego n).
    Małe twierdzenie Fermata
    Jeśli p jest liczbą pierwszą i a nie jest podzielne przez p, to .
    Funkcja Eulera
    Oznaczana przez , jest to liczba liczb mniejszych niż n względnie pierwszych z n.
    Twierdzenie Eulera
    Jeśli a jest względnie pierwsze z n, to .
    Przykład
    Rozwiążmy .
    Rozwiązanie w spoilerze.

    Jak zawsze zachęcam do komentowania, zadawania pytań i dyskutowania.
  4. Hakken
    Abstrakt
    Pierścień to struktura algebraiczna która porządkuje i formalizuje działania na liczbach całkowitych oraz działania modulo (arytmetykę modularną).
    Zwłaszcza arytmetyka modulo okazuje się przydatna, między innymi w kryptologii.
    Intuicyjnie pierścieniem jest zbiór z określonymi działaniami dodawania, odejmowania i mnożenia.
    Definicja
    Weźmy algebrę w której R jest niepustym zbiorem, to działania (funkcje) dwuargumentowe określone w tym zbiorze (), a 0 to pewien element wyróżniony (neutralny dla dodawania).
    Jeżeli ta algebra spełnia poniższe warunki, bo nazwana będzie pierścieniem.
    0 jest elementem neutralnym dodawania

    Działanie dodawania jest łączne

    Każdy element ma element przeciwny

    Element przeciwny do a często oznaczamy -a.
    Dodawanie jest przemienne

    jest półgrupą z mnożeniem, które jest łączne (warunek jest prawie dokładnie taki sam jak powyżej formułowany warunek o łączności dodawania, ten jest taki sam, tylko zamiast dodawania mamy mnożenie).
    Zachodzą prawa rozdzielności pomiędzy tymi działaniami

    Działania są wewnętrzne (czyli ich wyniki należą do zbioru R)

    Inne rodzaje pierścieni
    Możemy zdefiniować różne podobne struktury algebraiczne, przykładowo pierścień z jedynką który oprócz powyższych warunków wymaga, aby również dla mnożenia istniał element neutralny (jedynka).
    Inne rodzaje pierścieni to pierścienie przemienne, w których mnożenie jest przemienne (), czy też pierścienie bez dzielników zera.
    Dzielniki zera
    Dzielnikiem zera jest taki element pierścienia a, że istnieje dla niego element b należący do tego pierścienia, że ).
    Przykłady
    Pierścień zawierający tylko jeden element.
    Liczby całkowite ze standardowym mnożeniem i dzieleniem.
    . Jest to zbiór liczb całkowitych od 1 do n-1, operacje dodawania i mnożenia są modulo n, czyli jeżeli wynik działania jest większy niż n, to wynikiem działania jest reszta z dzielenia wyniku (obliczonego standardowo) przez n (np. ).
    Macierze kwadratowe o ustalonym rozmiarze (moje wpisy o macierzach: pierwszy, drugi, trzeci).
    Ideały
    Ideałem pierścienia R nazwiemy taki podzbiór H, że
    H jest podgrupą .



    Dla pierścienia przemiennego ostatnie dwa warunki są oczywiście równoważne.
    Można również rozważać ideały lewo- lub prawostronne, wtedy należy wyrzucić odpowiednio warunek trzeci lub drugi.
    Przykłady
    Jednoelementowy zbiór zawierający zero jest ideałem.
    W liczbach całkowitych ze standardowymi działaniami liczby parzyste są ideałem.
    Generatory ideałów
    Ideały mogą być generowane przez zbiór. Ideałem generowanym przez pewien zbiór jest zbiór powstały poprzez użycie mnożenia na wszystkich możliwych parach, gdzie jeden element pochodzi z pierścienia, a drugi z naszego zbioru generującego.
    Jeżeli zbiór którym generujemy ideał jest jednoelementowy, to mówimy, że jest to ideał główny.
    W przypadku gdy pierścień nie jest przemienny (czyli mnożenie w nim nie jest przemienne), możemy rozważać ideały lewo- oraz prawostronne ustawiając elementy z pierścienia odpowiednio po prawej lub po lewej stronie.
    Przykłady
    Dwójka w liczbach całkowitych generuje liczby parzyste.
    Trójka w liczbach całkowitych generuje liczby podzielne przez 3.
    To tyle na ten wpis, jak zawsze zachęcam do komentowania, dyskutowania i zadawania pytań.
  5. Hakken
    Przedsłowie
    Ten wpis będzie trochę bardziej popularnonaukowy. Wciąż będą twierdzenia dla tych, którzy (podobnie jak ja) lubią ścisłość, ale w większej mierze skupimy się na samym pomyśle i intuicji. Będę więc powoływał się na twierdzenia, których nie będę dowodził (inaczej niż autorytetem ).
    Zobaczymy jak taka forma wam się podoba, piszcie w komentarzach
    Abstrakt
    Podziałem sekretu nazwiemy takie rozdysponowanie informacji pomiędzy osobami, że dopiero kiedy dostatecznie duża liczba osób się dogada będą w stanie poznać sekret.
    Zastanowimy się jak to zrobić.
    Wstęp
    W naszym przypadku sekretem będzie wartość pewnego wielomianu (link do mojego wpisu o wielomianach).
    Weźmy dla przykładu zwykłą funkcję kwadratową: . Ile informacji potrzebujemy aby poznać wartości ?
    Musimy do tego znać wartości tego wielomianu w przynajmniej 3 (różnych) punktach. Jest to dość oczywiste - dostaniemy trzy równania o trzech niewiadomych, dane pochodzą z wykresu funkcji, więc nie będzie to układ sprzeczny.
    Jeżeli byśmy mieli mniej informacji (np. tylko dwa punkty), to oczywiście nie odgadniemy wartości których szukamy. Dla dociekliwych - dowodem na to jest twierdzenie Kroneckera-Capellego (link do artykułu na Wikipedii).
    Co więcej, znając te trzy punkty wynik będzie jednoznaczny (czyli dostaniemy dokładnie jeden wielomian).
    Analogiczne własności mają wielomiany wyższych stopni, co zapiszemy jako twierdzenie (a raczej twierdzonko. Czemu? Okaże się to za chwilę).
    Twierdzonko
    Dla różnych liczb rzeczywistych przez ustalone punkty przechodzi dokładnie jeden wielomian stopnia nie większego niż .
    To twierdzonko jest fajne, ale chcemy więcej. Chcemy zmienić zbiór nad którym rozpatrujemy nasze wielomiany.
    Twierdzenie to będzie prawdziwe nad każdym ciałem (mój wpis o ciałach), rozpatrzmy więc ciało , gdzie p jest liczbą pierwszą. Takie ciało będzie zawierało wszystkie liczby naturalne od 0 do .
    Działania będą modulo p, czyli jeżeli wynik dodawania lub mnożenia będzie większy niż wartość p, to jako wynik weźmiemy resztę z dzielenia przez p.
    Przykładowo dla p=13:

    Rozpatrywać będziemy nad tą strukturą wielomiany, przykładowo dla .
    Wtedy .
    Teraz możemy napisać nasze twierdzenie.
    Twierdzenie
    Dla różnych liczb przez ustalone punkty przechodzi dokładnie jeden wielomian nad stopnia nie większego niż (dla ).
    Teraz (wreszcie!) przejdziemy do podziału sekretu.
    Przyjmijmy, że pewna grupa k osób ma wspólny sekret M będący liczbą. Liczba ta jest mniejsza niż nasze p, a większa niż 0.
    Chcemy rozdzielić sekret pomiędzy te osoby tak, aby uzyskać pewien stopień bezpieczeństwa.
    Pierwszy stopień bezpieczeństwa
    Chcemy, aby wszystkie k osób mogło odtworzyć sekret, ale też aby bez pełnego kompletu było to niemożliwe.
    Aby to uzyskać weźmy dowolny wielomian W nad stopnia k-1 taki, że jego wartość w zerze wynosi M.
    Teraz dokonamy samego podziału sekretu - pierwszej osobie podamy wartość wielomianu w jedynce, drugiej w dwójce itd.
    Korzystając z naszego twierdzenia wiemy, że jeżeli wszystkie osoby zbiorą się razem, to będą mogły poznać wartość tego wielomianu w zerze (i tym samym poznać sekret).
    Co więcej, taki podział sekretu jest dobry, bo mając nawet tylko o jedną osobę za mało nie możemy z żadnym sensownym prawdopodobieństwem wyznaczyć M. Nie chcielibyśmy, żeby k-1 osób mogło wyznaczyć np. dwie liczby, z których dokładnie jedna będzie równa M. Chcemy, żeby nie byli w stanie nic powiedzieć o M.
    I tak własnie jest. Intuicyjnie można to zobaczyć na rysunku. Przyjmijmy, że nasz wielomian jest pierwszego stopnia (czyli na płaszczyźnie byłaby to prosta kreska (funkcja afiniczna mówiąc ściśle)).
    I wiemy na przykład, że jego wartość w jedynce wynosi 5. Nie jesteśmy nic w stanie powiedzieć o wartości w zerze, może to być równie dobrze 5, co -3 (i co dowolna inna liczba).
    Drugi poziom bezpieczeństwa
    Teraz byśmy chcieli, aby pewna podgrupa mogła odtworzyć sekret. Powiedzmy, że chcemy aby dowolna grupa k-3 osób mogła odtworzyć sekret.
    W tym celu wybieramy jakiś wielomian stopnia k-4, którego wartość w zerze to M. Podobnie jak wyżej przydzielamy kolejnym osobom kolejne wartości.
    Poziom trzeci?
    A co jeśli chcielibyśmy, aby do odtworzenia sekretu wystarczyła połowa (albo 75%)?
    Jak należy wtedy rozdysponować wartości? To zagadka dla was, piszcie w komentarzach .
    Jak zawsze zachęcam do komentowania, dyskutowania i zadawania pytań!
  6. Hakken
    Abstrakt
    Aby wprowadzić pewną hierarchię i porządek przy rozważaniu grafów wprowadzono termin drzewa. Różne rodzaje drzew są różnymi wariacjami na temat grafów, umożliwiając łatwe (szybkie) uzyskiwanie informacji właśnie ze względu na większe uporządkowanie.
    Uwaga, przed lekturą zachęcam do zapoznania się z tekstem dotyczącym grafów (link) jak i innych tekstów na tym blogu.
    Drzewa wolne
    Drzewem wolnym nazwiemy spójny, acykliczny graf. Zbiór rozłącznych drzew nazwiemy lasem.
    Przykład:
    Drzewo

    Las

    Drzewa ukorzenione
    Drzewo ukorzenione to takie drzewo wolne, w którym wyróżniamy jeden element (korzeń).
    Wierzchołki takiego drzewa często nazywa się węzłami.
    Drzewa rysuje się zwyczajowo korzeniem u góry, przykładowo:

    Tutaj korzeń oznaczyłem podwójnym okręgiem, ale raczej nie będę tego robił, i będę zakładał, że węzeł na górze rysunku do którego nic nie wchodzi jest korzeniem.
    Oznaczenia
    Rozważmy węzeł x drzewa ukorzenionego T (którego korzeniem niech będzie r). Każdy węzeł na ścieżce z r do x nazwiemy przodkiem x. X jest natomiast potomkiem każdego z tych węzłów.
    Na obrazku sprawa wygląda dość jasno - jeżeli na jakiejś ścieżce węzeł a jest wyżej niż węzeł b, to a jest potomkiem b, natomiast b jest przodkiem a.
    Poddrzewo o korzeniu x to drzewo złożone z potomków x (i x jest wtedy korzeniem takiego drzewa). Na rysunku jest to tak, jakby "odciąć" jakiś węzeł od reszty drzewa.
    Poprzednik x to taki węzeł y, że z y do x jest bezpośrednie połączenie. Wtedy też x jest nazywany następnikiem lub synem lub (w ramach równości płci...) dzieckiem y.
    Jeżeli jakiś węzeł nie ma synów (będę raczej stosował to określenie, chociaż w dzisiejszym świecie jest to dość niebezpieczne, ale cóż... żyję na krawędzi ) to nazywany jest liściem.
    Stopień węzła to liczba jego synów.
    Głębokość węzła to długość ścieżki od korzenia do tego węzła.
    Drzewo uporządkowane to takie, w którym wszyscy synowie są uporządkowani (czyli w jakiś sposób odróżnialni, mogą być pokolorowani czy też ponumerowani).
    Drzewa binarne
    Drzewo binarne to takie drzewo, że każdy wierzchołek ma co najwyżej dwóch synów (lewego i prawego). Warto przy tym zauważyć, że dwa drzewa: jedne z korzeniem i prawym synem a drugie z korzeniem i lewym synem są różne nawet jeśli wartości w węzłach są takie same.
    Przykład:

    Drzewa wyszukiwań binarnych - BST
    Drzewo BST to takie drzewo binarne, że jeżeli wartość węzła x wynosi y, to w jego lewym poddrzewie wszystkie węzły będą miały wartość mniejszą niż y, a w prawym większą niż y.

    Co nam to daje? W normalnym drzewie podczas szukania konkretnej wartości musimy sprawdzić każdy węzeł. W drzewie BST wystarczy tyle operacji, ile wynosi głębokość tego drzewa (porównujemy z wartością w korzeniu, schodzimy w jedną stronę, znowu porównujemy, schodzimy, itd.).
    Obiegi drzew
    Możemy obchodzić drzewa na trzy sposoby (no, możemy oczywiście na znacznie więcej, ale te trzy są standardowe): prefixowo, infixowo, postfixowo.
    Obiegi rozpatrujemy w ramach jakiejś operacji, weźmy na przykład wypisanie wartości danego węzła.
    Przy obiegu prefixowym najpierw wypiszemy siebie, później (prefixowo) lewe poddrzewo, a następnie (również prefixowo) prawe poddrzewo.
    Przy obiegu infixowym najpierw infixowo wypiszemy lewe poddrzewo, następnie siebie i na końcu (infixowo) prawe poddrzewo.
    Jak łatwo zgadnąć przy obiegu postfixowym najpierw postfixowo wypiszemy lewe poddrzewo, później prawo poddrzewo i na końcu siebie.
    Ciekawa obserwacja jest taka, że przy wypisaniu infixowo drzewa BST (z angielskiego BST to binary search tree, więc zasadniczo zwrot "drzewo BST" jest pleonazmem, bo BST samo w sobie zawiera słowo "drzewo", ale zwyczajowo tak się mówi) otrzymamy ciąg posortowany (ściśle monotoniczny).
    Proponuję jako ćwiczenie przeprowadzić na kartce (albo w myślach) obieg post/pre/in- fixowy dla powyższego drzewa BST.
    Jak zawsze zachęcam do komentowania, dyskutowania i zadawania pytań!
  7. Hakken
    Przedsłowie
    Abstrakt
    Graf to, mówiąc najprościej, wierzchołki połączone krawędziami.
    Używa się ich często do modelowania zjawisk ze świata rzeczywistego, takich jak rozmieszczenie miast, połączenia pociągowe czy relacje między poszczególnymi osobami.
    Definicja
    Grafem skierowanym nazwiemy parę , gdzie V jest skończonym zbiorem wierzchołków, a E relacją binarną w V. Zbiór E nazwiemy zbiorem krawędzi, a jego elementy krawędziami.
    Grafem nieskierowanym nazwiemy parę , gdzie V jest zbiorem wierzchołków jak wyżej, natomiast E to zbiór nieuporządkowanych par wierzchołków.
    Różnica między grafem nieskierowanym a skierowanym jest więc taka, że w grafie nieskierowanym para ze zbioru krawędzi , a w grafie skierowanym nie.
    Kolokwialnie rzecz ujmując, graf to wierzchołki (punkty) i łączące je krawędzie. W grafie skierowanym krawędzie mają strzałki - działają tylko w jedną stronę. W nieskierowanym krawędzie nie mają strzałek - działają w obie strony.
    Przykłady
    Poniżej jest wykonany rysunek (1.1) grafu skierowanego dla .

    Tutaj natomiast jest przykład (1.2) grafu nieskierowanego, dla .

    Oznaczenia
    W grafie skierowanym mówimy, że krawędź wychodzi i wchodzi do wierzchołka. Na przykładzie 1.2 powiemy, że krawędź wychodzi z wierzchołka 4 a wchodzi do wierzchołka 1.
    Jeżeli dwa wierzchołki są połączone krawędzią, to mówimy, że są one sąsiadami. W grafie nieskierowanym relacja bycia sąsiadem jest oczywiście symetryczna, czyli jeśli v jest sąsiadem u, to u jest sąsiadem v.
    W grafie skierowanym jest inaczej, jeśli u jest sąsiadem v, to v nie musi być sąsiadem u. Na przykładzie 1.2 3 jest sąsiadem 6, ale 6 nie jest sąsiadem 3.
    Stopniem wierzchołka w grafie nieskierowanym nazywamy liczbę krawędzi w których dany wierzchołek uczestniczy, na przykładzie 1.2 stopień wierzchołka 2 to 2, a wierzchołka 5 to 1.
    W grafie nieskierowanym stopień wejściowy wierzchołka to liczba krawędzi wchodzących do tego wierzchołka, a stopień wyjściowy to liczba krawędzi z niego wychodzących.
    Stopień wierzchołka w grafie nieskierowanym to suma stopnia wejściowego i wyjściowego.
    Dla wierzchołka 2 w przykładzie 1.1 jego stopień wejściowy to 2, wyjściowy 3, a więc stopień w ogóle to 5.
    Ścieżka o długości k pomiędzy wierzchołkami v i u to taki zbiór wierzchołków , że każdy jest sąsiadem swojego poprzednika oraz .
    Długość ścieżki to liczba wierzchołków wchodzących w skład ścieżki (inaczej mówiąc jest to moc wyżej zdefiniowanego zbioru).
    Jeżeli istnieje ścieżka p z wierzchołka u do v, to powiemy, że v jest osiągalny z v po ścieżce p.
    Cyklem nazwiemy taką ścieżkę , że oraz długość ścieżki jest niezerowa.
    Graf który nie zawiera cykli nazywamy acyklicznym.
    Spójność
    Graf nieskierowany jest spójny jeżeli każde dwa wierzchołki są przez siebie osiągalne.
    Spójne składowe to klasy abstrakcji relacji bycia osiągalnym. Kolokwialnie mówiąc, jeśli istnieje ścieżka z jednego wierzchołka do drugiego, to są one w ten samej spójnej składowej.
    Na przykładzie 1.2 mamy trzy spójne składowe: są to zbiory wierzchołków: . Oczywiście graf nieskierowany jest spójny wtedy, i tylko wtedy, gdy ma tylko jedną spójną składową (jest nią wtedy cały graf).
    Graf skierowany jest silnie spójny jeżeli każde dwa wierzchołki są osiągane jeden z drugiego.
    Analogicznie tworzymy silne spójne składowe. Są to klasy abstrakcji relacji bycia wzajemnie osiągalnym.
    Na przykładzie 1.1 mamy trzy silnie spójne składowe: .
    Ważenie grafu
    Graf jest ważony, jeżeli zdefiniujemy koszt przejścia po każdej krawędzi.
    Dodajmy wagi do grafu z przykładu 1.1

    Można w taki sposób prezentować np. koszt biletów pociągowych między miastami. Naturalnie nasuwającym się pytaniem jest "jak najtaniej przejechać z miasta A do miasta B?". Dla tego przykładu rozpatrzmy przejście z wierzchołka 1 do 4.
    Możemy przejść z 1 do 2 i z 2 do 4. Taka ścieżka ma sumaryczny koszt równy 7.
    Ale można też przejść z 1 do 2, z 2 do 5 i na koniec z 5 do 4. Taka ścieżki mimo, że jest dłuższa, to koszt jest mniejszy (wynosi 6).
    Algorytm rozwiązujący ten problem ogólnie to algorytm Dijkstry, ale nie będę teraz o nim pisał, być może poświęcę mu osobny wpis.
    Myślę, że na początek starczy. W następnym wpisie zajmę się najprawdopodobniej drzewami (nie, nie zmieniłem zainteresowań z matematyki/informatyki na botanikę ).
    Jak zawsze zachęcam do komentowania, zadawania pytań i dyskutowania!
  8. Hakken
    Przedsłowie
    Ten wpis jest pierwszym (i mam nadzieję, że nie ostatnim) wpisem poświęconym kryptologii, czyli w skrócie nauką o tworzeniu i łamaniu szyfrów.
    Zacznę od prostych szyfrów, następnie planuję przejść przez bardziej skomplikowane, a później zajmę się hashami (czy jak to w naszym języku się mówi "skrótami").
    Niestety ze względu na wysokie skomplikowanie większości zagadnień, nie będę w stanie przedstawić pełnej matematycznej aparatury stojącej za każdym z omawianych zagadnień.
    Abstrakt
    One-time pad, zwany po Polsku szyfrem z kluczem jednorazowym jest bardzo łatwym do zrozumienia, ale niemożliwym do złamania szyfrem.
    Jego siła opiera się na pełnej losowości klucza. Niestety, jest niepraktyczny, więc obecnie nie jest szeroko używany.
    Kryptografia - zasada działania
    Sposób działania tego szyfru jest bardzo prosty. Jest to funkcja, która przyjmuje dwa ciągi jedynek i zer - pierwszy będący szyfrowaną wiadomością, a drugi kluczem.
    Wynikiem jest ciąg jedynek i zer powstały poprzez wykonanie operacji xor (czyli alternatywy wykluczającej) na ciągach wejściowych.
    Należy jednak pamiętać, że klucz musi być całkowicie losowy, a także nie może on być użyty więcej niż jeden raz.
    Musi też być tej samej długości, co szyfrowana wiadomość.
    Deszyfrowanie wiadomośći przeprowadza się dokładnie tak samo, jak szyfrowanie (xoruje się tekst zaszyfrowany i klucz).
    Jak działa xor
    xor jest funkcją, która przyjmuje dwa argumenty. Każdy z nich jest zerem lub jedynką. Wynikiem xor-a jest 1, jeżeli podane znaki są różne, natomaist gdy znaki są równe, to wynikiem jest 0.
    1 xor 0 = 0 xor 1 = 1
    0 xor 0 = 1 xor 1 = 0
    Określimy funkcję xor na ciągach zer i jedynek tak, że będzie to działanie zdefiniowanej wyżej funkcji na kolejnych parach z obu ciągów.
    Przykład:


    10110010
    01100111
    ________ xor
    11010101

    Uwaga
    Mówię tutaj cały czas o ciągach zer i jedynek - jak to ma się do szyfrowania tekstu?
    Wystarczy sobie uświadomić, że w pamięci komputera tekst jest kodowany jako ciąg wartości binarnych (czyli właśnie zer i jedynek), a więc to takie wartości musimy de facto szyfrować.
    Kryptoanaliza - rozważania na temat łamania tego szyfru
    Przy zachowaniu warunków o których pisałem wcześniej szyfru tego nie da się złamać. Oznacza to, że jeśli komuś uda się przechwycić naszą zaszyfrowaną wiadomość (ale nie klucz), to jedyne co jest w stanie o niej powiedzieć, to jej długość.
    Dlaczego? Przyjmijmy, że przechwyciliśmy następującą zaszyfrowaną wiadomość: "011101010100011101". Teraz dla każdego ciągu binarnego o długości 18 (bo tyle znaków ma przechwycona wiadomość) możemy dobrać taki klucz, żeby po deszyfracji otrzymać właśnie tę wiadomość którą wybraliśmy.
    Przykładowo możemy przyjąć, że wiadomość jawna to "110100100101101001". Wtedy kluczem byłoby "101001110001110100" (xor obu wiadomości). Ale równie dobrze (z równym prawdopodobieństwem) wiadomością może być "000100100101101001", a wtedy kluczem byłby ciąg "11001110001110100".
    Nawet przy nieskończonej mocy obliczeniowej napastnik nie jest w stanie stwierdzić, który klucz jest poprawny. Ma on zbyt mało danych.
    To tak, jakbyśmy mieli rozwiązać równanie a+b=7 nie znając wartości a ani b. Jest nieskończenie wiele równie dobrych rozwiązań.
    Stosując ten szyfr jesteśmy podatni na zmianę wiadomości przez atakującego.
    Przyjmijmy, że ktoś przechwycził zaszyforwaną wiadomość, której tekstem jawnym jest "Spotkajmy się jutro o 15:30."
    Jeśli osoba przechwytująca wie, że ostatnimi znakami jest godzina spotkania, to może je łatwo zastąpić przez cokolwiek innego (skoro zna tekst jawny i zaszyforwany, to może obliczyć klucz).
    Odbiorca nie jest w stanie zweryfikować, czy wiadomość nie została gdzieś zmieniona.
    Podsumowanie
    Poważnymi wadami tego szyfru jest rozmiar klucza (przesłane dane muszą być dwa razy większe) oraz podatność na modyfikację wiadomości. Co więcej, klucz musi być przekazany w sposób bezpieczny, a jego generacja musi być w pełni losowa.
    Generowanie dużych losowych danych nie jest łatwe z programistycznego punktu widzenia, a ponowne użycie tego samego klucza może być tragiczne w skutkach (szyfr może wtedy zostać złamany).
    Osiągnięcie sprzyjających warunków jest zazwyczaj bardzo trudne, dlatego też szyfr ten nie jest powszechnie stosowany.
    Mimo to, jest to szyfr, którego nie da się złamać, wiec samo to zasługuje na uwagę.
    Jak zawsze zachęcam do komentowania, dyskutowania i zadawania pytań.
  9. Hakken
    Definicje
    Wielomianem charakterystycznym macierzy nazwiemy , gdzie I jest macierzą identyczności, A natomiast badaną macierzą.
    Pierwiastki wielomianu charakterystycznego nazywamy wartościami własnymi
    Niech będzie jednokrotną wartością własną.
    Wtedy rozwiązanie równania nazwiemy wektorem własnym.
    Nie zawsze jednak jest tak łatwo - jakaś wartość własna może być przecież pierwiastkiem wielokrotnym wielomianu charakterystycznego.
    Wtedy trzeba wyznaczyć bazę podprzestrzeni .
    Po zebraniu baz podprzestrzeni własnych dla każdej wartości własnej otrzymujemy bazę podprzestrzeni własnej.
    Przykład
    Weźmy

    Policzmy teraz wielomian charakterystyczny.

    Wartościami własnymi są więc o krotności 2 oraz , o krotności jeden.
    Zajmijmy się najpierw piątką.

    Bazą przestrzeni własnej dla piątki jest więc .
    To samo musimy obliczyć dla drugiej wartości własnej, czyli dwójki.
    To jest jednak pierwiastek podwójny, więc musimy wyznaczyć bazę .

    Bazą tego jądra jest wektor .
    Bazą podprzestrzeni własnej jest więc układ wektorów .
    Zastosowania
    Wartości i wektory własne okazują się użyteczne przy obliczeniach fizycznych (np. dla równania Schrödingera) lub przy wyznaczaniu postaci Jordana macierzy (czyli takiej postaci, gdzie na diagonali są wartości własne, bezpośrednio nad diagonalą jedynki lub zera, a wszędzie indziej zera).
    Kolejnym zastosowaniem jest rozpoznawanie twarzy przez komputery.
  10. Hakken
    W tym wpisie przedstawię podstawowe pojęcia używane do opisu macierzy.
    Przed lekturą zachęcam do zapoznania się z częścią pierwszą, wprowadzającą do zagadnienia macierzy (link).
    Operacje elementarne i schodkowanie macierzy
    Za pomocą operacji elementarnych, czyli:
    mnożeniu wiersza macierzy przez skalar
    dodawania jednego wiersza do drugiego
    zamienianiu wierszy miejscami

    możemy sprowadzić macierz do postaci trójkątnej górnej z jedynkami na diagonali.
    Aby to zrobić najpierw dzielimy pierwszy wiersz przez wartość pierwszego elementu w pierwszym wierszu (tak, aby zaczynał się od jedynki) i od każdego wiersza odejmujemy pierwszy pomnożony przez taką liczbę, aby na pierwszym miejscu było zero. Następnie postępujemy analogicznie dla pozostałych wierszy, zamieniając jedynie pierwszy wiersz i pierwszą wartość na i-ty wiersz i i-tą wartość.
    Okazuje się, że w takiej postaci dużo łatwiej jest wykonywać niektóre obliczenia.
    Rząd macierzy
    Rzędem kolumnowym macierzy nazywamy liczbę liniowo niezależnych kolumn, a rzędem wierszowym - liczbę liniowo niezależnych wierszy tej macierzy.
    Rząd kolumnowy jest równy rzędowi wierszowemu, i nazywamy go rzędem macierzy.
    Rząd macierzy łatwo jest obliczyć przez schodkowanie macierzy. Rząd macierzy będzie wtedy liczbą niezerowych wierszy które zostały po schodkowaniu.
    Ślad macierzy
    Śladem (oznaczamy tr) macierzy kwadratowej jest suma składników znajdujących się na diagonali.

    Jądro macierzy
    Jądrem macierzy (oznaczamy ker) nazywamy taki zbiór wektorów .

    Łatwo obliczyć jądro macierzy sprowadzonej do postaci schodkowej.
    Obraz macierzy
    Obrazem macierzy (który jest oznaczany przez im nazywamy wszystkie wektory, które mogą powstać w wyniki mnożenia jakiegoś wektoru przez tę macierz.
    .
    Obraz macierzy jest rozpięty przez kolumny tejże. Nie polecam jednak schodkować macierz przed wyznaczaniem obrazu, gdyż operacje na wierszach zmieniają obraz.
    Wyznacznik - rozwinięcie Laplace?a
    Macierzy kwadratowej możemy przypisać wartość zwaną wyznacznikiem.
    Dla macierzy jeden na jeden wartością wyznacznika (oznaczanego przez det) jest właśnie ta wartość.
    Jeżeli macierz jest wymiaru n na n, to wartością wyznacznika dla tej macierzy obliczamy tak:
    Wybieramy jakiś wiersz lub kolumnę. Przyjmijmy, że wybraliśmy wiersz (o numerze i), bo oba przypadki są symetryczne.
    Bierzemy po kolei . Wtedy wyznacznik macierzy to suma , gdzie to macierz powstała z wykreślenia z aktualnej macierzy i-tego wiersza oraz j-tej kolumny.


    Jest to dość powolna metoda (trzeba wykonywać dużo obliczeń), więc warto zauważyć, że jeżeli macierz jest w postaci trójkątnej górnej, to wartość wyznacznika jest równa iloczynowi składników na diagonali.
    Przy sprowadzaniu macierzy do postaci trójkątnej w celu liczenia wyznacznika wolno jedynie dodawać do siebie poszczególne wiersze, bo inne operacje zmieniają wartość wyznacznika (mnożenie wiersza lub kolumny przez stałą mnoży wyznacznik przez tę samą wartość, natomiast zamiana wierszy (kolumn) miejscami zmienia znak wyznacznika).
    Łatwo zauważyć, że jeżeli w macierzy jeden z wierszy jest kombinacją liniową pozostałych, to wartością wyznacznika jest zero. Łatwo to sprawdzić, wystarczy wyzerować jeden z tych wierszy (co jest możliwe, bo jest kombinacją liniową), a następnie względem tego wiersza zastosować rozwinięcie Laplace?a.
    Warto też zapamiętać jak obliczać wyznacznik dla macierzy 2 na 2, jest to bardzo proste:

    Przykład

    Rozwiązania umieszczę w spoilerach, zachęcam do zmagań się z obliczeniami samemu i jedynie sprawdzeniu poprawności po zakończeniu.
    Najpierw policzmy rząd macierzy.
    Teraz zajmijmy się śladem.
    Następnie musimy policzyć jądro.
    Wyznaczmy teraz obraz.
    Na koniec: wyznacznik.
    Jako dodatkowe ćwiczenie polecam wyznaczyć wszystkie powyższe wartości dla innych macierzy, na przykład .
    Następny wpis będzie już ostatnim (chwilowo...) wpisem poświęconym całkowicie macierzom.
    Jak zawsze zachęcam do zadawania pytań i dyskusji w komentarzach.
  11. Hakken
    Abstrakt
    Układ liczb czy symboli wpisanych w prostokąt nazywamy macierzą.
    Okazują się niezwykle przydatne przy badaniu algebry liniowej, jak i nauk korzystających z niej (mowa głównie o fizyce).
    Ze względu na szerokie występowanie tego obiektu matematycznego, do jego opisu służy szereg pojęć.
    W tej serii wpisów zajmiemy się określeniem czym macierz jest, jakie działania możemy na macierzach przeprowadzić, przedstawię również kilka najważniejszych typów macierzy.
    Omówię także pojęcia rzędu, jądra, obrazu, wyznacznika, śladu, wartości własnej.
    Czym jest macierz
    Najprościej rzecz biorąc, macierzą nazwiemy układ symboli (liczb, wyrażeń) wpisanych w prostokąt.
    Zbiór macierzy o n wierszach, m kolumnach i elementach z ciała oznaczamy przez .
    Przykłady


    Operacje na macierzach
    Mnożenie przez skalar
    Tutaj nie ma nic nadzwyczajnego, mnożemy każdy element macierzy przez skalar.

    Transpozycja
    Jest to obrócenie macierzy. Pierwszy wiersz staje się pierwszą kolumną, drugi wiersz staje się drugą kolumną i tak dalej.
    Transpozycję oznaczamy literką T.

    Sprzężenie Hermitowskie
    Najpierw transponujemy macierz, a następnie na każdym elemencie macierzy używamy sprzężenia (tak, jak w liczbach zespolonych).
    Oznaczamy literką H.

    Moduł
    Z każdego elementu macierzy bierzemy wartość bezwzględną.

    Działania na macierzach

    Dodawanie
    Dodawanie jest zdefiniowane tylko na macierzach tego samego rozmiaru. Dodajemy wtedy do siebie elementy na odpowiadających sobie pozycjach.

    Oczywiście w tym przykładzie użyłem liczb rzeczywistych (wraz ze standardowym dodawaniem), ale gdyby dodawania było zdefiniowane inaczej, to należałoby użyć właśnie tej operacji.
    Mnożenie
    Tu już nie jest aż tak łatwo jak przy dodawaniu.

    Przykładowo

    Ponieważ na początku mnożenie może być trudne, polecam napisane macierzy A normalnie, a macierzy B na górze po prawej stronie od A.
    Wtedy łatwo będzie zauważyć, które wartości należy pomnożyć przez które (łatwo to zaobserwować na podanym przykładzie).
    Warto też zauważyć, że mnożenie nie jest przemienne, co łatwo sprawdzić na przykładzie.

    Specjalne rodzaje macierzy
    Kwadratowa
    Jest to taka macierz, która ma tyle samo wierszy co kolumn.
    Diagonalna
    Jest to taka macierz kwadratowa, że wszędzie poza diagonalą ma zera. Diagonala jest to przekątna macierzy, z lewego górnego do prawego dolnego rogu.
    Zbiór takich macierzy oznaczamy DIAG.
    Trójkątna górna
    Jest to taka macierz, że pod diagonalą ma tylko zera.
    Zbiór takich macierzy oznaczamy TRIU.
    Trójkątna dolna
    Jest to taka macierz, że nad diagonalą ma tylko zera.
    Zbiór takich macierzy oznaczamy TRIL.
    Identycznościowa
    Jest to taka macierz diagonalna, że na przekątnej ma same jedynki.
    Oznaczamy ją jako I lub In.
    Macierz taka jest elementem neutralnym dla mnożenia.
    Symetryczna
    Jest to taka macierz, że jej transpozycja równa jest jej (transpozycja nic nie zmienia w przypadku macierzy symetrycznej).
    Hermitowska
    Jest to taka macierz, że jej sprzężenie Hermitowskie równe jest jej (czyli sprzężenie Hermitowskie macierzy Hermitowskiej nic nie zmienia).
    Nieosobliwa
    Powiemy, że macierz A jest nieosobliwa (odwracalna), jeżeli istnieje taka macierz B, że iloraz A i B da identyczność.
    Jeżeli taka macierz B nie istnieje, to A nazwiemy osobliwą (nieodwracalną).

    Jako zadanie do poćwiczenia polecam wykonać kilka mnożeń macierzy.
    Następny wpis również będzie poświęcony macierzom. Zajmę się w nim pojęciom opisującym macierze (ślad, wyznacznik, etc.).
    Jak zawsze zachęcam do zadawania pytań.
  12. Hakken
    Czytelnik powinien być zaznajomiony z podstawami algebry abstrakcyjnej (moje artykuły na ten temat: 1,2) oraz podstawowymi zagadnieniami i oznaczeniami matematycznymi.
    Abstrakt
    Przestrzenie liniowe to główny obiekt badań algebry liniowej, okazują się one niezwykle przydatne w innych gałęziach matematyki oraz fizyce (inżynierii), ze względu na swoje proste opisanie przez bazę.
    Jest to zbiór wektorów, które mogą być dodawana oraz skalowane.
    Definicja
    Niech (X,+) będzie grupą abelową, w której elementem neutralnym jest 0, a element przeciwny do a oznaczymy przez -a.
    Załóżmy, że w X określono działanie mnożenia (oznaczmy je przez kropkę, chociaż czasem będę ją pomijał) przez elementy z ciała K takie, że:
    Jest przemienne

    Posiada element neutralny (jedynkę)

    Jest łączne i rozdzielne względem dodawania


    Wówczas zbiór X wraz z działaniami mnożenia i dodawania nazwiemy przestrzenią liniową nad ciałem K.
    Elementy przestrzeni liniowej nazywamy wektorami.
    Przykłady
    Zbiór wielomianów z działaniami dodawania wielomianów i mnożenia ich przez liczbę jest przestrzenią liniową.
    Zbiór funkcji z niepustego zbioru w ciało K z funkcją zerową, składaniem funkcji (dodawanie) oraz mnożeniem ich przez liczbę z ciała K też jest przestrzenią liniową.
    Definicja
    Jeżeli X jest przestrzenią liniową nad jakimś ciałem, Y jest niepustym podzbiorem X oraz Y też jest przestrzenią liniową nad tym samym ciałem (z tymi samymi działaniami), to mówimy, że Y jest podprzestrzenią (liniową) X.
    Y jest podprzestrzenią liniową X wtedy, i tyle wtedy, gdy:



    Przykłady
    X jest podprzestrzenią liniową X.
    Wielomiany niższego stopnia są podprzestrzenią wielomianów wyższego stopnia, jeżeli są nad tym samym ciałem i są to wyrażenia tych samych zmiennych.
    Kombinacja liniowa
    Niech oraz .
    Wtedy x jest kombinacją liniową wektorów .
    Liniowa zależność
    Układ wektorów jest liniowo zależny wtedy, i tylko wtedy, gdy jeden z nich jest kombinacją liniową pozostałych.
    Bardzo praktyczną obserwacją jest, że układ jest liniowo niezależny, jeżeli suma wtedy, i tylko wtedy, gdy .
    Prawdziwe jest również twierdzenie odwrotne (czyli układ wektorów jest liniowo zależny, jeżeli istnieje taki układ skalarów (z których przynajmniej jeden jest niezerowy), że suma wektorów pomnożonych przez skalary wynosi 0).
    Oznaczenie
    Zbiór wszystkich kombinacji liniowych układu wektorów oznaczamy . Czasami zamiast słowa span używa się lin.
    Uwaga
    Jeżeli , to jest podprzestrzenią X.
    Rozpinanie przestrzeni
    Jeżeli X jest przestrzenią liniową w której zawiera się i , to mówimy, że przestrzeń X jest rozpięta przez ten układ wektorów (lub, że ten układ wektorów rozpina przestrzeń X).
    Baza przestrzeni liniowej
    Układ wektorów nazwiemy bazą, jeżeli jest to układ liniowo niezależny oraz rozpina daną przestrzeń.
    Wymiarem przestrzeni liniowej nazywamy liczbę jej wektorów bazowych i oznaczamy słowem dim.
    Przykładowe zadanie dla czytelników: sprawdź, czy układ jest bazą .
    Jak zawsze zachęcam do zadawania pytań.
  13. Hakken
    Abstrakt
    Wielomiany to wyrażenia powstałe z połączenia zmiennych i stałych. Są bardzo popularne, ponieważ łatwo obliczać ich wartość a także wykonywać inne operacje.
    Wielomiany
    Wielomianem nazywamy funkcję/wyrażenie postaci , gdzie x jest zmienną, a to współczynniki.
    Jeżeli wielomian n-tego stopnia ma m () pierwiastków, to możemy go zapisać jako to pierwiastki tego wielomianu, a wielomian R to reszta.
    Oznaczenie
    Zbiór wielomianów o współczynnikach w ciele co najwyżej n-tego stopnia zmiennej x będziemy oznaczać przez .
    Pierwiastkiem wielomianu nazwiemy taki argument, dla którego wartość wielomianu wynosi 0.
    Dowolny wielomian (którego dziedziną jest pierścień całkowity - dodaję to pro forma, gdyż dla tego tekstu nie będzie to miało znaczenia) n-tego stopnia ma co najwyżej n pierwiastków.
    Dodawanie i mnożenie wielomianów
    Wielomiany można bardzo łatwo dodawać, wystarczy dodać współczynniki obu wielomianów przy każdej potędze zmiennej.
    Mnożenie wielomianów jest nieco bardziej pracochłonne, trzeba każdy element z pierwszego wielomianu pomnożyć przez każdy element z drugiego. Należy przy tym pamiętać, że o ile współczynnik mnożymy, to potęgę przy zmiennej dodajemy.
    Dzielenie wielomianów
    Jeżeli mamy dwa wielomiany, i chcemy podzielić jeden przez drugi, to robimy to tak (W(x) będzie wielomianem dzielonym, a P(x) dzielnikiem):
    Porządkujemy wielomiany (zapisujemy oba w porządku malejącym co do potęg zmiennej)
    Dzielimy pierwszy wyraz W(x) przez pierwszy wyraz P(x)
    Otrzymany jednomian mnożymy prez P(x) i odejmujemy od W(x). W taki sposób dostajemy Wielomian R1(x)
    Pierwszy wyraz z R1(x) dzielimy przez pierwszy wyraz P(x)
    Otrzymany jednomian mnożymy przez P(x) i odejmujemy od R1(x). Dostajemy nowy wielomian, R2(x)
    Powtarzamy powyższe kroki do momentu, kiedy otrzymany wielomian R będzie niższego stopnia niż wielomian P. W szczególności jeżeli R będzie równe 0, to znaczy, że wszystkie pierwiastki P są pierwiastkami W.

    Krotność pierwiastków
    Jeżeli jakiś pierwiastek występuje w rozkładzie wielomianu k razy (przy czym k jest liczbą naturalną większą niż 1), to mówimy, że jest to pierwiastek k-krotny.
    Przykłady
    Wielomian ma dwa pierwiastki (1 oraz -3).
    Wielomian nie ma pierwiastków.
    Wielomian ma dwa pierwiastki ($-1 -\imath \sqrt{2} oraz -1 +\imath \sqrt{2}).
    Wielomian ma jeden pierwiastek (1) podwójny.
    Szukanie pierwiastków
    Dla wielomianów stopnia pierwszego pierwiastek łatwo obliczyć.
    Do wyliczenia pierwiastków równania kwadratowego można użyć wyróżnika, oznaczanego (i potocznie nazywanego) deltą.
    Dla równania wyróżnik jest równy .
    Pierwiastki są równe .
    Oczywiście w dziedzinie liczb rzeczywistych nie można wyciągać pierwiastka drugiego stopnia z liczby ujemnej, więc gdzie wyróżnik jest mniejszy niż zero próżno szukać pierwiastków rzeczywistych.
    Dla wielomianów wyższych stopni szukanie pierwiastków jest bardzo (lub przynajmniej dość) uciążliwe.
    Istnieją twierdzenia (np. twierdzenie Sturma) które pozwalają określić gdzie mniej więcej znajdują się pierwiastki.
    Zasadnicze twierdzenie algebry
    Stopień wielomianu zespolonego równy jest liczbie krotności jego pierwiastków (czyli np. wielomian trzeciego stopnia może mieć jeden pierwiastek potrójny, jeden podwójny i jeden zwykły lub trzy zwykłe).
    Dowód tego twierdzenia pozwolę sobie pominąć, bo jest dość trudny i wymaga wiedzy spoza moich wpisów i elementarnej wiedzy.
  14. Hakken
    Przed przeczytaniem tego wpisu polecam zaznajomić się z częścią pierwszą: tutaj.
    Krótkie wprowadzenie do funkcji trygonometrycznych
    W tym wpisie będą potrzebne podstawowe informacje z zakresu funkcji trygonometrycznych, jednak ze względu na ich złożoność nie będę im poświęcał więcej miejsca niż to potrzebne do zrozumienia tego wpisu.
    Weźmy dowolny kąt skierowany i ustawmy go tak, że w środku prostokątnego (kartezjańskiego) układu współrzędnych znajduje się jego wierzchołek, jedno ramie pokrywa się z dodatnią półosią, natomiast drugie ramie jest półprostą o początku w środku układu współrzędnych.
    Obierzmy punkt M o współrzędnych (a,b) taki, że punkt M należy do półprostej wyznaczonej przez ramię kąta (to, które nie leży na dodatniej półosi), i niech r oznacza odległość punktu M od początku układu współrzędnych.
    Ilustracja:
    http://upload.wikime...on_by_angle.svg
    Wtedy

    Dodatkowo

    Reprezentacja graficzna liczb zespolonych
    Liczbę zespoloną można przedstawić na płaszczyźnie zespolonej.
    Wprowadźmy na płaszczyznę prostokątny układ współrzędnych, tak, że jedna oś będzie określała część urojoną (Im z), a druga część rzeczywistą (Re z).
    Wtedy liczbę z przedstawimy odmierzająć wartości a i b na odpowiedznich osiach.
    Przykładowo liczbę przedstawimy tak:

    Gdzie czerwona kropka to nasz punkt, a szara kreska to moduł liczby z.
    Postać trygonometryczna liczby zespolonej
    Jeśli oraz , to niech $\phi$ będzie miarą łukową kąta pomiędzy półosią Re z i modułem z.
    Wtedy widać, że

    A wtedy .
    Jest to postać trygonometryczna liczby z.
    Oznaczenie
    nazywamy argumentem liczby zespolonej z i oznaczamy $arg z =\phi$.
    Jeżeli arguemnt należy do przedziału , to nazwiemy go argumentem głównym i oznaczymy .
    Mnożenie liczb w postaci trygonometrycznej
    Niech

    Wtedy
    Wzór de Moivre'a
    Jeśli , to
    , gdzie n jest liczbą naturalną.
    Dowód pominę, jest to dość nudny (ale niezbyt długi) dowód indukcyjny.
  15. Hakken
    Osoby czytające ten wpis powinny być zaznajomione z pojęciem ciała oraz podstawowymi symbolami i pojęciami matematycznymi. Oba te zagadanienia zostały omówione w moich wpisach (tu i tu).
    Abstrakt
    Liczby zespolone zostały stworzone w celu ułatwienie obliczeń i unormowania sposobu myślenia w przypadku liczb ujemnych.
    Składają się one z dwóch liczb rzeczywistych, stanowiących część rzeczytistą i urojoną.
    Liczby zespolone z działaniami dodawania i mnożenia stanowią ciało.
    Definicja
    Liczbą zespoloną nazywamy uporządkowaną parę liczb rzeczywistych (czyli dwie liczby rzezcywiste, przy czym ich kolejność ma znaczenie).
    Zbiór wszystkich liczb zespolonych oznaczamy przez .
    Liczby zespolone zapisujemy w nawiasie, ja będę stosował nawias okrągły. Przykładowo .
    Działania na zbiorze liczb zespolonych
    Niech
    Dodawania

    Mnożenie


    Tak definiujemy działania na liczbach zespolonych. Jest to jednak sposób absolutnie niepraktyczny i prawie nigdy się tak nie przeprowadza działań.
    Łatwiejsze i bardziej uniwersalne sposoby na przeprowadzanie obliczeń przedstwię za chwilę.
    Najpierw jednak...
    Oznaczenia
    Liczbę zespoloną zapisujemy jako po prostu a.
    Liczbę zespoloną zapisujemy jako . Nazywamy tę liczbę jednostką urojoną.
    Liczbę zespoloną zapisujemy jako
    Liczbę zespoloną zapisujemy jako .

    Obliczamy
    Użyjemy działania rozpisanego wyżej aby obliczyć kwadrat jednostki urojonej.

    Kwadratem jednostki urojonej jest -1
    Bardziej praktyczne działania na zbiorze liczb zespolonych
    Zapisujemy liczby zespolone w postaci sumy dwóch składników (korzystamy z ostatniego punktu oznaczeń), i otrzymujemy

    Dodawanie

    Mnożenie


    Jak widać wyniki wychądzą te same, a nie trzeba pamiętać wzorów, można dodawać więcej liczb naraz itp.
    Oznaczenia
    Niech .
    Wtedy powiemy, że a jest częścią rzeczywistą liczby z, oznaczamy a=Re z.
    Analogicznie b jest częścią urojoną, oznaczamy b=Im z.
    Liczbę nazywamy modułem liczby z, oznaczamy |z|.
    Liczbę nazywamy liczbą sprzężoną do z i oznaczamy .
    Na jeden wpis taka ilość informacji powinna wystarczyć, wkrótce pojawi się część druga, gdzie zajmę się potęgowaniem liczb zespolonych oraz postacią trygonometryczną.
    Zadania
    Jeśli ktoś ma chęć poużywać liczb zespolonych w celu nabycia wprawy w operowaniu nimi, przestawiam kilka prostych równań do sprawdzenia.
    Niech z będzie liczną zespoloną
    suma z i sprzężenia z jest równa części rzeczywistej z pomnożonej przez 2.
    iloraz z i sprzężenia z jest równy modułowi z podniesionemu do kwadratu.
    Liczbą odwrotną do (niezerowego) z jest iloraz sprzężenia z przez kwadrat modułu z liczby z.

    Przepraszam, że zadania w formie słownej, ale już przekroczyłem limit liczby wstawionych obrazków.
    Jako ambitniejsze zadanie pozostawiam udowodnienie twierdzenia: Liczby zespolone wraz z działaniami dodawania i mnożenia, gdzie elementami neutralnymi są 0 i 1 tworzą ciało.
    Podpowiedź w spoilerze:
    W przypadku niejasności, uwag, pytań (również do zadań!) zachęcam do komentowania.
  16. Hakken
    Uwaga!
    Jeśli jest przestrzenią metryczną zupełną (czyli taką przestrzenią metryczną, że każdy ciąg Cauchy'ego określony na niej ma granicę w rzeczonej przestrzeni), natomiast jest kontrakcją, to
    f ma dokładnie jeden punkt stały x0


    Dowód:
    Z nierówności trójkąta mamy, że

    To z kolei można ograniczyć z góry przez
    .
    Z tego otrzymujemy

    Wprawny obserwator zauważy, że jeśli zarówno jak i są punktami stałymi, to , czyli x=y, co dowodzi, że jest tylko jeden punkt stały.
    Teraz przyjmijmy, że Tn to n-krotne złożenie T ze sobą.
    Pozostaje więc pokazać, że jest ciągiem Cauchy'ego oraz, że jest on zbieżny do , który jest punktem stałym w .
    Zastąpmy więc w naszym równaniy x przez , a y przez :
    , co można ograniczyć z góry przez , a to można zapisać jako

    Wiemy, że oraz, że , więc jest ciągiem Cauchy'ego, co kończy dowód.
  17. Hakken
    Uwaga!
    Porządek ciągły
    Niech $(A,\leq)$ będzie porządkiem liniowym, czyli relac ją $\zeta$ częściowego porządku, która do tego jest łańcuchem, czyli spełnia następujące warunki:
    Zwrtoność
    $\forall a\in A (a,a)\in\zeta$
    Przechodniość
    $\forall a,b,c\in A \ \ \ ((a,b)\in\zeta \wedge (b,c)\in\zeta) \Rightarrow (a,c)\in\zeta$
    Antysymetria
    $\forall a,b\in A \ \ \ ((a,b)\in\zeta \wedge (b,a)\in\zeta) \Rightarrow (a=b)$
    Spójność
    $\forall a,b\in A \ \ \ ((x\leq y) \vee (y\leq x))$

    Powiemy, że $(A,\leq)$ jest porządkiem ciągłym jeżeli oprócz tego, że jest porządkiem liniowym (czyli spełnia powyższe warunki) jest dodatkowo:
    Gęsty
    $\forall a,b\in A \ \ \ (a\leq b \Rightarrow (\exists c\in A: a\leq c\leq b)$
    Każdy niepusty ograniczony z góry zbiór $B\subseteq A$ ma kres górny w $A$
    $sup B \in A$
    Każdy niepusty ograniczony z dołu zbiór $C\subseteq A$ ma kres dolny w $A$
    $inf C \in A$

    Przykładem prządku ciągłego jest $(\mathbb R, \leq)$, ale już $(\mathbb N, \leq)$ nie, bo nie jest spełniony warunek gęstości (nie ma żadnej liczby $x\in N$ takiej, że $4 \leq x \leq 5$).
    Można więc łatwo stwierdzić, że aby $(A,\leq)$ było porządkiem ciągłym, to moc $A$ musi być równa przynajmniej $\aleph_0$, bo inaczej nie będzie spełniony warunek gęstości.
    Ciągłość funkcji
    Również funkcja może być ciągła:
    Niech $(X,\tau_X), \ \ \ (Y,\tau_Y)$ będą przestrzeniami topologicznymi z przekształceniem $f: X \rightarrow Y$.
    Powiemy, że $f$ jest ciągłe, jeśli
    $\forall V\in \tau_Y \ \ \ f^{-1}(V)\in \tau_X$
    Przeciwobraz zbioru domkniętego jest domknięty

    Definicja Cauchy'ego
    W szczególności dla funkcji rzeczywistych $(R\subseteq \mathbb R) \ \ \ f: R \rightarrow \mathbb R$ możemy mówić o ciągłości w punkcie oraz o ciągłości na zbiorze $R$.
    Niech $x\in R$.
    Jeśli $\forall \varepsilon >0 \ \ \exists \sigma >0 \ \ \forall y\in R \ \ \ |x-y|<\sigma \Rightarrow |f(x)-f(y)|<\varepsilon$, to $f$ jest ciągła w punkcie $x$.
    Jeśli warunek ten zachodzi dla każdego $x\in R$, czyli
    $\forall x\in R \ \ \forall \varepsilon >0 \ \ \exists \sigma >0 \ \ \forall y\in R \ \ \ |x-y|<\sigma \Rightarrow |f(x)-f(y)|<\varepsilon$, to $f$ jest ciągła na $R$.
    Twierdzenie Darboux
    Jeśli obraz $f: \mathbb R \rightarrow \mathbb R$ każdego przedziału jest przedziałem, to $f$ ma własność Darboux.
    W szczególność dla $f$ ciągłego przyjmijmy, że $x<y, \ \ \ x,y\in \mathbb R$$ z faktu, że $f$ jest ciągła wynika, że w obrazie $f$ zawarty jest cały przedział $[f(x),f(y)]$ (lub $[f(y),f(x)]$), co w szczególności daje nam bardzo przydatne twierdzenie:
    Dla funkcji ciągłej $f:[a,b] \rightarrow \mathbb R$ z faktu, że $f(a) x f(b) <0$ wynika, że $\exists d\in [a,b]: \ \ \ f(d)=0$
    Każda funkcja ciągła ma własność Darboux.
    Dowód:
    Załóżmy, że $f(a)<f(b)$. Wtedy niech $x=sup\{y\in [a,b]: \ f(y)\leq c\}$.
    Wiemy, że $x\in [a,b]$, a więc z faktu, że $f$ jest funkcją ciągłą mamy, że $f(x) \leq c$.
    Załóżmy, że $f(x) \neq c$, a więc $0<\varepsilon<min\{x-a,b-x\}$ dla pewnego $\varepsilon$.
    Wynika z tego, że $f(v)<d$ jeżeli $|v-x|<\varepsilon$, czyli, że $f(x+\frac{\varepsilon}{2})<c$. Ale $x<x+\frac{\varepsilon}{2}$, podczas gdy $x$ jest supremum, co daje nam sprzeczność. Teza jest więc prawdziwa.
    Jak zawsze zachęcam do zadawania pytań.
  18. Hakken
    Uwaga!
    Doszło do mnie, że nie wszyscy pamiętają (albo nigdy się nie dowiedzieli) jakie oznaczenia stosuje się w matematyce (nie tylko wyższej).
    Przedstawię więc dzisiaj podstawowe symbole, oznaczenia i elementy tak, aby każdy mógł zrozumieć moje poprzednie i przyszłe wpisy.

    Kwantyfikatory
    Są dwa kwantyfikatory, tzw. ogólny i egzystencjonalny (szczególny, szczegółowy).
    Kwantyfikator ogólny $\forall$ wygląda jak odwrócona litera 'A', od angielskiego "(for) all" (nie bez powodu, dawniej pisało się dokument a następnie odwracało kartkę i dopiyswało się kwantyfikatory. Było to w czasach maszyn do pisania ).
    Oznacza on "dla każdego". Np. $\forall x zachodzi cośtam$ czytamy "dla każdego x zachodzi cośtam$.
    Kwantyfikator egzystenchonalny $\exists$ wygląda jak lustrzane odbicie litery 'E', od angieslkiego słowa "exists" i oznacza, że jakiś element istnieje.
    $\exists x cośtam$ czytamy "istnieje taki x, że zachodzi cośtam".
    Zbiory
    Zbiór jest pojęciem pierwotnym, nie posiada więc definicji. Jest to po prostu pewne ugrupowanie elementów. W zbiorze nie ma kolejności, większości, powtórzeń itp. są tylko elementy.
    Zbiory określamy na kilka sposobów, np. przez wypisanie wartości. $A=\{1,2,3\}$ - w ten sposób określiłem zbiór $A$, który ma trzy elementy ($1,2,3$).
    Symobl $\in$ oznacza, że jakiś element należy do zbioru, np. prawdziwe jest stwierdzenie, że $2\in A$, ale już nieprawdą jest, że $5\in A$, czyli $5\notin A$.
    Możemy też ustalić zbiór przez warunek, przykładowo $P=\{x\in \mathbb N: \frac{x}{2} \in \mathbb N\}$.
    Przeczytajmy to co napisałem: "P to zbiór takich liczb naturalnych x, że wynik dzielenia x przez 2 należy do liczb naturalnych" (czym są liczby naturalne napisałem niżej).
    Wnikliwy obserwator zauważy, że w ten sposób zdefiniowałem zbiór liczb parzystych.
    Na zbiorach możemy przeprowadzać działania.
    Dodawanie oznazcamy $\cup$ Zbiór powstały z dodania dwóch zbiorów, to zbiór zawierający elementy pierwszego i drugiego zbioru (i nic więcej), przykładowo $A=\{1,2,3\}$, $B={2,3,4}$, $A\cup B=\{1,2,3,4\}$.
    Iloraz oznaczamy $\cap$. Jest to część wspólna zbiorów, czyli dla $A,B$ jak wyżej $A\cap B=\{2,3\}$.
    Odejmowanie zbiorów oznaczamy - lub \. Dla $A,B$ jak wyżej $A-B=\{1\}$.
    Zbiór pusty to zbiór niezawierający żadnego elementu, oznaczamy go $\emptyset$. $\forall x x\notin \emptyset$
    Podzbiory
    Mówimy, że B jest podzbiorem A (oznaczamy $B\subset A$), jeśli każdy element z B zawiera się w A, czyli
    $\forall x \ \ \ x\in B \Rightarrow x\in A$
    Zbiory liczbowe
    $\mathbb N$ to liczby naturalne, czyli $0,1,2,3,...$ i tak dalej.
    $\mathbb Q$ to liczby wymierne, czyli takie ułamki, które można zapisać jako $\frac{a}{b}$, gdzie $a,b\in \mathbb N$.
    $\mathbb R$ to liczby rzeczywiste. Definiujemy je jako wszystkie możliwe granice ciągów liczb wymiernych. Intuicyjnie są to zwyczajne liczby, takie jak 5, 12.4, 15325.512346 itp.

    Proszę się nie bać zadawać pytania w komentarzach.
  19. Hakken
    Uwaga!
    Zajmiemy się dzisiaj ciałami.
    Ciało jest specjalnym przypadkiem pierścienia (konkretnie jest to pierścien przemienny taki, że każdy element niezerowy ma swój element odwrotny). Samymi pierścieniami jednak zajmować się nie będziemy.
    Ciała
    $(K,+,\cdot,1,0)$ nazwiemy ciałem, jeżeli K jest przynajmniej dwuelementowym zbiorem zawierającym $0$ i $1$, $+$ oraz $\cdot$ są działaniami binarnymi (czyli funkcjami $+:K\rightarrow K$, $\cdot:K\rightarrow K$) oraz spełnione są następujące warunki (od teraz działanie $+$ nazywać będziemy dodawaniem, a $\cdot$ - mnożeniem):

    $(K,+,0)$ jest grupą abelową z neutralnym elementem $0$ (pisałem o tym więcej w poprzednim wpisie, dla przypomnienia):
    $\forall x,y\in K \ \ \ x+y=y+x$
    $\forall x\in K x+0=x$
    $(K-\{0\},\cdot,1)$ jest grupą abelową (z elementem neutralnym $1$):
    $\forall x,y\in K \ \ \ x\cdot y=y\cdot x$
    $\forall x\in K \ \ \ x\cdot 1=x$
    Zachodzi rozdzielność dodawania względem mnożenia:
    $\forall a,b,c\in K \ \ \ (a+b)\cdot c=a\cdot c + b\cdot c$

    Przykłady ciał

    Liczby rzeczywiste z działanimi mnożenia i dodawania oraz elementami neutralnymi 0 i 1
    Liczby wymierne z działaniami i elementami neutralnymi jak wyżej

    Podciała
    Jeżeli $(X,+,\cdot,0,1)$ jest ciałem, a $Y\subset X$ oraz $0,1\in Y$, oraz jeżeli $(Y,+,\cdot,0,1)$ też jest ciałem, to Y jest podciałem ciała X.
  20. Hakken
    Uwaga!
    Niech $G$ będzie niepustym zbiorem, a $\diamond$ działaniem na nim, czyli funkcją $\diamond: G \times G \rightarrow G$.
    Mamy w takiej sytuacji doczynienia z grupoidem.
    Jeśli dodatkowo działanie $\diamond$ będzie łączne, czyli
    $\forall a,b,c\in G \ \ \ (a\diamond b)\diamond c= a\diamond(b\diamond c)$
    To strukturę taką nazwiemy półgrupą.
    Półgrupa z elementem neutralnym, czyli takim elementem $e\in G$, że
    $\forall a\in G \ \ \ e\diamond a=a\diamond e=a$
    nazywana jest monoidem.
    Jeśli dodatkowo każdy element ma swój element przeciwny, to znaczy
    $\forall a\in G \ \exists b\in G \ \ \ a\diamond b=b\diamond a=e$
    to strukturę taką nazwiemy grupą.
    Grupa w której działanie $\diamond$ jest przemienne, czyli
    $\forall a,b\in G \ \ \ a\diamond b=b\diamond a$
    nazywamy grupą abelową, lub po prostu przemienną.
    Można również mówić o takich strukturach jak lupa czy quasi-grupa.
    Quasi-grupa to struktura $(G,\diamond)$ taka, że każdy element ma element przeciwny (ale nie ma elementu neutralnego, a działanie $\diamond$ nie jest łączne!).
    Lupa natomiast to quasi-grupa, ale z elementem neutralnym (działanie $\diamond$ wciąż nie jest łączne).
    Przykładem grupy są liczby całkowite z działaniem dodawania, gdzie elementem neutralnym jest $0$, a przeciwnym do $x$ jest $-x$.
    Warto zauważyć, że każdy element z grupy ma dokładnie jeden element odwrotny, i jest to element zarówno lewo- jak i prawostronnie odwrotny.
    Dowód:
    Niech $x,y,z\in G$ oraz niech $x\diamond y=e$ i $y\diamond z=e$.
    Wtedy $z=e\diamond z=(x\diamond y)\diamond z=x\diamond (y\diamond z)=x\diamond e=x$.
    Widać więc, że $z=x$, czyli element prawostronnie odwrotny równy jest elementowi lewostronnie odwrotnemu.
    Niech teraz $x\in G$ oraz $y,y'\in G$ takie, że $x\diamond y=x\diamond y'=e$.
    Wtedy $y'=e\diamond y'=(x\diamond y)\diamond y'=y\diamond (x\diamond y')=y\diamond e=e$
    Z czego mamy, że $y'=y$, a więc element odwrotny jest tylko jeden.
    Można równie łatwo pokazać, że jeśli $x,y,z\in G$ oraz $x\diamond y=z\diamond y$, to $x=y$. Nie będę tego jednak tutaj dowodził, jeśli ktoś chce to może spróbować, nie jest to trudne.
×
×
  • Utwórz nowe...