Анотація до роботи:

Карнаух Т.О. Класи функцій та чисел, що визначаються трансформаційними та генеруючими моделями обчислень. – Рукопис.

Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.01.08 – математична логіка, теорія алгоритмів і дискретна математика. – Київський національний університет імені Тараса Шевченка, Київ, 2005.

В роботі розглядаються можливості моделей обчислень з різними обмеженнями (на тип памяті та/або на подання результату обчислень) щодо задання арифметичних функцій, дійсних чисел та дійсних функцій, а також звязки між класами дійсних функцій, обчислюваних строгими реалами, та класами функцій, описуваних методами класичного аналізу.

В роботі досліджено властивості граматик з памяттю, зокрема з нестираючою стековою памяттю; побудовано гніздові стекові генератори, що обчислюють трансцендентні числа; для неперервної всюди визначеної дійсної функції в термінах класичного аналізу отримано необхідні і достатні умови того, що її можна задати строгим реалом.

В дисертаційній роботі розглядаються можливості моделей обчислень з різними обмеженнями (на тип памяті та/або на подання результату обчислень) щодо задання арифметичних функцій, дійсних чисел та дійсних функцій, а також досліджуються звязки між класами дійсних функцій, обчислюваних строгими реалами, та класами функцій, описуваних методами класичного аналізу. Всі результати отримано вперше.

Сформулюємо основні результати дисертації

— досліджено властивості граматик з нестираючою стековою памяттю (зокрема доведено рекурсивність відповідних мов);

— побудовано гніздові стекові генератори, що обчислюють трансцендентні числа;

— доведено достатню умову, за виконання якої всюди визначена дійсна функція, задана монотонною послідовністю неперервних систем кубиків, може бути задана строгим реалом;

— для неперервної всюди визначеної дійсної функції в термінах класичного аналізу отримано необхідні і достатні умови того, що її можна задати строгим реалом.

Крім цього в дисертації отримано низку цікавих результатів:

— отримано характеризацію класа функцій, абсолютно обчислюваних за допомогою індексних граматик, в термінах систем лінійних рекурентних співвідношень;

— побудовано машини Тьюрінга, що обчислюють трансцендентні числа, не обчислювані гніздовими стековими генераторами;

— для дійсної функції в термінах класичного аналізу отримано необхідні умови того, що її можна задати строгим R-перетворювачем;

— побудовано приклад неперервної всюди визначеної на множині R дійсної функції, яка задається скінченним реалом, строгим магазинним R-перетворювачем, але не задається жодним строгим реалом;

— доведено, що клас неперервних всюди визначених на множині R дійсних функцій, що задаються строгими реалами, строго включається в клас неперервних всюди визначених на множині R дійсних функцій, що задаються строгими R-перетворювачами.

Результати дисертації отримано за допомогою стандартних методів теорії формальних мов, методів теорії чисел, метода діагоналізації Кантора, а також методом задання функції за допомогою апроксимацій.

Публікації автора:

1. Карнаух Т.О. Класи пам'яті R-перетворювачів. //Вісник Київського університету. Серія: фіз.-мат. науки. – 2003. – №2. – C. 148-154.

2. Карнаух Т.О. Обчислюваність трансцендентних чисел генераторами з гніздовою стековою пам'яттю. // Вісник Київського університету. Серія: фіз.-мат. науки. – 2003. – №3. – C. 216-220.

3. Карнаух Т.О. Граматики з пам'яттю. // Вісник Київського університету. Серія: фіз.-мат. науки. – 2004. – №2. – C. 245-252.

4. Карнаух Т.О. Про один метод апроксимації дійсних функцій // Вісник Київського університету. Серія: фіз.-мат. науки. – 2004. – №3. – C. 215-222.

5. Карнаух Т.О. Моделювання дійсних функцій строгими R-перетворювачами. // Вісник Київського університету. Серія: фіз.-мат. науки.–2004. – №4. – C. 192-200.

6. Лисовик Л.П., Карнаух Т.А. О классе функций, вычислимых с помощью индексных грамматик. // Кибернетика и системный анализ. – 2003. – №1. – C. 108-115.

7. Карнаух Т.О. Особливості моделювання неперервних функцій R-перетворювачами. // "Dynamical system modelling and stability investigation", thesis of conference reports. – 2003. – C. 401.

8. Карнаух Т.О. Словарні методи побудови трансцендентних чисел. // Десята міжнародна наукова конференція імені академіка М. Кравчука, 13-15 трав. 2004р., Київ: Матеріали конф. – К.:Задруга, 2004. – C. 123.

9. Карнаух Т.А. Об одном механизме управления выводом в грамматиках. // Дискретные модели в теории управляющих систем: VI международная конференция: Москва, 7-11 декабря 2004 г. Труды. – М.: Издательский отдел Факультета ВМиК МГУ им. М.В.Ломоносова, 2004. – С.116-120.