Porządek leksykograficzny
Z Wikipedii
Więcej informacji co należy poprawić, być może znajdziesz na odpowiedniej stronie. W pracy nad artykułem należy korzystać z zaleceń edycyjnych. Po naprawieniu wszystkich błędów można usunąć tę wiadomość.
Możesz także przejrzeć pełną listę stron wymagających dopracowania.
Porządek leksykograficzny 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".
