Wszystkie * doskonałe panele języka angielskiego

An Angielski pangram to zdanie zawierające wszystkie 26 liter alfabetu angielskiego. Najbardziej znanym angielskim pangramem jest prawdopodobnie „Szybki brązowy lis przeskakuje leniwego psa”. Moim ulubionym pangramem jest „Zadziwiająco niewiele dyskotek zapewnia szafy grające”.

Doskonały pangram to pangram, w którym każda z liter pojawia się tylko raz. Znalazłem w Internecie źródła zawierające listę znanych doskonałych pangramów. Wydaje się, że nikomu nie udało się wyprodukować ich wszystkich w sposób wyczerpujący, więc potraktowałem to jako zabawne wyzwanie. W ten sposób znalazłem wszystkie * doskonałe pangramy języka angielskiego. Gwiazdkę wyjaśnię później.

Uwaga. Źródło.
  • Crwth vox zaps qi gym fjeld bunk. (Dźwięk celtyckich skrzypiec uderza we wschodnie centrum fitness skoncentrowane na siłach duchowych, położone na jałowym płaskowyżu Skandynawii.) To są wszystkie prawnicze słowa Scrabble!
  • Squdgy kilp job zarf nth cwm vex. (Źle uformowane wodorosty kupują ozdobny podgrzewacz do filiżanek, który podrażnił jedno z wielu półotwartych zagłębień o stromych ścianach u szczytu doliny lub zbocza góry.)
  • Jock nimfy waqf drug vex blitz. (Darowizna na cele charytatywne odurzyła leśne duchy, które frustrowały atletę, który angażuje się w atak).
  • Hm, walc fiordów, cinq busk, pyx veg. (Zobaczmy, długie, wąskie, głębokie tańce wlotowe, piątka na kostce tworzy muzykę na ulicy, a mały okrągły pojemnik dla chorych i niezdolnych odpoczywa.) Również Scrabble legalny, ale ma wykrzyknik (Hm).

Niestety, są to jedne z najbardziej czytelnych zdań, jakie udało mi się znaleźć *. Wszystkie doskonałe pangramy wygenerowane z oficjalnej listy 3 turniejów i klubowych słów (OWL3) dla Scrabble bez wykrzykników zawierają słowo cwm lub crwth. Waqf jest legalnym turniejem Scrabble poza Ameryką Północną.

Jak znaleźć wszystkie idealne pangramy

Metoda znalezienia idealnych pangramów składa się z dwóch kroków. Pierwszym jest jednorazowe wyszukanie wszystkich zestawów słów zawierających każdą literę alfabetu angielskiego. Drugim krokiem jest sprawdzenie, który z tych zestawów można przekształcić w prawidłowe angielskie zdania.

Krok 1: Znajdowanie zestawów słów dla idealnego pangram

Aby rozpocząć wyszukiwanie zestawów słów, które span the angielski alfabet wymaga listy angielskich słów. Znalezienie i utrzymanie wysokiej jakości listy słów było znacznie trudniejsze, niż się spodziewałem. Początkowo myślałem, że ten projekt zajmie dwa dni, ale w wyniku tego problemu z jakością danych trwał dwa tygodnie.

Zacząłem od słownika uniksowego, który jest ogólnie dostępną listą angielskich słów. który jest dostarczany z prawie wszystkimi systemami operacyjnymi opartymi na Uniksie. Od razu zauważyłem, że lista zawiera problemy z jakością. Po pierwsze, każda litera alfabetu była uważana za słowo w słowniku uniksowym i zawierała wiele nie-słów, takich jak „vejoz”. Pokazało to potrzebę stworzenia czarnej listy do zarządzania listami słów znalezionych w Internecie. W słowniku uniksowym brakowało liczby mnogiej dla słów, więc słownik zawierałby słowo „pomarańczowy”, ale nie „pomarańcze”. Lista słów jest tak restrykcyjna, że żadne znane wcześniej doskonałe pangramy nie zawierają tylko słów ze słownika uniksowego. Nadal znalazłem niektóre, takie jak „squdgy kilp job zarf nth cwm vex”.

Następnie przeszukałem Internet, aby znaleźć większe zestawy słów. Znalazłem bardzo duże zestawy słów, które były ogromne, ale kiedy zacząłem szukać doskonałych pangramów z tych list, stwierdziłem, że były one zbyt zanieczyszczone słowami niskiej jakości, które nie są poprawnymi angielskimi słowami. Nawet po wielu rundach iteracji nadal nie udało mi się przeanalizować listy, aby znaleźć jakiekolwiek rozsądne lub wykonalne pangramy. Próbowałem to wyczyścić, tworząc białą listę słów o określonej długości, ale lista nadal była wyjątkowo niskiej jakości.

Wreszcie, po wielu iteracjach, zapłaciłem 15 USD, aby kupić próbne członkostwo w Ameryce Północnej Scrabble® Players Association, które dało mi dostęp do zastrzeżonego i chronionego prawem autorskim OWL3, który jest źródłem pewnych kontrowersji. Nawet wtedy musiałem dodać kilka znanych angielskich słów, takich jak jednoliterowe słowa „a” i „I”.

Uzbrojony w odpowiednią listę słów zaimplementowałem algorytm wszystkie zestawy słów z tej listy, z których każdy zawiera jedną z każdej litery alfabetu angielskiego. Szczegółowo opiszę algorytm w sekcji „Algorytm” poniżej.

Krok 2: Tworzenie angielskich zdań z zestawu słów

Biorąc pod uwagę zestaw słów, ustalenie, czy prawidłowe zdanie angielskie jest możliwe ze wszystkimi podanymi słowami jest nietrywialnym problemem, ale jest łatwiejsze niż większość innych problemów związanych z przetwarzaniem języka naturalnego (NLP).

Istnieją przydatne heurystyki do usuwania niekwalifikujących się zdań; Po wykonaniu tych heurystyk byłem w stanie ułożyć poprawne angielskie zdania z pozostałych słów. Zdania były często bezsensowne, ale wciąż aktualne. Oto heurystyka, której użyłem:

  1. Musi istnieć co najmniej jeden czasownik.
  2. Może być tylko jeden rzeczownik więcej niż czasowników, chyba że istnieje spójnik lub przyimek, z których oba są bardzo rzadkie.
  3. Jeśli istnieją przymiotniki, muszą być również rzeczowniki.

Heurystyka działa częściowo z powodu możliwości domniemanego tematy (ani doskonałe, ani pangram, ale „poruszaj się cicho i mów cicho” to zdanie z dwoma czasownikami i bez rzeczowników, z domniemanym podmiotem „ty”).

Ponieważ przestrzeń słów, które mogą prawdopodobnie uczestnictwo w doskonałych pangramach jest małe, łatwo jest ręcznie oznaczyć każde pojedyncze słowo odpowiednimi częściami mowy i sprawdzić, czy zestaw słów jest zgodny z tymi trzema prostymi heurystykami. To, czy podoba Ci się jakość tworzonych zdań, jest kwestią gustu.

Algorytm

Ta sekcja jest nieco techniczna, ale mam nadzieję, że nadal łatwa do naśladowania. Możesz przejść do sekcji „Wyniki & Nauka”.

Strategia wysokiego poziomu

Celem jest stworzenie wszystkich możliwych zestawów słowa z podanej listy słów, które „doskonale” obejmują alfabet angielski.

  1. Wyczyść listę słów, aby drastycznie zmniejszyć przestrzeń wyszukiwania, np. usuń słowa, które mają powtarzające się litery, takie jak „litery”.
  2. Użyj masek bitowych, aby efektywnie przedstawić słowa i odwzorować je z powrotem na oryginalne zestawy słów.
  3. Przeszukuj wszystkie możliwe stany, każda reprezentuje możliwą kombinację liter, poprzez wielokrotne iterowanie przez listę masek bitowych. Wydajność jest znacznie poprawiona dzięki programowaniu dynamicznemu.
  4. Rysuj strzałki (skierowane krawędzie) z idealnego stanu pangram, stanu końcowego, który ma wszystko litery angielskie, do państw pośredniczących, które go skomponowały. Zrób to ponownie z państwami pośredniczącymi, aby utworzyć strukturę danych, która może zrekonstruować zestawy słów, które są możliwe w postaci doskonałych pangramów. Nazywa się to cofaniem.
  5. Wyjście odkryte zestawy słów, które są prawdopodobnie idealnymi pangramami jako drzewa.

Czyszczenie listy, czyli kanonizacja

Pierwszym krokiem jest wyczyszczenie oryginalnej listy słów, aby zmniejszyć przestrzeń wyszukiwania i poprawić jakość wyników.

  1. Usuń wszystkie białe znaki wokół słowa i przekonwertuj je tylko na małe litery
  2. Upewnij się, że słowa zawierają tylko litery alfabetu angielskiego; Użyłem prostego filtra wyrażeń regularnych: /^+$/
  3. Filtruj względem innych list, np. czarne listy; jeśli słowo znajduje się na czarnej liście, pomiń je
  4. Usuń wszystkie słowa z powtórzonymi literami

Znacznie skróciło to przestrzeń wyszukiwania z list 200 000 ~ 370 000 słów do dużo mniejszych 35 000 ~ 65 000 słów.

Korzystanie z masek bitowych

Maski bitowe to całkowite reprezentacje stanów. Jest kilka zalet masek bitowych:

  • Maski bitowe dobrze przedstawiają ten problem. Kolejność liter nie ma znaczenia, więc wszystkie kombinacje słów można przedstawić jako 26-cyfrowy ciąg zer i jedynek, przy czym każda cyfra określa, czy w kombinacji istnieje litera. Na przykład. jeśli zestaw słów zawiera literę „e”, piątą cyfrą będzie 1, w przeciwnym razie 0.
  • Maski bitowe są wydajne: ponieważ przestrzeń wyszukiwania jest stała, maski bitowe zapewniają wydajne przechowywanie i reprezentacja wszystkich możliwych kombinacji liter. Ponadto operacje bitowe są szybkie; aby sprawdzić, czy można połączyć dwie maski bitowe w celu utworzenia większej maski bitowej, sprawdź, czy bitowe AND obu masek jest równe 0, z których obie są wyjątkowo szybkie operacje.

Dlatego zamień każde słowo w maskę bitową, którą można przedstawić jako liczbę całkowitą. Na przykład słowo „cab” zostanie odwzorowane na maskę bitową 111, która to liczba dziesiętna 7. Słowo „być” zostaje odwzorowane na 10010, co jest liczbą dziesiętną 18 itd. Największą możliwą maską bitową jest ta zawierająca wszystkie litery alfabetu, możliwy idealny stan pangram, 11111111111111111111111111, która jest liczbą dziesiętną 67 108 863 lub 2²⁶ -1. To dobrze pasuje do standardowej 32-bitowej liczby całkowitej ze znakiem, która może reprezentować górę do 2³¹-1.

Stosowanie masek bitowych dodatkowo kompresuje przestrzeń, ponieważ anagramy pojedynczego słowa są odwzorowywane na tę samą maskę bitową. Zarówno „piec”, jak i „link” odwzorowują maskę 10110100000000, która jest liczbą dziesiętną 11520. To dodatkowo zmniejsza przestrzeń wyszukiwania z 35 000 ~ 65 000 słów do masek 25 000 ~ 45 000 bitów.

Zachowaj odwzorowanie maski bitowej z powrotem na zestaw słów, z których pochodzą. Będzie to przydatne podczas wyprowadzania zestawów słów.

Wyszukiwanie idealnego pangramu z programowaniem dynamicznym

Przykład narysowanej zabawki tylko dla pierwszych 5 liter alfabetu angielskiego, ae

Rdzeń algorytmu jest dość prosty:

Biorąc pod uwagę możliwy stan (który składa się z prawidłowych kombinacji istniejących słów), wypróbuj wszystkie maski z początkowej listy słów, aby zobaczyć, czy jest możliwe utworzenie nowego prawidłowego stanu (sprawdzając, czy bitowe AND z stan i maska są równe 0, co oznaczałoby, że nie ma nakładających się liter). Utwórz nowy stan, używając operacji bitowej OR, która łączy wszystkie jedynki razem. Dla każdego nowego odkrytego stanu powtarzaj tak długo, aż nie będzie już żadnych niezbadanych stanów. Jeśli to osiągnie koniec, oznacza to, że algorytm znalazł co najmniej jeden możliwy doskonały zestaw słów pangram. Pierwszym możliwym stanem, który może wyliczyć wszystkie możliwe stany, jest stan pusty lub 0, w którym nie są uwzględnione żadne litery alfabetu. Zacznij więc od tego, a następnie rekurencyjnie odkryj, które stany są możliwe.

Ogromnym wzrostem wydajności jest zauważenie, że istnieje wiele sposobów osiągnięcia stanu przerywanego i że praca nad stanem nie zmienia się w zależności od tego, jak to się dzieje. został osiągnięty. Dlatego zamiast powtarzać pracę, gdy ponownie odwiedzany jest stan, zapisz wynik każdego stanu. Ta technika nazywa się programowaniem dynamicznym i przekształca złożony problem kombinatoryczny w program liniowy. Proces zapisywania stanu przerywanego nazywa się zapamiętywaniem.

Zatem utwórz tablicę o rozmiarze 2²⁶, między 0 a 67 108 863 włącznie. Każdy indeks reprezentuje stan maski bitowej, jak wyjaśniono wcześniej. Wartość przy każdym indeksie tablicy reprezentuje informacje o stanie. 0 oznacza, że stan jest nietknięty lub nieosiągalny. 1 oznacza, że stan znalazł sposób na osiągnięcie możliwego doskonałego stanu pangramu. -1 oznacza, że stan nie znalazł sposobu na dotarcie do końca.

Poniżej pseudokod:

Interlude: złożoność i praktyczna analiza środowiska wykonawczego

Istnieją 2²⁶ możliwych masek bitowych dla serii 26 bitów. Ponieważ każdy stan jest przetwarzany tylko raz z powodu zapamiętywania, czas działania tego algorytmu wynosi O (n 2 ^ d), gdzie d jest rozmiarem alfabetu, 26. Zmienna n nie oznacza liczby słów, ale liczba masek bitowych. Przy 67 108 863 i około 45 000 bitowych maskach daje to 3 biliony, co mój MacBook Pro mógł obsłużyć w około 45 minut; wykonalny dla każdego nowoczesnego komputera. Warto również zauważyć, że stos wywołań rekurencyjnych nigdy nie będzie głębszy niż 26 (prawdopodobnie nigdy nie będzie głębszy niż 15), więc jest również bardzo łatwy do zarządzania również z tego wymiaru.

Jedna zaleta podejścia z maską bitową z tylko 2²⁶ stanów oznacza, że wszystkie stany mogą być przechowywane w pamięci. Ponieważ na stan przypadają tylko 3 wartości (-1, 0, 1), można to zapisać w jednym bajcie. Przy jednym bajcie na stan, 2²⁶ stanów zajmuje około 67 megabajtów, co jest znowu bardzo łatwe w zarządzaniu.

Jednak wraz ze wzrostem alfabetu przestrzeń wyszukiwania rośnie wykładniczo, podobnie jak czas wykonywania, powodując problem, aby szybko stać się nie do rozwiązania. Krótka dyskusja na temat zbliżania się do idealnego pangramu dla większych alfabetów znajduje się w sekcji „Język z większymi alfabetami” poniżej.

Dynamiczne tworzenie ukierunkowanego wykresu acyklicznego (DAG)

Rysowanie DAG tylko dla masek bitowych ze stanem 1

Teraz, gdy wypełniliśmy stany maski bitowej, czas na znalezienie rozwiązania!

Aby znaleźć zestawy słów, które utworzyły zbiór możliwych doskonałych pangramów, musimy wyprowadzić, które stany pośrednie były integralne przy tworzeniu stanów końcowych Następnie pojawia się pytanie uzupełniające, które inne państwa pośredniczące utworzyły te stany pośrednie i tak dalej, aż jedyną pozostałą rzeczą są stany, które odwzorowują bezpośrednio na słowa. Ten proces nazywa się cofaniem.

Aby zachować śledzić relacje między stanami, celem jest stworzenie Di rektowany graf acykliczny (DAG), który utrzymuje, które stany pośrednie tworzą dany stan. Przez DAG można łatwo przejść w celu pobrania wyników, zwłaszcza ze względu na ich niecykliczny charakter. Aby skonstruować, zacznij od możliwego doskonałego stanu pangram i utwórz skierowaną krawędź (strzałkę), która wskazuje stany pośrednie, które go tworzą. Powtórz ten proces ze stanami pośredniczącymi, a wygeneruje DAG. Nigdy nie będzie żadnych cykli, ponieważ strzałki zawsze wskazują stan o mniejszej wartości.

Zamiast odbudowywać relacje odkryte na etapie wyszukiwania, co wiąże się z ponownym przejściem przez biliony możliwych kombinacji stanów, bardziej efektywne jest zbudowanie DAG podczas fazy programowania dynamicznego. W metodzie rozwiązywania, jeśli nowo skonstruowany stan może osiągnąć możliwy idealny stan pangram, zapisz skierowaną krawędź ze stanu nowo skonstruowanego do stanu pierwotnego tylko wtedy, gdy stan pierwotny jest mniejszy niż jego uzupełnienie (aby zmniejszyć powielanie krawędzi).

Wydrukuj owoce swojej pracy w formie drzewa!

Dane wyjściowe przykładu zabawki

Prawdopodobnie najłatwiejszym formatem przeglądania wynikowych zestawów słów jest wypisanie ich jako drzew z węzłem głównym jako idealnym stanem pangram. Biorąc pod uwagę DAG skonstruowany z góry, najlepszym sposobem na rozpakowanie go jest zrobienie tego rekurencyjnie, zapisując każdy stan na dysku w każdym kroku zamiast do pamięci, ponieważ drzewo jest o rząd wielkości większe niż DAG.

Udoskonaleniem tej formy rozwinięcia jest podsumowanie stanów, które mają tylko jedną możliwą kombinację słów. Stan, który jest maską słów i nie składa się na niego z podrzędnych, można podsumować w trywialny sposób. Stan można podsumować, jeśli można podsumować jego podstaty i jego elementy składowe, a wszystkie maski pochodzące od niego i jego dzieci nie mają nakładających się bitów / znaków. Wydrukowanie podsumowanego DAG poprawia czytelność wynikowego drzewa wyjściowego poprzez skrócenie i uproszczenie go.

Ponieważ podsumowanie zależy tylko od mniejszego z dwóch stanów, iteracja przez tablicę od początkowego stanu 0 w górę i użycie powyższych reguł do zarządzania regułą podsumowania pozwala na ukończenie tego w czasie liniowym.

Wytworzone drzewa Pangram!

Nie krępuj się przechodzić przez idealne drzewa pangram, aby sprawdzić, czy może znaleźć ciekawe zdania!

Istnieje wiele możliwych doskonałych pangramów

Zaskoczyła mnie liczba doskonałych możliwych pangramów. Tam jest dużo! Najlepsza strategia łączenia ich w całość nie wymaga skomplikowanego procesora języka naturalnego. Po oznaczeniu słów kandydatów jako kwalifikujących się rzeczowników lub czasowników, zbiór słów musi zawierać co najmniej jeden rzeczownik, jeden czasownik oraz właściwy stosunek rzeczowników i czasowników.

Jakość danych to trudny problem

Sekcja algorytmów zajęła dwa dni, ale problem z jakością danych zajął dwa tygodnie. Kiedy wspomniałem o tym odkryciu mojemu przyjacielowi, który jest starszym inżynierem Google, nie był zdziwiony, mówiąc, że problemy z jakością danych to jedne z najtrudniejszych problemów w inżynierii. Wyciągnięta lekcja.

Zasady doskonałych pangramów

Jest wiele niuansów co do tego, co kwalifikuje się jako doskonały pangram! Chciałem przeszukiwać pangramy bez żadnych wykrzykników (np. Hm, pht), ale są też inne popularne ograniczenia, takie jak skróty, akronimy, skróty, inicjały, pojedyncze litery, własne rzeczowniki i cyfry rzymskie. Są też słowa, które są nazwami liter, na przykład Qoph, które moim zdaniem są oszustwem.

Po złagodzeniu niektórych z tych ograniczeń jest wiele „doskonałych” pangramów. Prawdopodobnie rzędu bilionów . Jest wiele akronimów i inicjałów.

Gwiazdka

Gwiazdka jest na miejscu, ponieważ definicja wszystkich doskonałych pangramów języka angielskiego nie jest dobrze zdefiniowana. Istnieją niuanse związane z tym, co powinno być dozwolone w doskonałych pangramach języka angielskiego. Istnieje również wiele sporów dotyczących tego, czy niektóre słowa są nawet angielskimi słowami. Biorąc pod uwagę te niuanse, naprawdę trudno jest powiedzieć, że znalazłem wszystkie doskonałe pangramy. Mogę dość pewnie sformułować dwa twierdzenia:

  1. Znalazłem metodologię tworzenia wszystkich doskonałych pangramów języka angielskiego i innych języków z podobnymi lub mniejszymi zestawami znaków.
  2. I wyliczyli wszystkie zestawy słów, które mogą potencjalnie tworzyć doskonałe pangramy, używając oficjalnego słownika turniejowego Scrabble y, OWL3.

Nie krępuj się tworzyć własnych doskonałych pangramów za pomocą technik opisanych w tym poście!

Zależność Perfect Pangrams od słów pochodzenia walijskiego i arabskiego

Słowa pochodzące z języka walijskiego i arabskiego były naprawdę ważne dla istnienia doskonałych angielskich pangramów (chyba że ograniczenia doskonałego pangramu zostały złagodzone). Używając listy słów OWL3 ze ścisłymi zasadami dotyczącymi doskonałych pangramów, nie ma doskonałych pangramów, które nie zawierają słów „cwm (s)” lub „crwth (s)”, obydwu słów walijskich. W międzynarodowym Scrabble arabskie słowo „waqf (s)” jest ważnym słowem, które może dać doskonałe pangramy bez uciekania się do „cwm (s)” lub „crwth (s)”.

Wydajność strumienia pracy

Ważnym było, aby być bardziej wydajnym w równoległym wykonywaniu zadań podczas tego projektu. Pełne uruchomienie zajmuje 25 minut w przypadku słownika uniksowego i blisko godzinę w przypadku naprawdę dużych słowników. Miałem początkowe problemy z przełączaniem kontekstu przez 30-minutowe okno, ale poprawiłem się w miarę zwiększania produktywności.

Rozszerzenie / uogólnienie – Anagram Finder

Idealny panel wyszukiwanie jest również odpowiednikiem znajdowania anagramów dla ciągu „abcdefghijklmnopqrstuvwxyz”. A co by było, gdybyś chciał zbudować ogólną wyszukiwarkę anagramów?

Tej samej techniki można użyć, o ile reprezentacja stanu i reguły zarządzania ważność kombinacji słów jest aktualizowana. Zamiast zarządzać stanami jako liczbami całkowitymi, łatwiej byłoby śledzić stan jako mapę odpowiednich znaków. Sprawdzanie, czy kombinacje są prawidłowe, oznacza, że kombinacja dwóch map nie przekracza żądana liczba znaków anagramu dla każdej litery. Upewnij się tylko, że przestrzeń stanów jest łatwa do przetworzenia; przy zbyt dużej liczbie liter przestrzeń wyszukiwania może się bardzo powiększyć w mgnieniu oka. Czy możesz też powtarzać słowa? Upewnij się, że zdefiniowałeś te zasady w środku Twoje programowanie dynamiczne rozwiązanie.

Języki z większymi alfabetami

Iroha to słynny japoński poemat doskonały pangram napisane w okresie Heian

To podejście i rozwiązanie są liniowe w rozmiarze zestawu słów, ale wykładnicze w rozmiarze alfabetu. Takie podejście może nie działać w przypadku większego zestawu znaków, na przykład współczesnego japońskiego, który ma 46 sylab. 2⁴⁶ wynosi 70 368 744 177 664; ponad milion razy większa niż angielska przestrzeń wyszukiwania wynosząca 2²⁶ = 67 108 864.

Nie jest do końca jasne, czy to podejście będzie działać w przypadku języka japońskiego. Jeśli język japoński ma wystarczająco niską entropię, co jest możliwe, podejście to byłoby wykonalne. Zamiast inicjalizować tablicę o rozmiarze 2⁴⁶, stany będą śledzone na mapie. Ponadto można wykorzystać strukturę języka japońskiego; na przykład kana を (wo) jest prawie wyłącznie używana jako imiesłów postpozycyjny i można ją wykluczyć z wyszukiwania, zmniejszając przestrzeń wyszukiwania.

Kambodżański język khmerski ma największy alfabet z 74. Kolejnym możliwym krokiem jest zbadanie rozwiązań, które są sub-wykładnicze w rozmiarze alfabetu.

Inspiracja

Zainspirował mnie postęp Aubrey De Grey w znalezieniu liczby chromatycznej samolotu, który ma być co najmniej 5. Jest to znaczący postęp, który został osiągnięty dzięki podstawowym metodom obliczeniowym.

Nie trzeba dodawać, że znalezienie idealnych pangramów nie wystarczy, aby poprawić dolną granicę liczby chromatycznej płaszczyzny.

To sprawia, że wierzę, że istnieje wiele nisko wiszących problemów owocowych, które mają proste metody obliczeniowe do rozwiązania problemu, który jest trudny do rozwiązania ręcznie. Wzywam was do znalezienia i rozwiązania niektórych z tych problemów. Daj mi znać, jeśli coś znajdziesz!

Dzięki

Jestem bardzo wdzięczny moim bardzo wspaniałym przyjaciołom, którzy pomogli mi przez korektę i jamowanie ze mną, zwłaszcza Anna Zeng, Catherine Gao, Danny Wasserman, George Washington i Nick Wu!

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *