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 k
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 tu
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 dowolne
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 (neutra
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ę dogad
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
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ł
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 On
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 podprze
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 wie
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
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 elem
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
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
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ą
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 t
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ę
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 t
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 dodatkow
