|
ИСТИНА |
Войти в систему Регистрация |
ИПМех РАН |
||
Unipotent dynamics on a torus and complexity functions of subwords of powers of twoдипломная работа (Магистр)
- Научный руководитель: Канель-Белов Алексей Яковлевич
- Автор: Mohammadmehdi Golafshan
- Тип: Магистр
- Организация, в которой проходила защита: Московский Физико технический Институт
- Год защиты: 2020
- Аннотация: The main goal of my Master’s thesis is to present and apply the notions of complexity function to some directly connected properties of the words. This work is strongly related to the courses Combinatorics on Words and Symbolic Dynamics that I followed. Let w be a (possibly infinite) word of symbols from an alphabet. In computer science, the complexity function of a word is the function pw(n) of a positive integer n to be the number of different factors (consecutive subwords) of length n occurring in the word w. After having introduced this complexity function, I present the notion of Sturmian words. Then I study the complexity of Sturmian words which are aperiodic words with the least factor complexity. I show in my master’s thesis a well-known characterization of Sturmian words as codings of rotations with an irrational angle and a convenient partition of the perimeter of the circle. Making use of that alternative definition, I am able to show that, for all n > 0, the word made by the left-most (most significant digit) of the sequence 2n, w = 248136125... can be described by these words (otherwise stated the jth digit occurring in w is the left-most digit in the decimal expansion of 2j ). The next section of my Master’s thesis explains that the sequence made by powers of 2 one the circle with irrational angle is dense. I prove in that case that pw(n). Finally, the last section is dedicated to the very intersting relation existing between k-dimensional torus with the sequence of left-most digit occurring in the decimal representation of 2 to the power nk, where n, k are positive integers. Then by using Kronecker’s theorem in Ergodic theory and Weyl theorem in Fourier Analysis, I will prove these sequences are dense on the k-dimensional torus. In the end, I would try to find some properties of complexity functions of these sequences. The main theorem in this thesis is: Theorem. Given a natural k. The word wn is considered, nth term of which is the first digit of the number 2nk in decimal representation. Then there is a polynomial P(k) of degree d(d + 1)/2 such that in this sequence the number of distinct words; of length k for sufficiently large k is equal to P(k). The thesis was supported by Russian science foundation grant N 17-11-01377
- Добавил в систему: Белов Алексей Яковлевич
Прикрепленные файлы
| № | Имя | Описание | Имя файла | Размер | Добавлен |
|---|---|---|---|---|---|
| 1. | Отзыв Митрофанова | Otziv_Mitr.pdf | 85,1 КБ | 26 июня 2020 [AlexeiBelov] | |
| 2. | Отзыв Научного Руководителя | report_on_Mehdi_thesis_by_Belov.doc | 29,5 КБ | 26 июня 2020 [AlexeiBelov] | |
| 3. | Отзыв Ильи Иванова-Погодаева | report_on_Mehdi_thesis_by_Ivanov-Pogodaev.doc | 30,5 КБ | 26 июня 2020 [AlexeiBelov] | |
| 4. | Презентация | combinepdf3.pdf | 4,5 МБ | 26 июня 2020 [AlexeiBelov] | |
| 5. | Полный текст | Thesis18.pdf | 1,2 МБ | 26 июня 2020 [AlexeiBelov] |