علیرضا حسین زاده - دانشگاه آزاد اسلامی واحد گناباد گناباد ایران

شاخه ای از نظریه اطلاع که با علوم کامپیوتر مرتبط است پیچیدگی کولموگروف نامیده می شود. این ارتباط اولین بار در سال 1965 توسط آندری کولموگروف ریاضیدان مشهور روسی تحت همین عنوان ارایه گردید. کولموگروف پیچیدگی یک رشته باینری با طول متناهی را بصورت طول کوتاهترین توصیف آن و یا به عبارتی طول کوتاهترین برنامه محاسباتی که این رشته را توصیف می کند، تعریف کرد. یک حقیقت اعجاب انگیز و جالب آن است که او ثابت نمود که اگر این رشته باینری از یک توزیع احتمال با آنترپی شانون h3 حاصل شده باشد آنگاه پیچیدگی آن تقریبا برابر hاست. در مقاله حاضر به اجمال مفهوم پیچیدگی کولموگروف و ارتباط آن با آنتروپی شانون را بررسی می کنیم.

پیچیدگی کولموگروف، پیچیدگی شرطی کولموگروف، آنتروپی شانون، ماشین تیورینگ، توابع بازگشتی جزیی