Sortowanie bąbelkowe (Bubble Sort)
1. Co to jest sortowanie bąbelkowe?
Sortowanie bąbelkowe to jeden z najprostszych sposobów sortowania danych. Polega na ustawianiu elementów w odpowiedniej kolejności, na przykład od najmniejszej do największej liczby lub odwrotnie.
Jego nazwa pochodzi od sposobu działania – większe liczby stopniowo przesuwają się na koniec listy, podobnie jak bąbelki powietrza unoszące się w wodzie.
2. Do czego służy?
Sortowanie bąbelkowe służy do porządkowania różnych danych, takich jak:
-
Liczby od najmniejszej do największej.
-
Liczby od największej do najmniejszej.
-
Nazwy w kolejności alfabetycznej.
-
Wyniki uczniów od najniższego do najwyższego.
-
Różne wartości znajdujące się na liście.
Jest wykorzystywane głównie do nauki podstaw informatyki i działania algorytmów.
3. Jak działa sortowanie bąbelkowe?
Algorytm porównuje ze sobą dwie sąsiadujące liczby. Jeżeli są ustawione w złej kolejności, zamienia je miejscami.
Następnie przechodzi do kolejnej pary liczb i wykonuje tę samą czynność. Powtarza cały proces tak długo, aż wszystkie elementy będą prawidłowo uporządkowane.
Przykładowy kod w pythonie:
4. Zalety i wady
Zalety:
-
Jest prosty do zrozumienia.
-
Łatwo nauczyć się jego działania.
-
Nie wymaga dodatkowej pamięci.
Wady:
-
Jest powolny przy dużej liczbie elementów.
-
Wykonuje dużo porównań.
-
Istnieją szybsze algorytmy sortowania.
1. Cyberbezpieczeństwo
Cyberbezpieczeństwo to zbiór działań, metod, zasad i technologii służących ochronie komputerów, urządzeń, sieci, systemów informatycznych oraz przechowywanych w nich danych przed nieautoryzowanym dostępem, wykorzystaniem, modyfikacją, uszkodzeniem lub zniszczeniem. Jednym z podstawowych celów cyberbezpieczeństwa jest zapewnienie poufności, integralności i dostępności informacji.
Najważniejsze zagrożenia
Phishing
Phishing to forma oszustwa wykorzystująca socjotechnikę. Polega na podszywaniu się pod zaufaną osobę, firmę lub instytucję w celu nakłonienia użytkownika do ujawnienia poufnych informacji, takich jak hasła, dane osobowe czy dane bankowe. Atak może odbywać się za pośrednictwem wiadomości e-mail, komunikatorów, wiadomości SMS lub fałszywych stron internetowych.
Złośliwe oprogramowanie
Złośliwe oprogramowanie (malware) to programy stworzone w celu uzyskania nieuprawnionego dostępu do urządzenia, kradzieży danych, zakłócenia działania systemu lub wykonania innych szkodliwych działań. Do przykładów należą wirusy, konie trojańskie, programy szpiegujące oraz ransomware.
Ataki na systemy i sieci
Ataki cybernetyczne mogą polegać na próbach uzyskania nieautoryzowanego dostępu do komputerów, serwerów, kont użytkowników lub sieci. Ich celem może być kradzież informacji, przejęcie kontroli nad systemem, zakłócenie jego działania lub spowodowanie utraty danych.
Kradzież danych uwierzytelniających
Przejęcie haseł i innych danych logowania może prowadzić do uzyskania dostępu do poczty elektronicznej, mediów społecznościowych, systemów szkolnych, bankowości internetowej lub innych usług. Ryzyko zwiększa stosowanie tego samego hasła w wielu serwisach.
Jak dbać o bezpieczeństwo?
Stosować silne i unikalne hasła dla poszczególnych kont.
Korzystać z uwierzytelniania wieloskładnikowego (MFA), które wymaga zastosowania co najmniej dwóch różnych czynników uwierzytelniania, np. hasła oraz kodu lub urządzenia.
Regularnie aktualizować system operacyjny, aplikacje i oprogramowanie zabezpieczające.
Zachować ostrożność podczas otwierania linków i załączników pochodzących z nieznanych lub podejrzanych źródeł.
Korzystać z oprogramowania antywirusowego i zapory sieciowej.
Regularnie wykonywać kopie zapasowe ważnych danych.
Nie udostępniać innym osobom haseł, kodów uwierzytelniających ani innych poufnych informacji.
Sprawdzać adresy stron internetowych i nadawcę wiadomości przed podaniem jakichkolwiek danych.
2. Algorytm Grahama
Algorytm Grahama (Graham scan) to algorytm z dziedziny geometrii obliczeniowej służący do wyznaczania otoczki wypukłej zbioru punktów na płaszczyźnie. Algorytm został przedstawiony przez Ronalda L. Grahama w 1972 roku.
Czym jest otoczka wypukła?
Otoczka wypukła to najmniejszy wypukły wielokąt zawierający wszystkie analizowane punkty. Można ją porównać do elastycznej gumki rozciągniętej wokół zbioru punktów — punkty znajdujące się wewnątrz nie wpływają na kształt końcowej otoczki.
Jak działa algorytm?
Algorytm Grahama można przedstawić w kilku podstawowych krokach:
Wybór punktu bazowego
Spośród wszystkich punktów wybierany jest punkt o najmniejszej współrzędnej Y. Jeżeli kilka punktów ma taką samą współrzędną Y, wybiera się ten o najmniejszej współrzędnej X.Sortowanie punktów
Pozostałe punkty są sortowane według kąta względem wybranego punktu bazowego. W przypadku takich samych kątów można wykorzystać odległość od punktu bazowego do rozstrzygnięcia kolejności.Budowanie otoczki
Punkty są kolejno dodawane do stosu reprezentującego aktualną otoczkę.Sprawdzanie kierunku skrętu
Dla każdych trzech kolejnych punktów sprawdzane jest, czy tworzą skręt w odpowiednim kierunku. Jeżeli środkowy punkt nie należy do otoczki wypukłej, zostaje usunięty.Otrzymanie wyniku
Po przetworzeniu wszystkich punktów stos zawiera punkty tworzące otoczkę wypukłą.
Złożoność obliczeniowa
Najbardziej czasochłonnym etapem algorytmu jest sortowanie punktów, które zajmuje:
O(n log n)
Pozostałe etapy mają łącznie liniową złożoność względem liczby punktów. W rezultacie całkowita złożoność algorytmu Grahama wynosi:
O(n log n)
Zastosowania
Algorytmy wyznaczania otoczki wypukłej znajdują zastosowanie m.in. w:
grafice komputerowej,
robotyce,
systemach informacji geograficznej (GIS),
analizie danych przestrzennych,
przetwarzaniu obrazów,
geometrii obliczeniowej.
Algorytm Grahama jest przykładem efektywnego algorytmu, w którym odpowiednie uporządkowanie danych pozwala na szybkie rozwiązanie problemu geometrycznego.
Algorytm – definicja i przecięcie dwóch odcinków
1. Czym jest algorytm?
Algorytm to uporządkowany ciąg jasno określonych czynności, które należy wykonać, aby rozwiązać dany problem lub osiągnąć określony cel. Każdy krok algorytmu powinien być dokładnie opisany i możliwy do wykonania.
Algorytm można porównać do przepisu kulinarnego – aby uzyskać odpowiedni efekt, trzeba wykonać wszystkie czynności we właściwej kolejności.
Algorytmy są wykorzystywane zarówno przez ludzi, jak i komputery. W informatyce stanowią podstawę programowania, ponieważ pozwalają komputerowi wykonywać zadania, analizować dane i rozwiązywać problemy.
2. Przecięcie dwóch odcinków
Przecięcie dwóch odcinków to zagadnienie matematyczne i informatyczne polegające na sprawdzeniu, czy dwa odcinki znajdujące się na płaszczyźnie mają ze sobą przynajmniej jeden wspólny punkt.
Możliwe są trzy sytuacje:
Odcinki przecinają się – mają jeden wspólny punkt.
Odcinki nie przecinają się – nie mają żadnego wspólnego punktu.
Odcinki nakładają się – leżą na tej samej prostej i mają więcej niż jeden wspólny punkt.
Do rozwiązania tego problemu wykorzystuje się współrzędne punktów określających końce obu odcinków.
3. Jak działa algorytm przecięcia dwóch odcinków?
Algorytm sprawdza wzajemne położenie dwóch odcinków na płaszczyźnie. W tym celu analizuje współrzędne ich końców i wykonuje odpowiednie obliczenia matematyczne.
Cały proces można podzielić na kilka etapów:
Pobranie danych – odczytanie współrzędnych czterech punktów, które wyznaczają dwa odcinki.
Sprawdzenie położenia punktów – określenie, po której stronie prostej znajduje się dany punkt.
Porównanie wyników – sprawdzenie, czy odcinki znajdują się po przeciwnych stronach swoich prostych.
Sprawdzenie szczególnych przypadków – uwzględnienie sytuacji, w której punkty leżą na jednej prostej, a odcinki mogą się stykać lub nakładać.
Wyświetlenie wyniku – określenie, czy odcinki mają wspólny punkt.
4. Orientacja trzech punktów
Orientacja trzech punktów to metoda matematyczna pozwalająca określić wzajemne położenie trzech punktów na płaszczyźnie.
Dzięki niej można sprawdzić, po której stronie prostej wyznaczonej przez dwa pierwsze punkty znajduje się trzeci punkt.
Wynik sprawdzenia może oznaczać:
Wynik dodatni – trzeci punkt znajduje się po jednej stronie prostej.
Wynik ujemny – trzeci punkt znajduje się po przeciwnej stronie prostej.
Wynik równy zero – wszystkie trzy punkty leżą na jednej prostej.
Orientacja jest bardzo ważna w algorytmie przecięcia dwóch odcinków, ponieważ pozwala określić, czy odcinki mogą się ze sobą przecinać.
5. Szczególne przypadki przecięcia odcinków
Podczas sprawdzania przecięcia odcinków należy uwzględnić również sytuacje, w których punkty leżą na jednej prostej.
Może wtedy wystąpić kilka przypadków:
Jeden odcinek może kończyć się dokładnie w miejscu, w którym zaczyna się drugi.
Odcinki mogą częściowo na siebie nachodzić.
Jeden odcinek może znajdować się całkowicie wewnątrz drugiego.
Odcinki mogą leżeć na tej samej prostej, ale nie mieć wspólnego fragmentu.
Samo sprawdzenie, czy punkty leżą na jednej prostej, nie wystarcza. Trzeba również ustalić, czy znajdują się w granicach danego odcinka.
6. Zastosowanie algorytmu
Algorytm przecięcia dwóch odcinków ma wiele praktycznych zastosowań w informatyce, matematyce i grafice komputerowej.
Wykorzystuje się go między innymi w:
Grafice komputerowej – do sprawdzania, czy linie i obiekty na ekranie przecinają się.
Grach komputerowych – do wykrywania kontaktu obiektów i sprawdzania ich położenia.
Projektowaniu map – do analizowania przebiegu dróg i innych elementów.
Geometrii obliczeniowej – do rozwiązywania problemów związanych z położeniem figur i punktów.
Programowaniu – do tworzenia algorytmów analizujących położenie obiektów na płaszczyźnie.
7. Złożoność obliczeniowa
Złożoność obliczeniowa określa, ile czasu lub zasobów komputer potrzebuje na wykonanie danego algorytmu.
Algorytm przecięcia dwóch odcinków ma złożoność O(1), czyli stałą. Oznacza to, że wykonuje określoną liczbę operacji niezależnie od wielkości danych wejściowych.