А   Б  В  Г  Д  Е  Є  Ж  З  І  Ї  Й  К  Л  М  Н  О  П  Р  С  Т  У  Ф  Х  Ц  Ч  Ш  Щ  Ю  Я 


Алгоритмічна проблема

Алгоритмічна проблема Пуанкаре може бути сформульована в чисто алгебраїчних термінах. Дійсно, як довів Вальдхаузен[96], Будь-які два сплетення Хегора однакового роду стандартної сфери S3 еквівалентні.

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

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

Багато відомих алгоритмічні проблеми - алгебри і топології можуть бути сформульовані як задачі дослідження можливості розв'язання певних класів відносин еквівалентності і негативні рішення таких проблем зазвичай виходять у вигляді тверджень про наявність нерозв'язних відносин серед певного тину відносин еквівалентності.

Дві основні алгоритмічні проблеми можуть бути визначені наступним чином.

Крім алгоритмічних проблем до математичної теорії граматик відносяться також проблеми оцінки складності виведення в граматиках.

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

Зв'язок між алгоритмічними проблемами і ентропійними характеристиками груп //Докл.

Третя частина, Алгоритмічні проблеми (§ 14 - 23), є кульмінаційною. У ній викладається ряд фундаментальних результатів теорії, які на щастя, піддаються популяризації. Більш детальна характеристика змісту книги дана у вступі.

Тотожність ПРОБЛЕМА - алгоритмічна проблема розпізнавання рівності (тотожності) слів в алгебраїч.

Більш формальні формулювання цих та інших алгоритмічних проблем використовують теорію нумераций і теорію рекурсивних множин. Тоді G є Факторгруппа вільної групи F (X) з базою X за нормальною підгрупі N, породженої безліччю R. Для групи G проблема рівності можна вирішити тоді і тільки тоді коли безліч a (N) рекурсивно.

Більш формальні формулювання цих та інших алгоритмічних проблем використовують теорію нумераций і теорію рекурсивних множин. Саме, нехай О (XRy - кінцевий код групи. Тоді G є Факторгруппа вільної групи F (X) з базою X за нормальною підгрупі N, породженої безліччю R. Для групи G проблема рівності можна вирішити тоді і тільки тоді коли безліч a (N) рекурсивно.

Подібні питання і утворюють коло алгоритмічних проблем теорії граматик.

Аналогічно, позитивно була б вирішена алгоритмічна проблема спряженості елементів в нильпотентних групах, якби в кожній Ніль-потентность групі G з кінцевим числом породжують для будь-якої пари неспряжених елементів а, видання існував нормальний дільник N кінцевого індексу такий, що образи а, видання в фактор-групі GIN були також неспряженість.

Схема Патерсона завжди зупиняється.

Крім проблеми еквівалентності представляють інтерес і інші алгоритмічні проблеми.

У роботі[50]з'ясована тісний зв'язок між класичними алгоритмічними проблемами і поняттям, що апроксимується алгебри щодо відповідних предикатів. Після цього вже досить просто вирішуються проблеми рівності та входження для нильпотентних груп, а також деякі інші алгоритмічні питання. Треба зауважити, що розвиток і застосування ідей, що містяться в[50], І в даний час ще далекі від свого вичерпання.

Поліциклічні групи-найбільш широкий клас груп, в якому всі класичні алгоритмічні проблеми знайшли позитивне рішення.

Як вже зазначалося в § 1 + 1 серед алгоритмічних проблем особливе місце займають ті в яких потрібно знайти алгоритм для обчислення всіх значень деякої функції.

цей історичний проміжок - знаменується чіпаючи завданням математичних алгоритмів і постановкою ряду Кфупних алгоритмічних проблем, які не піддавалися решенік традиційними методами. У їх числі знамениті геометричні завдання стародавніх греків - трисекція кута і квадратура кола, проблема можливості розв'язання рівнянь в радикалах, яка призвела до створення Деора Галуа, а також ряд алгоритмічно нерозв'язних завдань, На цьому етапі відбулося усвідомлення поняття алгоритму як окремого об'єкта вивчення, що, в кінцевому підсумку, призвело до створення строгої математичної теорії алгоритмів.

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

Вільні розв'язні групи є ФА -, ФАС-групами, а тому в них позитивно вирішуються алгоритмічні проблеми рівності та пов'язаності. Фактори нижнього центрального ряду вільної розв'язної групи є вільна абелева група.

І нарешті хоча визначення звичайної діаграми Вороного на випадок простору довільної розмірності очевидно, її побудова пов'язано зі значними алгоритмічними проблемами.

Якщо ми фіксуємо Некро п і обмежуємося розглядом проблеми входження в М тільки для перших га натуральних чисел, то ми отримуємо обмежену алгоритмічну проблему. Величина К (М, п) інтуїтивно висловлює кількість інформації, доурую треба мати, щоб можна було вирішити цієї обмеженої проблему. Зокрема, безліч М рекурсивно тоді і тільки тоді коли К (М, га) обмежена зверху нск-рій константою.

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

Перша досліджує алгоритми з точки зору встановленого ними відповідності між вихідними даними і результатами; до неї відносяться, зокрема, проблеми побудови алгоритму, що володіє тими чи іншими властивостями - алгоритмічні проблеми.

Можна було навести ще багато прикладів алгоритмічно НЕ-р азрешімих проблем, з ними ми ще зустрінемося при вивченні теорії граматик алгоритмічних мов. До типу алгоритмічних проблем відноситься і теорема Геделя про неповноту арифметичної логіки. Перш за все уточнимо основні поняття, що використовуються в теоремі Геделя.

У заключній частині роботи розглядаються різноманіття асоціативних алгебр з тотожністю Лієв нильпотентних фіксованого індексу. Увага зосереджена на розв'язання алгоритмічних проблем в цих многовидах. Показано, що алгоритмічно дозволимо питання про здійсненності тотожності Лієв нильпотентних фіксованого індексу в звичайно породженою алгебри, в якій можна вирішити проблему рівності слів. Також доведено, що в різноманітті Лієв нильпотентних алгебр проблема рівності слів вирішується за допомогою алгоритму, що використовує техніку базисів Гребнера.

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

З іншого боку, приблизно в той же час, А. Пуанкаре поставив проблему, яку зазвичай називають алгоритмічної проблемою Пуанкаре.

Теорія алгоритмів виникла й оформилася в самостійну дисципліну в 30 - 40 - х рр. нашого століття. Приблизно в цей же час, а також у наступні роки були отримані вирішення низки класичних алгоритмічних проблем математичної логіки, алгебри і топології. Надалі намітилася зв'язок теорії алгоритмів з кібернетикою: проектуванням обчислювальних пристроїв, програмуванням, моделюванням біологічних об'єктів (хоча в досить скромних поки масштабах), математичної лінгвістикою. Виявилося, що бувають алгоритмічні проблеми (рекурсивно) розв'язні і нерозв'язні. Останні навіть розрізняють за ступенями нерозв'язності.

Для цього досить уявити i; у вигляді послідовної композиції трьох програм: програми перекладу з десяткової системи в унарна, програми 31 програми перекладу з унарною системи в десяткову, (Тут напрошується порівняння з електронними обчислювальними машинами, що працюють в двійковій системі числення; в них є пристрій, або програма, для пераработкі вихідних даних з десяткової системи в двійкову, а також пристрій, або програма, для перекладу остаточної програми знову в десяткову систему. Корисно помітити, що хоча ми маємо намір приділяти головну увагу обчисленню числових функцій, проте це не обмежує по суті природи алгоритмічних проблем, що вирішуються на машинах Тьюринга. Оскільки таке ж зауваження можна зробити і щодо слова, що зображує результуючі дані то ясно, що алгоритм пошуку рішення задачі можна інтерпретувати як алгоритм обчислення значення числової функції по заданому значенню її аргументу. подібна арифметична інтерпретація (або коротше - арифметизации) часто застосовується в математичній логіці і теорії алгоритмів; ми з нею ще зустрінемося в цьому параграфі.

Відповідно двом можливим альтернативам, алгоритмічну проблему називають можливо розв'язати або нерозв'язною. Алгоритмічні проблеми розглядаються переважно для напівгруп, заданих тих чи інших ефективним способом; найбільш типово їх розгляд для напівгруп, заданих визначальними співвідношеннями.
 Властивість комплексу бути стягують або замкнутого різноманіття - гомеоморфними сфері 5 - стає алгоритмічно нераспознаваемой для п 3 (комплекси) та п 5 (різноманіття), як зазначив С.П.Новіков на початку 1960 - х рр., Використовуючи конструкції гомологической алгебри, хоча для п 4 відповідь також навряд чи позитивний. Зауважимо, що проблема гомеоморфізму двовимірних комплексів і проблема гомеоморфними тривимірного різноманіття з краєм стягують, ймовірно, можна розв'язати. найпростіші алгоритмічні проблеми теорії тривимірних замкнутих різноманіть і вузлів, мабуть, також можна розв'язати, хоча приклад завдання про розпізнаванні тривіального вузла (вище) показує, що, з огляду на алгебраїчних складнощів теоретико-груповими методами, незважаючи на наявність критерію тривіальності вузла, це питання я не можу припинити.

Рольф[402]доводить, що структура FM (2 + 2 2) містить нескінченний ланцюг. Зауважимо, що-все основні алгоритмічні проблеми для модулярних структур залишаються відкритими. Елемент а структури з відношенням А і з I називається нормальним (субнормальний), якщо а А 1 (соотв. Це поняття нормального елемента є узагальненням нормального дільника в структурі підгруп групи, відмінне від відомого поняття нормальності в сенсі Куро-ша. Кінцева мета спеціальної теорії мереж Петрі - автоматичний аналіз властивостей мереж, їх автоматичні синтез і перетворення, на підставі чого можуть бути побудовані практичні алгоритми аналізу, синтезу і перетворень дискретних систем, що моделюються мережами. Зокрема, корисно знайти алгоритми, за допомогою яких для будь-якої пред'явленої мережі можна встановити, чи володіє вона цікавлять нас властивістю - чи є вона обмеженою, живою, стійкої і т.п. В першу чергу потрібно з'ясувати існування таких алгоритмів. Ці питання формулюються як масові алгоритмічні проблеми для мереж: проблема обмеженості (чи існує алгоритм, який дозволяє дізнатися, чи є дана мережа обмеженою), проблема потенційної жвавості переходів, проблема жвавості мереж, проблема стійкості проблема безпеки. Кажуть, що проблему можна вирішити, якщо відповідний алгоритм розпізнавання властивостей існує, в іншому випадку проблема нерозв'язна.

Доведено наступний результат про равносильности різних концепцій поняття алгоритму: класи функцій, обчислюваних на машинах Тьюрінга, частково рекурсивних функцій, обчислюваних за допомогою нормальних алгорифм Маркова ( аналогічні класи функцій при інших концепціях поняття алгоритму), збігаються. На думку більшості сучасних математиків, цей клас функцій адекватний класу інтуїтивно В. Таке ототожнення дозволяє надати математичность алгоритмическим проблем.

Цей факт, встановлений в 1936 А. Church), є одним з фундаментальних результатів спільної алгоритмів теорії. На ньому засновані (або можуть бути засновані) всі відомі негативні рішення алгоритмічних проблем.
 Прийняті угоди дозволяють проводити аналіз багатьох природних і компактних програмних реалізацій алгоритмів сортування масивів. У розділах 67і 6.8 розглядається драйвер, який служить ілюстрацією того, як слід використовувати реалізації угруповань в більш загальних контекстах, а також різні реалізації типів даних. І хоча ми завжди будемо приділяти належну увагу вимогам до організації програмних пакетів, основні зусилля будуть спрямовуватися на розв'язання алгоритмічних проблем, до розгляду яких ми зараз і переходимо.

Визначення поняття алгоритму було використано, для доказу неіснування алгоритмів для вирішення того чи іншого класу задач. Так, наприклад, Черч показав, що не існує алгоритму, що вирішує проблему розв'язання числення предикатів. Проблеми, які полягають в знаходженні алгоритму, вирішую -, ного ту чи іншу нескінченну серію однотипних завдань, отримали назву алгоритмічних проблем. Нерозв'язність алгоритмічної проблеми означає, що, шуканий алгоритм неможливий. Останнім часом no - J Лучен ряд результатів, що відносяться до нерозв'язності алгоритмічних проблем в різних розділах математики. Ці результати є додатком математичної логіки до питань, які лежать поза нею.

Переходячи до багатокомпонентної динаміці сорбції, слід підкреслити, що в практичних додатках значення цього розділу теорії зростає. У той же час кількість публікацій по динаміці суміші явно недостатньо. ця ситуація в значній мірі пояснюється тими математичними труднощами, які виникають при спробах поширити локально-детерміновану модель (1) - (5) для опису динаміки суміші. Хоча чисто алгоритмічні проблеми і можуть бути вирішені експлуатація програм на ЕОМ вимагає непропорційно великих витрат машинного часу, причому в міру збільшення числа компонентів ці витрати різко зростають.

Визначення поняття алгоритму було використано, для доказу неіснування алгоритмів для вирішення того чи іншого класу задач. Так, наприклад, Черч показав, що не існує алгоритму, що вирішує проблему розв'язання числення предикатів. Проблеми, які полягають в знаходженні алгоритму, вирішую -, ного ту чи іншу нескінченну серію однотипних завдань, отримали назву алгоритмічних проблем. Нерозв'язність алгоритмічної проблеми означає, що, шуканий алгоритм неможливий. Останнім часом no - J Лучен ряд результатів, що відносяться до нерозв'язності алгоритмічних проблем в різних розділах математики. Ці результати є додатком математичної логіки до питань, які лежать поза нею.

Теорія алгоритмів виникла й оформилася в самостійну дисципліну в 30 - 40 - х рр. нашого століття. Приблизно в цей же час, а також у наступні роки були отримані рішення ряду класичних алгоритмічних проблем математичної логіки, алгебри і топології. Надалі намітилася зв'язок теорії алгоритмів з кібернетикою: проектуванням обчислювальних пристроїв, програмуванням, моделюванням біологічних об'єктів (хоча в досить скромних поки масштабах), математичної лінгвістикою. Виявилося, що бувають алгоритмічні проблеми (рекурсивно) розв'язні і нерозв'язні. Останні навіть розрізняють за ступенями нерозв'язності.

У наступні роки в універсальної алгебри виділяється два основних напрямки. Перше з них пов'язане з вивченням властивостей алгебраїчних систем і описом цих властивостей різними логічними засобами. Це призводить до розгляду класів алгебраїчних систем і способів конструювання класів. Другий напрямок пов'язаний з алгоритмічними проблемами алгебри, і воно також інспіровано дослідженнями за логікою.

Про всі словах Q, к-які при цьому виходять (в тому числі і про самому початковому слові Р), говорять, що вони еквівалентні Р в А. Це дозволяє природним чином зіставити кожному А. Звідси стає зрозумілою важливість дослідження можливості розв'язання алгоритмічної проблеми розпізнавання еквівалентності слів в довільному А. Ця проблема була вперше сформульована А. Туз[1]; вона полягає в тому, що для довільного А.

Основне завдання тут полягає в тому, щоб отримати певні відомості про будову автомата шляхом спостереження його реакції на ті чи інші зовнішні впливи. При цьому виникає велике коло завдань, пов'язаний з класифікацією експериментів і з питаннями можливості розв'язання задач певними видами експериментів, а також з оцінками довжин мінімальних експериментів, достатніх для вирішення тих чи інших завдань. Поняття експерименту з автоматами використовується також в задачах надійності і контролю керуючих систем, зокрема контролю автоматів. Багато хто з перерахованих вище завдань можуть розглядатися як алгоритмічні проблеми. Для кінцевих автоматів більшість з них має позитивне рішення.

В одинадцятому розділі розглядаються комбінаторні у власному розумінні додатки, що групуються навколо так званої Головною теореми Макмагона. Тут розкривається знову-таки полугрупповая природа цієї старої теореми комбінаторики, узагальнюється потім за допомогою зручного для подібних комбінаторних додатків поняття факторизации вільного моноїд. Що стосується десятої глави, то її зміст - разом з частиною змісту гл. Посту), дуже тісно пов'язане з алгоритмічними проблемами і проблематикою умов кінцівки, а останнім часом збагачується змістовними зв'язками з теорією різноманіть.

Було поставлено завдання побудови по можливості більш простих прикладів. В цьому напрямку блискучий успіх був досягнутий ленінградським математиком Г, С. Цейтин і налічує всього лише сім допустимих підстановок, проблема еквівалентності слів також алгоритмічно нерозв'язна. Протягом останніх тридцяти років були виявлені і багато інших алгоритмічні проблеми, які не можуть бути дозволяє алгоритм. Для деяких з них це дуже довго не вдавалося встановити, хоча вони вже давно значилися в списку кандидатів на алгоритмічно нерозв'язні проблеми. Лише в Наприкінці1969 р молодому ленінградському математику Ю. В. Мати-Ясевич вдалося довести, що ця знаменита проблема алгоритмічно нерозв'язна.

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