Porządek leksykograficzny
Z Wikipedii
Porządek leksykograficzny to pojęcie matematyczne odnoszące się do sposobu uporządkowania elementów zbiorów.
Załóżmy, że na zbiorze X mamy jakiś porządek i chcemy rozszerzyć go na ciągi elementów zbioru X. X może być zbiorem liczb całkowitych, zbiorem symboli pewnego alfabetu, lub jakimkolwiek innym zbiorem, którego elementy potrafimy porównywać.
Porządek leksykograficzny na ciągach elementów należących do X definiuje się następująco:
- znajdujemy najmniejsze takie i, że i-ty element porównywanych ciągów jest różny
- ten ciąg jest większy w porządku leksykograficznym, którego i-ty element jest większy.
- jeśli dopuszczamy ciągi różnej długości, należy też ustalić sposób porównywania końca ciągu z elementami ciągu. Zwykle zakłada się, że jest albo większy albo mniejszy od wszystkich elementów X
Przykłady:
- zakładając normalny porządek na liczbach, ciąg (1, 0, 0, 0) jest leksykograficznie większy od ciągu (0, 10, 100, 1000) – na pierwszej różniącej się pozycji liczba w pierwszym ciągu (1) jest większa niż w drugim (0).
- zakładając porządek alfabetyczny, słowo "krowa" jest większe od słowa "kot" – na pierwszej różniącej się pozycji "r" jest większe od "o".
Nazwa porządku leksykograficznego pochodzi od sposobu w jaki słowa są uporządkowane w słowniku, najpierw według pierwszej litery, następnie według drugiej, i tak dalej.
W teorii ekonomii porządek leksykograficzny ma znaczenie głównie jako prosty przykład preferencji, których nie można przedstawić przy pomocy ciągłej funkcji użyteczności.
[edytuj] Linki zewnętrzne
- Lexicographic Order MathWorld (en)
