Головна Головна -> Реферати українською -> Дисертації та автореферати -> КЛАСИ ФУНКЦІЙ ТА ЧИСЕЛ, ЩО ВИЗНАЧАЮТЬСЯ ТРАНСФОРМАЦІЙНИМИ ТА ГЕНЕРУЮЧИМИ МОДЕЛЯМИ ОБЧИСЛЕНЬ

КЛАСИ ФУНКЦІЙ ТА ЧИСЕЛ, ЩО ВИЗНАЧАЮТЬСЯ ТРАНСФОРМАЦІЙНИМИ ТА ГЕНЕРУЮЧИМИ МОДЕЛЯМИ ОБЧИСЛЕНЬ

Назва:
КЛАСИ ФУНКЦІЙ ТА ЧИСЕЛ, ЩО ВИЗНАЧАЮТЬСЯ ТРАНСФОРМАЦІЙНИМИ ТА ГЕНЕРУЮЧИМИ МОДЕЛЯМИ ОБЧИСЛЕНЬ
Тип:
Реферат
Мова:
Українська
Розмiр:
15,80 KB
Завантажень:
203
Оцінка:
 
поточна оцінка 5.0


Скачати цю роботу безкоштовно
Пролистати роботу: 1  2  3  4  5  6  7  8  9  10 
Київський національний університет
імені Тараса Шевченка
КАРНАУХ Тетяна Олександрівна
УДК 519.7+510.5
КЛАСИ ФУНКЦІЙ ТА ЧИСЕЛ, ЩО ВИЗНАЧАЮТЬСЯ
ТРАНСФОРМАЦІЙНИМИ ТА ГЕНЕРУЮЧИМИ МОДЕЛЯМИ ОБЧИСЛЕНЬ
01.01.08 — математична логіка, теорія алгоритмів
і дискретна математика
Автореферат
дисертації на здобуття наукового ступеня
кандидата фізико-математичних наук
Київ – 2005
Дисертацією є рукопис.
Робота виконана на кафедрі теоретичної кібернетики Київського національного університету імені Тараса Шевченка
Науковий керівник: доктор фізико-математичних наук, професор
ЛІСОВИК Леонід Петрович,
Київський національний університет імені Тараса Шевченка,
професор кафедри теорії та технології програмування
Офіційні опоненти: доктор фізико-математичних наук, професор
КАПІТОНОВА Юлія Володимирівна,
Інститут кібернетики імені В.М.Глушкова НАН України,
завідувач відділу теорії цифрових автоматів
кандидат фізико-математичних наук, доцент
ГАНЮШКІН Олександр Григорович,
Київський національний університет імені Тараса Шевченка,
доцент кафедри алгебри та математичної логіки
Провідна установа: Інститут математики НАН України, відділ топології
м. Київ
Захист відбудеться “--” листопада 2005 року о 14 годині на засіданні спеціалізованої вченої ради Д .001.18 Київського національного університету імені Тараса Шевченка за адресою: 03680, м. Київ-127, проспект академіка Глушкова, 2, корп. 7, Київський національний університет імені Тараса Шевченка, механіко-математичний факультет.
З дисертацією можна ознайомитись у бібліотеці Київського національного університету імені Тараса Шевченка (вул. Володимирська, 58).
Автореферат розісланий “--6 ” жовтня 2005 року.
Вчений секретар спеціалізованої вченої ради ----------------В.В.Плахотник


ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
Актуальність теми. Теорія алгоритмів бере свій початок з середини 30-х років 20-го сторіччя, коли відбулись перші спроби дати точний математичний еквівалент загальному інтуїтивному представленню про алгоритм. Одним з таких уточнень поняття алгоритму є машини Тьюрінга. Одночасно з уточненням поняття алгоритму точне математичне значення отримує поняття обчислюваності.
На сьогодні доведено, що такі моделі, як числення рівностей Ербрана та Гьоделя, машини Тьюрінга, канонічні системи Поста, нормальні алгорифми Маркова мають однакові обчислювані можливості для класа арифметичних функцій (тобто функцій типу N0N0), а саме, задають клас частково рекурсивних функцій. За тезою Чьорча, сформульованою в 1936 році, клас функцій, обчислюваних за допомогою алгоритмів у широкому інтуїтивному розумінні, співпадає з класом частково рекурсивних функцій. За даних обставин загальна теорія частково рекурсивних функцій набула бурхливого розвитку.
В роботі Т. Хаяші 1975 року та в роботі Р. Гілмана 1996 року зявляються арифметичні функції, які задаються як неспадні функції, множина значень яких співпадає з множиною довжин слів мови. Якщо мову задано граматикою, то отримуємо принципово новий підхід до задання арифметичної функції – за допомогою граматики. Даний підхід є дуже цікавим для досліджень, оскільки дозволяє звузити загальний клас частково рекурсивних функцій за рахунок обмежень, які вводяться для граматики. Зокрема Хаяші та Ґілман розглядають індексні граматики.
Інша гілка розвитку теорії оперує з поняттям обчислюваного дійсного числа, яке вперше було введено в 1936 році А. Тьюрінгом. За першим означенням Тьюрінга під обчислюваним числом ми розуміємо число, двійковий розклад дробової частини якого є обчислюваним на машині Тьюрінга. Фактично обчислюваним числом є сама машина Тьюрінга, яка його обчислює. Дане означення має ряд суттєвих недоліків, оскільки, наприклад, унеможливлює побудову за двома обчислюваними числами, обчислюваного числа, яке є їх сумою. Тому надалі воно зазнало змін. Інші означення обчислюваного числа були сформульовані в 1936 році Банахом і Мазуром. Серед радянської школи слід зазначити внесок Шаніна в дослідження обчислюваних чисел. Крім різних концепцій обчислюваності дійсних чисел, дослідження розгортались і навколо такого напрямку як обчислювальні можливості алгоритмічних пристроїв для задання обчислюваних чисел.

Завантажити цю роботу безкоштовно
Пролистати роботу: 1  2  3  4  5  6  7  8  9  10 



Реферат на тему: КЛАСИ ФУНКЦІЙ ТА ЧИСЕЛ, ЩО ВИЗНАЧАЮТЬСЯ ТРАНСФОРМАЦІЙНИМИ ТА ГЕНЕРУЮЧИМИ МОДЕЛЯМИ ОБЧИСЛЕНЬ

BR.com.ua © 1999-2017 | Реклама на сайті | Умови використання | Зворотній зв'язок