Zasada gołębiej dziury

Dzisiejsza notka będzie o pewnej matematycznej ciekawostce, która pokazuje, że nawet pozornie oczywiste stwierdzenie mogą mieć daleko idące konsekwencje, jakich nie da się na pierwszy rzut oka przewidzieć. Mamy mianowicie pewną kombinatoryczną regułę, mówiącą (w jednej z wersji), że:

Jeżeli n obiektów umieścimy w m < n pudełkach, to znajdzie się pudełko zawierające więcej niż jeden obiekt.

Zaskakujące, prawda? ;-) Wydaje się, że niewiele jest rzeczy bardziej oczywistych. A jednak powyższe twierdzenie doczekało się swojej własnej nazwy – i to nawet takiej, która uwzględnia nazwisko odkrywcy! W języku polskim mówimy mianowicie o zasadzie szufladkowej Dirichleta, a analogią jest podobno układanie skarpetek w szufladach. W angielskim z kolei używa się do tego… gołębi, a reguła jest znana jako pigeonhole principle – w dosłownym tłumaczeniu ‘zasada gołębiej dziury’.

Co jest niezwykłego w tak prostej obserwacji? Otóż jej wyjątkową cechą jest to, że stosuje się do wręcz nieograniczonego spektrum zjawisk różnego typu i wielu dziedzin, pozwalając udowadniać prawdziwość mnóstwa czasami zaskakujących stwierdzeń. Ich ciężar gatunkowy może się wahać od zabawnych, aczkolwiek pouczających, aż do zupełnie kluczowych dla niektórych dziedzin nauki. Oto przykłady:

• Struktury danych oparte na haszowaniu zawsze muszą uwzględniać metody rozwiązywania kolizji. Ten znany fakt jest konsekwencją tego, iż liczba możliwych kluczy n przekracza (zazwyczaj znacznie) rozmiar pojemnika m, więc nawet przy najlepszej funkcji haszującej znajdą się takie dwa klucze, które zostaną przyporządkowane w to samo miejsce.
• W pudełku jest 5 czarnych i 5 białych kul. Ile co najmniej kul musimy wybrać, żeby wśród nich znalazła się para tego samego koloru? Nie, wcale nie sześć – wystarczą trzy. Skoro mamy m = 2 kolorów, to już n = 3 kul gwarantuje, że będzie wśród nich para tego samego koloru.
• Wśród wszystkich obecnie żyjących ludzi co najmniej dwójka wypowiedziała w ciągu swojego dotychczasowego życia identyczną liczbę słów. Nawet gdyby ktoś paplał 24 godziny na dobę z prędkością jednego słowa na sekundę, w ciągu jednej doby nie powie ich więcej niż 86.400. Najstarszy człowiek miał/ma około 130 lat, w związku z czym ilość możliwych wartości dla wielkości ‘liczba wypowiedzianych słów’ to ok. 86.400 * 365,25 * 130, czyli nieco ponad 4 miliardy. Ponieważ na Ziemi żyje obecnie ponad 6 miliardów ludzi – czyli więcej – na mocy zasady szufladkowej wnioskujemy, że musi istnieć co najmniej dwójka, która wypowiedziała w ciągu życia tę samą liczbę słów.
• Jeśli algorytm kompresji bezstratnej rzeczywiście kompresuje (tj. zmniejsza objętość przynajmniej jednego pliku), to istnieje dla niego taki plik, który po “kompresji” będzie większy niż przed nią. Innymi słowy, nie ma doskonałych metod kompresji i nawet rosyjscy hakerzy nic na to nie poradzą :) Jest to bowiem bezpośrednia konsekwencja zasady ‘gołębiej dziury’.
  Powiedzmy, że najmniejszy plik faktycznie kompresowany (tj. zmniejszany) przez nas algorytm ma początkowy rozmiar , zaś po kompresji jest to już , gdzie . Istnieje skończona liczba plików rozmiaru , którą oznaczymy . (Jeśli na przykład jest to rozmiar w bajtach, to ). Z założenia żaden z tych plików nie zmienia rozmiaru podczas kompresji, więc ich wielkość po skompresowaniu to również . Oznacza to jednak, że tych plików to wyniki kompresji plików, bo także (większy niż ) jest kompresowany do jednego z tych plików. Ponieważ , na mocy zasady szufladkowej istnieją dwa takie pliki – mianowicie i jakiś plik rozmiaru – które są kompresowane do tego samego pliku wyjściowego. Jeśli tak jest, to algorytm nie może być bezstratny – czyli mamy sprzeczność, Q.E.D. :-)

Całkiem sprytne, nieprawdaż? Jak na zupełnie “oczywistą oczywistość”, zasada szufladkowa wykazuje niezwykłą użyteczność w wielu zaskakujących momentach. Warto o niej pamiętać nie tylko podczas poszukiwań pary pasujących skarpetek :)

Triki z PowerShellem #12 – Rozpakowywanie

Wiele programów z sieci wciąż jeszcze ściąga się w postaci archiwów do samodzielnego wypakowania, jak choćby w formacie .zip. Ma to swoje zalety i wady – do tych drugich należy fakt, że nie bardzo wiadomo, jak wygląda wewnętrzna struktura katalogów takiej paczki. Używając opcji typu Wypakuj tutaj ryzykujemy zaśmiecenie folderu Downloads plikami programu. Dlatego osobiście zawsze stosuję polecenie Wypakuj do nowego katalogu.
I tu czasem jest mały zonk, gdy twórca archiwum zdecydował się na spakowanie całego folderu, a nie tylko zawartych w nim plików. Powstają wtedy nadmiarowe katalogi, wydłużające ścieżki do plików (co widać obok – w wersji trochę przesadzonej ;)).

Ponieważ podobne sytuacje zdarzają mi się dość często, postanowiłem im zaradzić przy pomocy najlepszego narzędzia na takie okazje, czyli PowerShella rzecz jasna :) Wynikiem jest poniższy skrypt do sprytniejszego rozpakowywania archiwów:

Jego działanie polega wpierw na zwykłej dekompresji archiwum. Jak można zauważyć, używa do tego obiektu COM-owskiego Shell.Application. To sprawia, że skrypt ma pod tym względem te same możliwości co zwykły windowsowy Eksplorator (dla większych plików pokaże nawet pasek postępu ;]).
Później wypakowana zawartość jest poddawana operacji, którą nazywam tutaj ‘skróceniem ścieżki’. Polega ona wyrzuceniu jednego poziomu drzewa folderów, o ile tylko pewien katalog jest jedynym elementem swojego katalogu nadrzędnego. Takie właśnie sytuacje powstają przy dekompresji do nowego folderu archiwów źle zapakowanych (przynajmniej z mojego punktu widzenia ;P). Wynikiem działania skryptu będzie więc w sumie jeden nowy podkatalog zawierający bezpośrednio całą interesującą zawartość archiwum.

Oczywiście używanie powyższego skryptu tylko z poziomu linii komend PowerShella nie jest specjalnie wygodne; lepiej jest dodać go do menu kontekstowego archiwów, czyli np. plików .. O tym, jak można tego dokonać, napisałem dość obszernie przy okazji prezentacji skryptu do wysyłania przez FTP.