Головна Головна -> Реферати українською -> Дисертації та автореферати -> дисертації на здобуття наукового ступеня кандидата фізико-математичних наук

дисертації на здобуття наукового ступеня кандидата фізико-математичних наук

Назва:
дисертації на здобуття наукового ступеня кандидата фізико-математичних наук
Тип:
Реферат
Мова:
Українська
Розмiр:
13,54 KB
Завантажень:
157
Оцінка:
 
поточна оцінка 5.0


Скачати цю роботу безкоштовно
Пролистати роботу: 1  2  3  4  5  6  7  8 
Київський національний університет імені Тараса Шевченка
УДК 510.5
БЄЛЯЄВ Володимир Миколайович
m-звідність з інформаційними обмеженнями
01.01.08 – математична логіка, теорія алгоритмів
і дискретна математика
Автореферат дисертації на здобуття наукового ступеня
кандидата фізико-математичних наук
Київ-2006
Дисертацією є рукопис
Робота виконана в Одеському національному університеті
імені І.І. Мечникова Міністерства освіти і науки України
Науковий керівник
доктор фізико-математичних наук, професор Варбанець
Павло Дмитрович, Одеський національний університет імені І.І. Мечникова,
завідувач кафедри комп’ютерної алгебри та дискретної математики.
Офіційні опоненти:
доктор фізико-математичних наук, професор Оманадзе Роланд Шалвович,
Тбіліський державний університет імені Ів. Джавахішвілі, Інститут прикладної
математики імені І. Векуа, професор кафедри дискретної математики, м. Тбілісі, Грузія;
доктор фізико-математичних наук, професор Лісовик Леонід Петрович,
Київський національний університет імені Тараса Шевченка,
професор кафедри теорії програмування
Провідна установа
Інститут кібернетики імені В. М. Глушкова Національної
академії наук України
Захист відбудеться “ 13 березня 2006 р. о 14 годині на засіданні
спеціалізованої вченої ради Д .001.18 при Київському національному
університеті імені Тараса Шевченка за адресою:
03127, м. Київ, просп. академ. Глушкова 2, корпус № 7,
механіко-математичний факультет.
З дисертацією можна ознайомитись у бібліотеці Київського національного
університету імені Тараса Шевченка (вул. Володимирська, 58).
Автореферат розісланий “ 24 ” січня 2006 р.
Вчений секретар
спеціалізованої вченої ради Плахотник В.В.
Загальна характеристика роботи
Актуальність теми. Поняття алгоритму започатковувалось на самих ранніх етапах роз-витку математики. Для відповіді на питання про існування алгоритмічного рішення можна обмежитись інтуїтивним поняттям алгоритму, оскільки достатньо лише запропонувати рішення і переконатися в тому, що процедура рішення є ефективною. У випадку ж необхідності упевнитися в зворотному, тобто у відсутності алгоритму, необхідна формальна ха-рактеризація алгоритму – потрібно показати, що застосування будь-якого алгоритму не дасть бажаного рішення. Такі характеризації були дані лише в 30-их роках минулого сторіччя в роботах К. Гьоделя, А. Тюрінга, А. Чьорча, Ж. Ербрана, Е. Поста і С. Кліні. Ці дослідники визначили різні поняття рекурсивних функцій і відповідні поняття рекурсивно перераховних множин, використовуючи, зокрема, абстрактні обчислювальні машини, схеми правил чи породжувальні граматики. Усі ці, на перший погляд, різні підходи визначали один клас функцій і клас множин.
Початок розвитку найважливіших розділів теорії алгоритмів – теорії рекур-сивно перераховних множин і ступенів нерозв'язності – відносяться до ще більш пізнього часу – середини 40-их – початку 50-их років. Саме в ті роки були опубліковані фундаментальні роботи Е. Поста і С. Кліні, що містили не тільки первісні методи і результати теорії, але й визначили на найближчі два-три деся-тиріччя шляхи її розвитку.
Предметом дисертаційної роботи є дослідження певного різновиду алго-ритмічних звідностей. У теорії рекурсії алгоритмічні звідності являють собою ос-новний засіб класифікації підмножин натурального ряду за складністю. Як відомо, існує два стандартних способи ввести алгоритмічну складність для множин. Один з них запропонований А. М. Колмогоровим та іншими дослідниками і базується на зіставленні кожному початковому сегменту множини довжини його найкоротшої розв’язувальної програми для деякого стандартного обчислювального пристрою. Цей спосіб характеризує “індивідуальну” (абсолютну, у природному змісті слова) складність множини.
Інший спосіб (історично він з'явився раніше) встановлює деякий передпоря-док на множині всіх множин даної сукупності. Алгоритмічні звідності саме слугують засобом установлення таких передпорядків.

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



Реферат на тему: дисертації на здобуття наукового ступеня кандидата фізико-математичних наук

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