Представление строк, которые мы используем в программировании в математической нотации

Question

Теперь я программист, который недавно обнаружил, насколько он плох, когда дело доходит до математики, и решил немного сосредоточиться на этом с этого момента, поэтому Я прошу прощения, если мой вопрос оскорбляет ваш интеллект .

В математике есть ли концепция строк, которая используется в программировании? то есть перестановка символов.

В качестве примера, скажем, я хотел перевести следующее в математическую запись:

let s be a string of n number of characters.

Причина в том, что я хотел бы использовать это представление для поиска других вещей о строке s, таких как ее длина: len(s).

Как вы формально представляете такую ​​вещь в математике?

---

Говоря более практично, скажем так, я хотел математически объяснить такую ​​функцию:

fitness(s,n) = 1 / |n - len(s)|

Или написано более "дружественным к программированию" способом:

fitness(s,n) = 1 / abs(n - len(s))

Я использовал эту функцию, чтобы объяснить, как работает фитнес-функция для данного GA; вопрос был в том, чтобы найти строки из 5 символов, и мне нужно было отсортировать решения в порядке возрастания в соответствии с их оценкой пригодности, указанной в приведенной выше функции.

Итак, мой вопрос, как вы представляете вышеуказанный псевдокод в математической записи?

Answer 1

Вы можете использовать нотацию теории языка, которая используется для обсуждения таких вещей, как обычные языки, контекстно-свободные грамматики, теория компиляторов и т. Д. Краткий обзор:

• Наборсимволы известны как алфавит .Вы можете написать: «Пусть A - алфавит ASCII, набор, содержащий 128 символов ASCII».

• A string - последовательностьперсонажей.ε - пустая строка.

• Набор строк формально известен как язык .Общее утверждение: «Пусть s ∈ L будет строкой на языке L .»

• Объединение алфавитовпроизводит наборы строк (языков). A представляет все 1-символьные строки, A A , также записанные A ² , представляет собой наборвсе две строки символов. A ⁰ - набор всех строк нулевой длины, который точно равен A ⁰ = {ε}.(Он содержит ровно одну строку, пустую строку.)

• A ^* - это специальная запись, представляющая набор всех строк валфавит A любой длины.То есть A ^* = A ⁰ ∪ A ¹ ∪ A ² ∪ A ³ ....Вы можете узнать эту запись из регулярных выражений.

• Для длины используйте столбцы абсолютных значений.Длина строки с равна | с |.

Итак, для вашего утверждения:

lets это строка из n символов.

Вы можете написать:

Пусть A будет набором символов и s ∈ A ⁿ - строка из n символов.Длина с равна | с |= n .

Answer 2

Математически вы объяснили fitness(s, n) очень хорошо, если len(s) четко определено.

В текстах CS строка s над набором S определяется как конечный упорядоченный список элементов S , а ее длина часто записывается как | s | - но это всего лишь обозначение, и оно не меняет (математического) значения, лежащего в основе вашего определения fitness, что совершенно ясно, как вы его написали.