Algebra abstrakcyjna dla teoretycznych informatyków

Mam rozsądne wykształcenie matematyczne, ale nigdy nie czułem się w 100% swobodnie z abstrakcyjną algebrą (matematyka grup, pierścieni, pól itp.). Myślę, że było to częściowo tak, jak potrzebowałem, aby zobaczyć aplikacje, a wszystkie, które mogłem znaleźć, dotyczyły fizyki, a nie CS. Ponieważ moim zainteresowaniem jest naprawdę CS, czy są teraz dostępne jakieś materiały (szkice online, notatki z wykładów, filmy, książki), które obejmują algebrę abstrakcyjną z punktu widzenia aplikacji w CS, a szczególnie algorytmów / teorii? Cieszę się, że te aplikacje są całkowicie teoretyczne, ale nie powinny zakładać żadnej wcześniejszej wiedzy z zakresu algebry abstrakcyjnej.

Jestem pewien, że gdyby te zasoby istniały, doceniłoby je wielu badaczy CS.

Możesz spróbować notatek z kursu Madhu Sudana: Algebra i obliczenia

Jedną z możliwych ścieżek do algebry abstrakcyjnej może być spojrzenie na nią z punktu widzenia kryptografii, która dotyczy algorytmów na polu skończonym. Pola są pierścieniami, a pola to także dwie grupy połączone prostymi prawami. Teoria pola wykorzystuje przestrzenie wektorowe w widocznym miejscu (teoria Galois), więc ten kąt powinien obejmować wiele abstrakcyjnych algebry. Książka

Komputerowe wprowadzenie do teorii liczb i algebry autorstwa V. Shoupa

może zatem być interesujące.

Moją osobistą rekomendacją byłoby zignorowanie aplikacji i przestudiowanie podstawowego tekstu matematycznego dla studentów na temat algebry abstrakcyjnej. Nie brakuje ich. Po prostu zaufaj, że wszystkie te rzeczy są przydatne i że użycie ujawni się łatwiej, gdy tylko opanujesz materiał.

Najbardziej podstawowa algebra jest konstruktywna i można łatwo wdrożyć podstawowe pojęcia w celu lepszego zrozumienia, np. Algorytmy sprawdzające, czy tabliczka mnożenia jest grupą, rozwiązywanie równań w grupie, program sprawdzający, czy dwie struktury algebraiczne są izomorficzne itp. Większość z tych problemów mają rozwiązania brutalnej siły, które są łatwe do wdrożenia, ale powolne. Im więcej uczysz się o algebrze, tym więcej algorytmicznych skrótów możesz zrobić, aby przyspieszyć swoje programy. Np. Słynne testy pierwotności Millera-Rabina i AKS .

Sprawdź tę książkę Rudolfa Lidla i Haralda Niederreitera: Wprowadzenie do skończonych pól i ich zastosowań (2. wydanie, 1994) http://www.amazon.com/Introduction-Finite-Fields-their-Applications/dp/0521460948

Cytując opis książki w Amazon: „Teoria pól skończonych jest gałęzią współczesnej algebry, która zyskała na znaczeniu w ostatnich latach ze względu na jej różnorodne zastosowania w takich obszarach, jak kombinatoryka, teoria kodowania, kryptologia i matematyczne badanie obwodów przełączających . ”

Oprócz kryptografii bardzo dobrym praktycznym zastosowaniem algebry w informatyce jest być może implementacja ułamków, w których licznik i mianownik są typu integralnego lub „dużej liczby całkowitej”, a długość kodowania jest niewielka przez zmniejszenie ułamków (tj. Uwzględnienie największego wspólnego dzielnik licznika i mianownika).

Jeśli chodzi o typy danych „wielka liczba całkowita”, interesującym rezultatem jest tak zwane „twierdzenie o chińskiej reszcie”, które pozwala na zrównoleglenie operacji na liczbach całkowitych, gdy znana jest reprezentacja jako czynniki pierwsze argumentów.

Co więcej, większość rzeczy znalezionych w algebrze może być przyjemna estetycznie (tylko osobisty punkt widzenia).