imported>Aka: /* Standartnummerierung bei der Indizierung mit Buchstaben */ Abkürzung korrigiert

2026-01-23T17:23:30Z

Standartnummerierung bei der Indizierung mit Buchstaben: Abkürzung korrigiert

Neue Seite

Die '''Standardnummerierung''' der abzählbar-unendlichen Menge der [[Wort (Theoretische Informatik)|Zeichenketten]] <math>\Sigma^*</math> ist die unter den Voraussetzungen eines beliebigen [[Alphabet (Informatik)|Alphabetes]] <math>\Sigma:=\{\sigma_1\ldots\sigma_m\}</math> mit endlicher [[Mächtigkeit (Mathematik)|Mächtigkeit]] <math>m:=|\Sigma|\in\mathbb{N}</math> und eindeutiger [[Nummerierung (Informatik)|Zeichennummerierung]] <math>\sigma \in \Sigma^{\{1\ldots m\}}</math> (wo die Zahlen <math>1\le i\le m</math> den Gesamtvorrat aller Zeichen <math>\sigma_i\in\Sigma</math> produzieren) diejenige [[Nummerierung (Informatik)|Aufzählweise]] <math> \nu_\sigma \in (\Sigma^*)^{\mathbb{N}} </math> (wo jede Zahl <math>n\in\mathbb N</math> genau ein Wort <math>\nu_\sigma^n \in \Sigma^*</math> produziert), welche genau diejenige [[Bijektion|bijektive]] [[Aufzählbarkeit]] <math> \alpha_\sigma\in \mathbb N^{\Sigma^*} </math> (wo jede möglichen Zeichenkette <math>w\in\Sigma^*</math> genau eine Zahl <math>\alpha_\sigma^w\in\mathbb N</math> produziert) [[Umkehrfunktion|umkehrt]], die für alle Worte <math> \sigma_{i_1}\ldots\sigma_{i_L}\in\Sigma^{2+} </math>jedweder Länge <math>L\in\mathbb N</math> der optimalen Konvention gehorcht, dass

<math> \alpha_\sigma^{\sigma_{i_1}\ldots\sigma_{i_L}}=\sum_{p=1}^L i_p m^{L-p} </math>

== Beispiele ==

=== Binäre Standardnummerierung mit [[Haskell (Programmiersprache)|Haskell]] ===
Sei <math>\Sigma = \{1,2\}</math> mit <math>(1,2)=(\sigma_1,\sigma_2)</math>.

Die Elemente der Menge <math>\Sigma^*</math> lassen sich systematisch auflisten:

:<math>\Sigma^*=\{\epsilon, 1, 2, 11, 12, 21, 22, 111, 112, 121, 122, 211, 212, 221, 222, \ldots\}</math>

Als i-tes Wort in der Liste erscheint stets <math>\nu_\sigma^i</math>.

<math>\nu_\Sigma^8=112</math> entspricht <math>\alpha_\sigma^{112} = \alpha_\sigma^{\sigma_1\sigma_1\sigma_2}= 1 \cdot 2^2 + 1 \cdot 2^1 + 2 \cdot 2^0 = 8</math>.

Mithilfe eines [[Haskell (Programmiersprache)|Haskell]]-Zeileninterpreters lässt sich Letzteres schnell überprüfen:

<syntaxhighlight lang="haskell">
strings chars = [] : [ string ++ [char] | string <- strings chars, char <- chars ]

zip [0..16] (strings "12")
</syntaxhighlight>
:[(0,""),(1,"1"),(2,"2"),(3,"11"),(4,"12"),(5,"21"),(6,"22"),(7,"111"),(8,"112"),(9,"121"),(10,"122"),(11,"211"),(12,"212"),(13,"221"),(14,"222"),(15,"1111"),(16,"1112")]

Deutlich wird dabei, dass unser herrschendes [[Stellenwertsystem]] angesichts der zu überspringenden führenden Nullen '''keine''' Standardnummerierung im Sinne obiger Definition ergibt:

<syntaxhighlight lang="haskell">
zip [0..12] (strings "0123456789")
</syntaxhighlight>
:[(0,""),(1,"0"),(2,"1"),(3,"2"),(4,"3"),(5,"4"),(6,"5"),(7,"6"),(8,"7"),(9,"8"),(10,"9"),(11,"00"),(12,"01")]

<syntaxhighlight lang="haskell">
zip [0..12] (strings "1234567890")
</syntaxhighlight>
:[(0,""),(1,"1"),(2,"2"),(3,"3"),(4,"4"),(5,"5"),(6,"6"),(7,"7"),(8,"8"),(9,"9"),(10,"0"),(11,"11"),(12,"12")]

<syntaxhighlight lang="haskell">
drop 99 $ zip [0..121] (strings "123456789X")
</syntaxhighlight>
:[(99,"99"),(100,"9X"),(101,"X1"),(102,"X2"),(103,"X3"),(104,"X4"),(105,"X5"),(106,"X6"),(107,"X7"),(108,"X8"),(109,"X9"),(110,"XX"),(111,"111"),(112,"112"),(113,"113"),(114,"114"),(115,"115"),(116,"116"),(117,"117"),(118,"118"),(119,"119"),(120,"11X"),(121,"121")]

<syntaxhighlight lang="haskell">
drop 90 $ zip [0..100] (strings "123456789")
</syntaxhighlight>
:[(90,"99"),(91,"111"),(92,"112"),(93,"113"),(94,"114"),(95,"115"),(96,"116"),(97,"117"),(98,"118"),(99,"119"),(100,"121")]

=== Standartnummerierung bei der Indizierung mit Buchstaben ===
Eine bekannte Anwendung der Standardnummerierung ergibt sich, wenn man als Alphabet die Großbuchstaben des [[Lateinisches Alphabet|Lateinischen Alphabet]] verwendet, d. h. <math>\Sigma = \{\mathrm{A},\mathrm{B},\mathrm{C},\ldots,\mathrm{Z}\}</math>.

Die Elemente der Menge der nicht leeren Zeichenketten <math>\Sigma^+</math> lassen sich nun systematisch auflisten:
:<math>\Sigma^+=\{\mathrm{A}, \mathrm{B}, \ldots, \mathrm{Y}, \mathrm{Z}, \mathrm{AA}, \mathrm{AB}, \ldots, \mathrm{AY}, \mathrm{AZ}, \mathrm{BA}, \mathrm{BB}, \ldots, \mathrm{ZY}, \mathrm{ZZ}, \mathrm{AAA}, \mathrm{AAB}, \ldots\}</math>

Diese Auflistung wird in vielen Tabellenkalkulationsprogrammen zur Bennenung der Spalten verwendet.

In langen Aufzählung, die nach dem Schema a) b) c) ... durchindiziert sind, findet eine Abwandlung dieses Verfahrens gelegentlich ebenfalls Anwendung, falls mehr als 26 Items indiziert werden müssen, dann folgt auf z) das Item aa).

Auch Varianten mit einer kleinerne Menge an Buchstaben sind gebräuchlich, beispielsweise für die [[Benennung veränderlicher Sterne]].

[[Kategorie:Theoretische Informatik]]

Standardnummerierung - Versionsgeschichte

imported>Aka: /* Standartnummerierung bei der Indizierung mit Buchstaben */ Abkürzung korrigiert