drzewa

Tym razem coś dla młodszych czytelników bloga, chociaż pewnie nie tylko ich może to zainteresować. Zbliża się maj, a skoro maj, to matury, w tym ta z informatyki. Pomyślałem, że może Was zaciekawić, jak osoba pracująca od kilku lat w IT rozwiązałaby zadania, które pojawiły się na maturze próbnej w grudniu 2022 roku.

Wiemy, czym są grafy, a także jak zapisujemy je w pamięci komputera. Przejdźmy w takim razie do najbardziej podstawowych algorytmów grafowych — przechodzenie po ich wierzchołkach i krawędziach. Jest to zdecydowanie najprostszy i najbardziej podstawowy temat algorytmiczny związany z grafami, więc opiszę go dość zwięźle.

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.

Poprzednio w serii algorytmika gier pochyliłem się nad grą w sapera, gdzie przeanalizowaliśmy, jak generuje się planszę oraz prowadzi rozgrywkę. Teraz spróbujmy przenieść na komputer jedną z najpopularniejszych gier rozgrywanych na kartce — kółko i krzyżyk. Jednak tym razem nie skupimy się na zaprogramowaniu całej rozgrywki, a tylko na jednej rzeczy: sztucznej inteligencji komputerowego gracza.

W ciągu sześciu ostatnich artykułów o sortowaniu opisałem najbardziej znane podejścia do sortowania oraz kilka wywodzących się od nich. Algorytmów sortowania jest jednak bardzo wiele i nie byłem w stanie omówić wszystkich tych, które planowałem. W tym artykule opisuję trzy algorytmy, które miały znaleźć się wcześniej na blogu, jednak z różnych powodów odłożyłem je na później — sortowanie odd-even, gnoma oraz drzewiaste.

Po sortowaniu bąbelkowym i sortowaniu przez wstawianie nadszedł czas na omówienie ostatniego z tak zwanych prostych podejść do sortowania. Tym razem elementów nie będziemy zamieniać czy wstawiać, tylko wybierać. A co to dokładnie oznacza? Więcej w artykule.