Informatyka dynamic-programming

1

Mikrooptymalizacja do obliczania odległości edycji: czy jest poprawna?

W Wikipedii podano implementację oddolnego schematu programowania dynamicznego dla odległości edycji. Nie jest całkowicie zgodny z definicją; komórki wewnętrzne są obliczane w następujący sposób: if s[i] = t[j] then d[i, j] := d[i-1, j-1] // no operation required else d[i, j] := minimum ( d[i-1, j] + 1, // a …

10 algorithms dynamic-programming string-metrics correctness-proof program-optimization

1

Znajdowanie najdłuższego powtarzającego się podsekwencji

Biorąc pod uwagę ciąg sss, Chciałbym znaleźć najdłuższą powtarzającą się (przynajmniej dwukrotnie) podsekwencję. To znaczy, chciałbym znaleźć ciągwww który jest podciągiem (nie musi być ciągły) z sss takie, że w=w′⋅w′w=w′⋅w′w=w' \cdot w' . To jest,wwwto ciąg, którego połówki pojawiają się dwa razy z rzędu. Zauważ, żewww jest podsekwencją sss, ale …

9 algorithms optimization dynamic-programming strings subsequences

1

Jak zrekonstruować las drzew składniowych z wektora Earley?

Użycie wektora Earleya jako rozpoznającego jest dość proste: po osiągnięciu końca struny wystarczy sprawdzić, czy produkcja aksjomatyczna została rozpoczęta w pozycji 0. Jeśli masz przynajmniej jeden ciąg, łańcuch jest akceptowany. Użycie wektora Earleya do odtworzenia drzewa przetwarzania jest mniej oczywiste. Właściwie nie jestem w stanie ustalić, jak mogłaby działać procedura …

9 context-free dynamic-programming parsers ambiguity syntax-trees

4

Co jest „dynamiczne” w programowaniu dynamicznym?

Jeden z moich seniorów odbył rozmowę kwalifikacyjną i zapytano go, dlaczego nazywa się to dynamicznym. Nie mógł odpowiedzieć, a po tym, jak zrezygnował z wywiadu, powiedział, że nie ma w tym nic dynamicznego, po prostu tak to się nazywa. Trudno mi w to uwierzyć. Czy odnosi się to do faktu, …

9 terminology dynamic-programming

Pytania otagowane jako dynamic-programming