świstak.codes

O programowaniu, informatyce i matematyce przystępnym językiem

Autor: Tomasz Świstak

Rysowanie grafów — algorytmy

Mówiąc o grafach w kontekście algorytmiki, zwykle przywodzi na myśl rozwiązywanie za ich pomocą różnych problemów, np. poruszanego przeze mnie już w trzech artykułach szukania ścieżek. Rzadziej jednak porusza się temat tego, że jeśli chcemy graf narysować, należałoby rozmieścić jego wierzchołki w przestrzeni w pewien sensowny i uporządkowany sposób tak, aby jak najlepiej przedstawić jego charakterystykę. Znajomość przynajmniej rodzajów i właściwości algorytmów do tego służących to obowiązkowa wiedza dla osób zajmujących się wizualizacją danych. W artykule przedstawiam wszystko, co potrzebujesz wiedzieć na ten temat.

Czytaj więcej

Szybkie wyszukiwanie ścieżek

Klasyką algorytmiki jest wykorzystywanie takich algorytmów, jak BFS, algorytm Dijkstry czy Bellmana-Forda do wyszukiwania najkrótszych ścieżek. Jednak algorytmy te wykonują bardzo dużo operacji i przy rozbudowanych przypadkach, takich jak znajdowanie tras na mapie albo nawet ścieżki, po której ma przejść postać w grze komputerowej, mogą być zbyt wolne czy też zająć zbyt dużo pamięci. Na szczęście są również inne podejścia do tego problemu, dużo wydajniejsze, jeśli posiadamy nieco więcej informacji o grafie. Czas najwyższy poznać jedno z nich — algorytm A*.

Czytaj więcej

Praktyczne zastosowania przechodzenia po grafie

W artykule „Przechodzenie po grafie” przedstawiłem algorytmy służące do przechodzenia po węzłach grafu — DFS (przechodzenie w głąb) oraz BFS (przechodzenie wszerz). Jednak samo odwiedzanie węzłów może wydawać się na pierwszy rzut oka mało przydatne, dlatego przedstawię trzy sposoby, jak można wykorzystać te algorytmy do celów praktycznych. Użyjemy też wszystkie trzy pokazane tam sposoby przechodzenia grafu: rekurencyjny DFS, iteracyjny DFS oraz BFS.

Czytaj więcej

Grafy — wprowadzenie

Grafy to jedna z najważniejszych koncepcji matematycznych, które na stałe weszły do świata informatyki. Wielu programistów może nie dostrzegać tego na pierwszy rzut oka, ale znajdziemy je niemal wszędzie. Warto wiedzieć, czym one są i jak działają, niezależnie od tego, czym w świecie IT się zajmujemy. Jest to też temat dość mi bliski, bo zawodowo mam do czynienia z praktycznym zastosowaniem grafów od dłuższego czasu. W tym wpisie opisuję je od strony teoretycznej, aby przedstawić, czym są, skąd się wzięły i przede wszystkim, jakie znalazły zastosowania. Na początku nie przedstawię całej teorii grafów, tylko moim zdaniem jej najważniejsze elementy.

Czytaj więcej

Duże liczby pierwsze

Do tej pory przedstawiłem, czym są liczby pierwsze, ich zastosowania, jak możemy sprawdzać pierwszość liczb oraz jak możemy prostymi sposobami znajdować je. Jednak wszystko to, co do tej pory opowiedzieliśmy sobie, jest w dużej mierze zabawą. Jak poruszyłem już na samym początku serii, w kryptografii wykorzystuje się liczby pierwsze 2048-bitowe, więc w systemie dziesiętnym mogą one mieć nawet 617 cyfr. Dowiedzmy się więcej, jak jesteśmy w stanie odkryć tak duże, a nawet i większe liczby pierwsze. Na razie tylko w teorii.

Czytaj więcej