javascript

Podstawową funkcją w aplikacjach, gdzie pozwalamy użytkownikom na edycję czegokolwiek, jest możliwość cofania i ponawiania zmian, nieraz nazywana u nas z angielskiego „undo-redo”. Każdy kto miał okazję programować wie, że wbrew pozorom nie jest to prosty i oczywisty temat. Zobaczmy, jakie są podejścia do implementacji.

Szukanie największego lub najmniejszego elementu w zbiorze danych to jedno z najprostszych zadań algorytmicznych, które implementował zapewne każdy, kto miał styczność z programowaniem. Jednak co zrobić, gdy chcemy znaleźć drugi z kolei największy element? A może trzeci najmniejszy? Albo może po prostu k-ty element? Czy da się to zrobić bez wcześniejszego posortowania zbioru? Nazywamy to problemem selekcji i przyjrzymy się mu w tym artykule.

Niemal 4 lata temu na blogu opublikowałem artykuł „Podstawowe operacje na barwach”, gdzie opisałem, w jaki sposób przekonwertować obraz na skalę szarości, zmienić jasność, kontrast, wykonać korekcję gamma, a także wykonać inwersję barw (czyli konwersję do negatywu). Powróćmy do tej tematyki i omówmy kolejną wartą uwagi i przydatną operację: znajdowanie dominującej barwy w obrazie.

W informatyce bardzo często spotykamy się z pojęciem losowości. Generujemy losowe liczby (w tym pierwsze), losowe dane. Wymieniając bardziej szczegółowo, mamy losowe identyfikatory, losowy stan gier, losowe przeszukiwanie przestrzeni rozwiązań. Przykładów można wymieniać wiele, tylko odpowiedzmy sobie na kluczowe pytanie — jak w ogóle komputer losuje? Czy komputer jest w stanie wygenerować coś, co jest naprawdę losowe?

W aplikacjach graficznych jedną z dostępnych funkcji jest możliwość skorygowania perspektywy wykonanego zdjęcia. Zwykle jest to w bardzo prostej formie, gdzie korygujemy perspektywę do „wyprostowania” zdjęcia. Możliwe, że spotkałeś(-aś) się z tym w aplikacjach mobilnych, gdzie po zrobieniu zdjęcia kartki z tekstem aplikacja sama wyprostuje zdjęcie. Robienie czegoś takiego (aczkolwiek bez wykrycia położenia kartki) jest przedmiotem tego artykułu. Zrozummy temat z punktu widzenia matematyki, a następnie zaimplementujmy wszystko od zera. Aczkolwiek po drodze wskażę też, gdzie można znaleźć gotowe rozwiązania.

Już dawno niczego nie rysowaliśmy na blogu, czyż nie? Powróćmy więc do tej przyjemnej serii i zobaczmy, w jaki sposób algorytmicznie rysować kolejną rzecz. Tym razem częściowo w klimacie zbliżających się świąt — porysujmy gwiazdy. A to dlatego, że kryje się za tym prosta, ale ciekawa matematyka i algorytmika.

Opowiadając do tej pory o problemie komiwojażera (TSP), pokazałem, w jaki sposób możemy bardzo powoli znajdować optymalne rozwiązanie i jak zadowalające (nieco szybciej), korzystając z heurystyk. Wszystko to były sposoby stworzone typowo pod problem komiwojażera i nie da się ich przełożyć na inne problemy obliczeniowe. Mamy jednak całą klasę algorytmów metaheurystycznych, które możemy wykorzystać do dowolnych, trudnych obliczeniowo problemów. Poznajmy przykładowe, dalej zostając w uniwersum TSP.

Opisując ostatnio problem komiwojażera, pokazałem sposoby, jak możemy otrzymać optymalne rozwiązanie. Niestety, co było widać na przykładach załączonych w artykule, algorytmy te były bardzo wolne, więc i nie do użycia w praktycznych zastosowaniach. W praktyce zaś stosuje się heurystyki, które może nie zapewniają znalezienia najlepszego rozwiązania, ale w zależności od tego, jaką zastosujemy, możemy uzyskać wynik bliski optymalnego. Zobaczmy przykładowe podejścia tego typu.

Do tej pory na blogu miałem okazję pokazać dwa ciekawe problemy obliczeniowe: problem skoczka szachowego oraz zliczania unikalnych elementów. Omawiając je (i nie tylko), wspominałem o innym, może i najbardziej znanym — problemie komiwojażera. Czytaj dalej, aby dowiedzieć się, o co w nim chodzi, jak możemy go rozwiązać, dlaczego na okładce jest listonosz, a także co ma wspólnego z grafami. Tak, niemal równo po dwóch latach wracam na blogu do tematyki grafów.

Bardzo często w Internecie znajdziemy przykłady dziwnego kodu, najczęściej napisanego w JavaScripcie. Nie zabierając temu wartości humorystycznej, to nieraz takie wpisy pokazują brak zrozumienia mechanizmów języków programowania. Wybrałem 5 takich przykładowych dziwactw, które wyjaśnię, dlaczego tak jest. Oczywiście dalej będzie mogło to wszystko wydawać się dziwne, ale może już nieco mniej. Dodatkowo, żeby nie było tak dobrze, większość przykładów nie będzie javascriptowa.