Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Алгоритмічна теорія інформації це галузь інформатики яка намагається вловити суть складності використовуючи інструменти

Алгоритмічна теорія інформації

Алгоритмічна теорія інформації

Алгоритмічна теорія інформації — це галузь інформатики, яка намагається вловити суть складності, використовуючи інструменти з теоретичної інформатики. Головна ідея — визначити складність (або описову складність, колмогоровську складність, складність Колмогорова — Хайтіна) рядка як довжину найкоротшої програми, яка виводить даний рядок. Рядки, які можуть виводитися короткими програмами, розглядаються як не дуже складні. Ця нотація напрочуд глибока і може бути використана для постановки і доведення неможливості деяких результатів так само, як це робить теорема Геделя про неповноту і проблема зупинки Тюрінга.

Цю галузь наприкінці 1960-х років розробили Андрій Колмогоров, [en] і Грегорі Хайтін. Існують кілька варіантів колмогоровської складності або алгоритмічної інформації. Найширше, переважно завдяки Леоніду Левіну (1974), використовується заснована на саморозмежовуваних програмах.

Принцип мінімальної довжини повідомлення (МДП) статистичного та індуктивного виведення і машинного навчання розробили 1968 року [en] і Д. Болтон (D. M. Boulton). МДП — баєсова ймовірність (вона включає попередні переконання) та інформаційно-теоретична. Вона має бажані властивості статистичної інваріантності (виведення трансформується з репараметризацією, наприклад, так само, як здійснюється перехід від полярних координат до декартових), статистичну узгодженість (навіть для дуже складних проблем МДП збігатиметься до будь-якої нижчої моделі) і ефективність (модель МДП збігатиметься до будь-якої істинної нижчої моделі швидко, наскільки можливо). 1999 року Крістофер Воллес і Девід Дав (David L Dowe) показали формальний зв'язок між МДП і алгоритмічною теорією інформації (або колмогоровською складністю).

Див. також

Посилання

  • Solomonoff's IDSIA page [ 14 червня 2006 у Wayback Machine.]
  • Schmidhuber's generalizations of algorithmic information [ 18 травня 2006 у Wayback Machine.]
  • Li & Vitanyi's textbook [ 14 травня 2006 у Wayback Machine.]
  • Minimum Message Length and Kolmogorov Complexity[недоступне посилання з Май 2018] (by C.S. Wallace[недоступне посилання з Июль 2019] and D.L. Dowe [ 12 лютого 2006 у Wayback Machine.], Computer Journal, Vol. 42, No. 4, 1999).
  • David Dowe [ 12 лютого 2006 у Wayback Machine.]'s Minimum Message Length (MML) [ 9 лютого 2006 у Wayback Machine.] and Occam's razor [ 16 травня 2006 у Wayback Machine.] pages.
  • P. Grunwald, M. A. Pitt and I. J. Myung (ed.), °FF-A2ED-02 °FC49FEBE7C&ttype=2&tid=10478 Advances in Minimum Description Length: Theory and Applications[недоступне посилання з Май 2018], M.I.T. Press, April 2005, .
  • (pdf).
  • Вяткін В. Б. [ 28 липня 2021 у Wayback Machine.] Задача оцінки негентропії відображення системних об'єктів та традиційні підходи до кількісного визначення інформації (матеріали з дисертації) [ 28 липня 2021 у Wayback Machine.]
В іншому мовному розділі є повніша стаття Algorithmic information theory(англ.). Ви можете допомогти, розширивши поточну статтю за допомогою з англійської.
  • Дивитись автоперекладену версію статті з мови «англійська».
  • Перекладач повинен розуміти, що відповідальність за кінцевий вміст статті у Вікіпедії несе саме автор редагувань. Онлайн-переклад надається лише як корисний інструмент перегляду вмісту зрозумілою мовою. Не використовуйте невичитаний і невідкоригований машинний переклад у статтях української Вікіпедії!
  • Машинний переклад Google є корисною відправною точкою для перекладу, але перекладачам необхідно виправляти помилки та підтверджувати точність перекладу, а не просто скопіювати машинний переклад до української Вікіпедії.
  • Не перекладайте текст, який видається недостовірним або неякісним. Якщо можливо, перевірте текст за посиланнями, поданими в іншомовній статті.
  • Докладні рекомендації: див. .

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Algoritmichna teoriya informaciyi ce galuz informatiki yaka namagayetsya vloviti sut skladnosti vikoristovuyuchi instrumenti z teoretichnoyi informatiki Golovna ideya viznachiti skladnist abo opisovu skladnist kolmogorovsku skladnist skladnist Kolmogorova Hajtina ryadka yak dovzhinu najkorotshoyi programi yaka vivodit danij ryadok Ryadki yaki mozhut vivoditisya korotkimi programami rozglyadayutsya yak ne duzhe skladni Cya notaciya naprochud gliboka i mozhe buti vikoristana dlya postanovki i dovedennya nemozhlivosti deyakih rezultativ tak samo yak ce robit teorema Gedelya pro nepovnotu i problema zupinki Tyuringa Cyu galuz naprikinci 1960 h rokiv rozrobili Andrij Kolmogorov en i Gregori Hajtin Isnuyut kilka variantiv kolmogorovskoyi skladnosti abo algoritmichnoyi informaciyi Najshirshe perevazhno zavdyaki Leonidu Levinu 1974 vikoristovuyetsya zasnovana na samorozmezhovuvanih programah Princip minimalnoyi dovzhini povidomlennya MDP statistichnogo ta induktivnogo vivedennya i mashinnogo navchannya rozrobili 1968 roku en i D Bolton D M Boulton MDP bayesova jmovirnist vona vklyuchaye poperedni perekonannya ta informacijno teoretichna Vona maye bazhani vlastivosti statistichnoyi invariantnosti vivedennya transformuyetsya z reparametrizaciyeyu napriklad tak samo yak zdijsnyuyetsya perehid vid polyarnih koordinat do dekartovih statistichnu uzgodzhenist navit dlya duzhe skladnih problem MDP zbigatimetsya do bud yakoyi nizhchoyi modeli i efektivnist model MDP zbigatimetsya do bud yakoyi istinnoyi nizhchoyi modeli shvidko naskilki mozhlivo 1999 roku Kristofer Volles i Devid Dav David L Dowe pokazali formalnij zv yazok mizh MDP i algoritmichnoyu teoriyeyu informaciyi abo kolmogorovskoyu skladnistyu Div takozhKolmogorovska skladnistPosilannyaSolomonoff s IDSIA page 14 chervnya 2006 u Wayback Machine Schmidhuber s generalizations of algorithmic information 18 travnya 2006 u Wayback Machine Li amp Vitanyi s textbook 14 travnya 2006 u Wayback Machine Minimum Message Length and Kolmogorov Complexity nedostupne posilannya z Maj 2018 by C S Wallace nedostupne posilannya z Iyul 2019 and D L Dowe 12 lyutogo 2006 u Wayback Machine Computer Journal Vol 42 No 4 1999 David Dowe 12 lyutogo 2006 u Wayback Machine s Minimum Message Length MML 9 lyutogo 2006 u Wayback Machine and Occam s razor 16 travnya 2006 u Wayback Machine pages P Grunwald M A Pitt and I J Myung ed FF A2ED 02 FC49FEBE7C amp ttype 2 amp tid 10478 Advances in Minimum Description Length Theory and Applications nedostupne posilannya z Maj 2018 M I T Press April 2005 ISBN 0 262 07262 9 pdf Vyatkin V B 28 lipnya 2021 u Wayback Machine Zadacha ocinki negentropiyi vidobrazhennya sistemnih ob yektiv ta tradicijni pidhodi do kilkisnogo viznachennya informaciyi materiali z disertaciyi 28 lipnya 2021 u Wayback Machine V inshomu movnomu rozdili ye povnisha stattya Algorithmic information theory angl Vi mozhete dopomogti rozshirivshi potochnu stattyu za dopomogoyu perekladu z anglijskoyi Divitis avtoperekladenu versiyu statti z movi anglijska Perekladach povinen rozumiti sho vidpovidalnist za kincevij vmist statti u Vikipediyi nese same avtor redaguvan Onlajn pereklad nadayetsya lishe yak korisnij instrument pereglyadu vmistu zrozumiloyu movoyu Ne vikoristovujte nevichitanij i nevidkorigovanij mashinnij pereklad u stattyah ukrayinskoyi Vikipediyi Mashinnij pereklad Google ye korisnoyu vidpravnoyu tochkoyu dlya perekladu ale perekladacham neobhidno vipravlyati pomilki ta pidtverdzhuvati tochnist perekladu a ne prosto skopiyuvati mashinnij pereklad do ukrayinskoyi Vikipediyi Ne perekladajte tekst yakij vidayetsya nedostovirnim abo neyakisnim Yaksho mozhlivo perevirte tekst za posilannyami podanimi v inshomovnij statti Dokladni rekomendaciyi div Vikipediya Pereklad

Дата публікації:
Топ