Payamvdn/NorthPersian_fa_wiki huggingface dataset:
نظریه بازی های ترکیبیاتی شاخه ای از ریاضیات و علوم نظری رایانه است که به طور معمول به مطالعهٔ بازی های ترتیبی و دنباله دار با اطلاعات کامل می پردازد و مطالعهٔ آن بیشتر شامل بازی های دونفره ای است که در آن بازیکنان به نوبت، حرکاتی در راستای رسیدن به موقعیت برد انجام می دهند. همچنین این بازی ها در زمان متناهی پایان می یابند و برنده براساس قوانین بازی مشخص می شود. این نظریه به طور سنتی، به بررسی بازی های شانسی یا بازی های اطلاعات ناقص نمی پردازد و موضوع عمدهٔ آن بازی هایی است که مجموعهٔ حرکات در هر مرحله از بازی مشخص است و بازیکن ها نیز از آن مطلع اند. هدف از بررسی بازی ها یافتن برندهٔ بازی از یک حالت اولیه مشخص و همچنین نحوهٔ پیروزی برنده است -یعنی برنده با چه حرکاتی می تواند پیروز شود- که اصطلاحاً به آن استراتژی برد می گویند. امروزه با استفاده از تکنیک های پیشرفتهٔ ریاضی، نوع و تعداد بازی هایی که می توانند به صورت ریاضی تحلیل و بررسی شوند، در حال گسترش است. یه طوری که در بازی های ترکیبیاتی تمامی قوانین و حرکات مجاز و حتی تحلیل بازی نوشته می شوند. شطرنج، چکرز و گو از بازی های ترکیبیاتی غیر بدیهی به شمار می روند
، اما بازی هایی مانند ایکس او جزء بازی های بدیهی به حساب می آیند و در هر دو نوع این بازی ها، حرکات را می توان به کمک درخت بازی ها نمایش داد. بازی های ترکیبیاتی شامل بازی های یک نفره با جداول ترکیبیاتی مانند سودوکو یا بازی های بدون بازیکن اتوماتیک مانند بازی زندگی کانوی است. همچنین نظریه بازی ها به طور کلی شامل بازی های شانسی، بازی هایی که نیاز به دانش خاص ندارند و بازی هایی است که بازیکن ها هم زمان می توانند بازی کنند و هدف آن شبیه سازی تصمیمات واقعی زندگی است. نظریه بازی های ترکیبیاتی با نظریه بازی های سنتی یا اقتصادی، که در ابتدا برای مطالعهٔ بازی های ترکیبیاتی سادهٔ دارای شانس توسعه پیدا کردند، متفاوت است. در نظریه بازی های ترکیبیاتی تأکید کمتری بر پالایش عملی الگوریتم های جستجو مانند هرس آلفا بتا - که در اکثر کتاب های هوش مصنوعی به آن اشاره شده است - وجود دارد و بیشتر بر روی نتایج نظری توصیفی، مانند محاسبهٔ پیچیدگی بازی ها یا یافتن راه حل های بهینه تأکید می شود. همچنین بخش مهمی از نظریه بازی های ترکیبیاتی دربارهٔ بازی های حل شده است. به طور مثال در بازی ایکس او می توان ثابت کرد که اگر هر دو بازیکن به طور
بهینه بازی کنند، مساوی می شوند. معمولاً هرچه بازی ها ساختار ترکیبیاتی بیشتری پیدا کنند، یافتن نتایج مشابه برای آن ها سخت تر می شود. به طور مثال در سال ۲۰۰۷ اعلام شد که بازی چکرز حل شدهٔ ضعیف است. بازی های دنیای واقعی عموماً پیچیده تر از آن هستند که بتوانیم به راحتی تحلیلشان کنیم، اگرچه به تازگی تحلیل و آنالیز آخر بازی گو موفقیت آمیز بوده است. با استفاده از نظریه بازی های ترکیبیاتی، بازیکن ها در هر مرحله می توانند دنباله ای از تصمیمات بهینه را برای برد پیدا کنند ولی در برخی بازی ها این تصمیمات به راحتی یافت نمی شوند. انواع. بازی های ترکیبیاتی به دو دستهٔ بازی های منصفانه و بازی های پارتیزانی تقسیم می شوند. بازی های منصفانه به بازی هایی گفته می شود که حرکت های قابل قبول در آن وضعیت، تنها به وضعیت کنونی بستگی داشته باشد و نه براساس نوبت بازیکنان. در بازی های منصفانه، مستقل از نوبت بازیکنان و تنها براساس وضعیت موجود می توان استراتژی برد را تعیین کرد. به بیانی دیگر، اگر وضعیت بازی را ثابت نگه داریم و نوبت بازیکنان را عوض کنیم، تحلیل بازی تغییری نمی کند. به طور مثال در بازی نیم، هر مجموعه ای از شی ها که توسط یک باز
یکن خارج شوند، توسط بازیکن دیگر نیز می توانند خارج شوند. اما به طور مثال بازی سلطه گر منصفانه نیست زیرا یکی از بازیکن ها، دومینوها را به صورت افقی و بازیکن دیگر آن ها را عمودی قرار می دهد و در نتیجه شرایط برای دو بازیکن یکسان نیست. به همین ترتیب بازی چکرز نیز منصفانه نیست زیرا بازیکن ها رنگ های مختلف خود را دارند. بازی نیم نیم یک بازی دونفرهٔ راهبردی (استراتژیک) ریاضی است که با کپه هایی از سنگ ریزه انجام می شود. در هر نوبت هر بازیکن از یک کپه حداقل یک سنگ ریزه برمی دارد (بازیکن حتی می تواند تمام کپه را نیز بردارد). نیم اغلب به این صورت بازی می شود که در هر نوبت بازیکن حداقل یک شیء را برمی دارد و ممکن است هر تعدادی را به شرط اینکه از یک پشته باشد بردارد. در نهایت بازیکنی که نتواند چیزی را بردارد بازنده است. نیم به صورت ریاضی برای تعداد متناهی از کپه ها و سنگ ریزه ها حل شده است و می توان مشخص نمود که کدام بازیکن برنده خواهد شد. با جمع دودویی (باینری) اندازه کپه ها می توان این مسئله را حل نمود. به این ترتیب که معادل دودویی اندازه کپه ها را بدون درنظرگرفتن رقم نقلی با هم جمع کرد. این عمل همان یای انحصاری (XOR) در
مدارهای منطقی است که در تئوری بازی های ترکیبی آن را جمع نیمی می نامند. جمع نیمی را می توان به صورت ذهنی که انگشتان دست را به ترتیب توان های ۲ در نظر می گیرند و اگر عددی دارای آن توان ۲ بود آن را بالا می برند و اگر دارای آن توان نبود آن را پایین می آورند و در جمع با سایر اعداد اگر آن عدد دارای توانی از ۲ بود وضعیت مربوط به آن انگشت را برعکس می کنند؛ یعنی اگر بالا بود آن را پایین می آورند و اگر پایین بود آن را بالا می برند. در بازی معمولی استراتژی برد، صفر کردن جمع نیمی اندازه کپه هاست که این امر تا زمانی که جمع نیمی آن ها صفر نشده است ممکن است. اگر جمع نیمی صفر شود بازیکنی که نوبت آن است خواهد باخت. (در صورتی که بازیکن دیگر اشتباه نکند). همان طور که مشخص است این بازی منصفانه می باشد زیرا استراتژی برد تنها وابسته به وضعیت کنونی است و به نوبت بازیکنان بستگی ندارد. بازی ایکس او ایکس او یک بازی دو نفره است. نام این بازی به دلیل علامت های X و O است که در طول بازی استفاده می شود. برای آغاز این بازی در یک صفحه، جدولی با ۳ ردیف و ۳ ستون رسم می شود و هر یک از طرفین یکی از علامت های X یا O را انتخاب می کنند و تا انتهای
بازی برای پر کردن خانه های جدول از آن استفاده می کنند. برای شروع بازی یکی از طرفین به قید قرعه علامت X یا O را که قبلاً انتخاب کرده در یکی از خانه های جدول ۹ خانه ای قرار می دهد. سپس نفر دوم علامت مربوط به خود را در خانه های دیگر که هنوز پر نشده اند قرار می دهد و این روند به صورت متوالی و گردشی تکرار می شود. بازی زمانی به پایان می رسد که یکی از بازیکنان بتواند علامتی را که در ابتدای بازی انتخاب کرده در یکی از ردیف های افقی، عمودی یا قطری قرار دهد و در این صورت آن بازیکن برنده است. در طول بازی هر یک از طرفین با قرار دادن علامت خود در مقابل علامت های حریف نباید اجازه دهند که حریف یک خط عمودی، افقی یا قطری را با علامت خود پر کند. در این بازی نفر اول می تواند به گونه ای بازی کند که هیچ وقت نبازد. به این صورت که ابتدا خانهٔ وسط را علامت می گذارد. حال دو حالت ممکن است پیش آید: سپس هر فرد به گونه ای بازی می کند که در اولویت اول اگر امکان برد در همان مرحله داشت، ببردو در اولویت دوم اگر حریف امکان برد داشت، از آن جلوگیری کند و اگر هیچ یک از این شرایط نبود، همان روش بالا را تکرار کند. می توان نشان داد با این استراتژی،
نفر اول هیچ گاه نمی بازد. پس این بازی یک بازی پارتیزانی است که در آن نوبت و ترتیب بازی بازیکنان در شکست یا برد آن ها نقش دارد. تاریخچه. نظریه بازی های ترکیبیاتی در رابطه با تئوری بازی های منصفانه که در آن ها هر دو بازیکن قادر به انجام اعمال یکسان هستند، به وجود آمد. یکی از این بازی های مهم، بازی نیم است که به صورت کامل حل شده است. تاکنون تحلیل های زیادی از بازی های گوناگون به چاپ رسیده اند که نقطهٔ آغاز آن ها تحلیل بازی نیم توسط چارلز ال بوتون در سال ۱۹۰۲ بوده است. نیم یک بازی دونفرهٔ منصفانه است و هر کس که در انتها قادر به انجام حرکتی نباشد، بازنده است. در سال ۱۹۳۰، قضیه اسپراگ-گراندی نشان داد که تمامی بازی های منصفانه با کپه ها در بازی نیم معادلند. پس از آن جان کانوی نظریه بازی های پارتیزانی را که پیشرفت شگرفی بود، ارائه و توسعه داد. بررسی اجمالی. یک بازی در ساده ترین حالت خود لیستی از حرکت های ممکن است که دو بازیکن که آن ها را چپ و راست می نامند، می توانند انجام دهند. موقعیت بازی از تمام حرکاتی که حتی از یک بازی دیگر می توان انجام داد، نتیجه می شود. این ایده که بازی ها از جهت حرکت های ممکن آن ها منجر به ب
ازی دیگری می شوند، تعریف بازگشتی ریاضی بازی است که در نظریه بازی های ترکیبیاتی، استاندارد است. در این تعریف هر بازی نمادی به شکل {L|R} دارد که در آن formula_1 و formula_2 مجموعه ای از موقعیت های بازی هستند که به ترتیب توسط بازیکن چپ و راست می توانند ایجاد شوند و نمادهای یکسانی دارند. از این نماد برای بررسی روند انجام مرحله به مرحلهٔ بازی ها و تحلیل و بدست آوردن استراتژی برد استفاده می شود. کاربردها. نظریه بازی های ترکیبیاتی روش های جدیدی برای آنالیز کردن درخت بازی ها ارائه کرده است. مانند استفاده از اعداد سوررئال که زیر کلاسی از همهٔ بازی های دو نفره با اطلاعات کامل است. بازی هایی که در نظریه بازی های ترکیبیاتی مورد بررسی قرار می گیرند، در هوش مصنوعی و به خصوص در برنامه ریزی های خودکار و زمانبندی شده نیز کاربرد دارند. همچنین این شاخه ارتباط هایی با دیگر شاخه های ریاضیات مانند نظریه کدگذاری، نظریه گراف، نظریه اعداد، منطق ریاضی، نظریه ماترویدها و نظریه شبکه دارد. نیمبرها. برای هر عدد ترتیبی می توان یک بازی منصفانه تعریف کرد که تعمیمی از بازی نیم است و در آن در هر حرکت هر دو بازیکن می توانند یک عدد را با یک عدد
ترتیبی کوچک تر جایگزین کنند. بازی هایی که به این شکل تعریف می شوند، با عنوان نیمبرها شناخته می شوند. قضیه اسپراگ-گراندی نشان می دهد که هر بازی منصفانه معادل است با یک نیمبر. همچنین کوچک ترین نیمبرها همان ساده ترین و کوچک ترین اعداد روی ترتیب معمول اعداد ترتیبی یعنی ۰ و * هستند. مطالعهٔ بیشتر. هرس آلفا بتا بازی ویتوف سامانه چندعامله پیچیدگی بازی شکل گسترده بازی درخت بازی
رایانش شناختی یا CC تکنولوژی ای است که قصد دارد با استفاده از علوم شناختی و علوم رایانه رفتار و تفکرات انسان را در یک مدل کامپیوتری شبیه سازی کند. رایانش شناختی متشکل از سیستم های خودآموزی است که با داده کاوی، بازشناخت الگوها و پردازش زبان های طبیعی، سعی بر آن دارند که مجموعهٔ رفتار انسان را تقلید کنند. هدف رایانش شناختی تولید سیستم های کامپیوتری است که بدون کمک انسان قدرت تصیم گیری داشته باشند. تاریخچه. اساس ایجاد رایانش شناختی به قرن ۱۹ام میلادی برمی گردد. به طور کلی هوش مصنوعی توسط جرج بول با بیان نظریاتی از منطق در کتاب «قانون فکر» مطرح شد. همچنین تحقیقات چارلز ببیج برای ساخت موتور تحلیلی در این مسیر نقش به سزایی داشت. در ماه مه سال ۱۹۹۷ شرکت آی بی ام با ارائهٔ ربات شطرنج باز خود، دیدگاه جهان کامپیوتر را دربارهٔ ماشین های با هوش انسانی را تغییر داد. این ربات دیپ بلو نام دارد و از تکنولوژی رایانش شناختی بهره می برد. در آن سال در برابر گری کاسپارف، قهرمان شطرنج جهان، از بین ۶ مسابقهٔ انجام شده برندهٔ ۴ مسابقه شد. پس از آن در سال ۲۰۰۵ ربات دانشگاه استنفورد با نام استنلی موفق به بردن جایزهٔ مسابقهٔ ماشین سوار
ی DARPA شد. این ماشین با بهره گیری از سنسورهای متعدد و دستگاه مسیر یاب و به بهره گیری از دانش هوش مصنوعی و یادگیری ماشین توانسته بود رفتارهای یک راننده را بدون نیاز به کمک انسان شبیه سازی کند. ویژگی ها و کارکرد سیستم های رایانش شناختی. با تغییر در اطلاعات و تغییر در نیازها ماشین ها باید این اطلاعات جدید را دریافت کرده و آن را یاد بگیرند. این سیستم ها باید به گونه ای مهندسی شوند تا بتوانند به طور پویا اطلاعات را دنبال کرده و فرا بگیرند و در این راستا نیاز است که تعامل خوبی با محیط اطراف برقرار کنند. همچنین به دلیل ارتباط مستقیم با جهان اطراف نیاز است که وظائف مدنظر را در زمان های واقعی و مشخص شده انجام دهند. روند کار به اینگونه است که هربار اطلاعات جدیدی به سیستم تزریق می شود، با یادگیری آن سیستم توسعه می یابد و هربار با وجود اطلاعات بیشتر، بهتر می تواند در رابطه با مشکل موجود تصمیم گیری کند. در واقع سعی می شود روند یادگیری که در مغز انسان شکل می گیرد، به همان گونه در ماشین ها پیاده سازی شود. کاربردهایی از رایانش شناختی. از جمله کاربرهای مهم این تکنولوژی، کاربرد آن در علم پزشکی است. برای بیماری که وارد اورژانس
می شود، یک سیستم رایانش شناختی می تواند با بررسی قسمت های مختلف بدن و با در نظر گرفتن سابقهٔ استفادهٔ داروهای مختلف و سابقهٔ سفر و موارد گوناگون دیگر، به دقت پیش بینی کند که بیمار مبتلا به آنفلوآنزا یا بیماری های ویروسی یا هر بیماری دیگر است. با توجه به این کاربرد، می توان پی برد که تکنولوژی های شناختی می توانند جهان اطراف ما را بشناسند و نشانه های آن را دریابند و متوجه شوند چه اتفاقاتی رخ می دهد. هدف سیستم های شناختی، کمک کردن به انسان، بدون کمک انسان است. در این مورد، سیستم شناختی هم به پزشک و پرستار و هم به بیمار کمک شایان توجهی می کند. به عنوان کاربردی دیگر، در مراکز خدمات تلفنی ربات هایی که از رایانش شناختی بهره می برند می توانند به نمایندگان فروش محصولات کمک کنند تا هربار محصولات پیشنهادی خود را در راستای نیاز مشتریان بهبود دهند. همچنین، مجموعهٔ هتل هیلتون در همکاری با IBM رباتی به نام Connie تولید کرده اند که به زبان انسان قادر به پاسخگویی به درخواست های مشتریان دربارهٔ هتل، جاذبه های گردشگری، رستوران های اطراف و دیگر پرسش های مشتریان است. سیستم هایی مانند Google و Siri بر پایهٔ یادگیری ماشین کار می ک
نند. گرچه در حال حاضر از پیش برنامه نویسی شده اند و قادر به انجام کارهای محدود و مشخصی هستند، اما به زودی در آینده با گسترش این سیستم ها در حوزهٔ رایانش شناختی شاهد آن خواهیم بود که با جمع آوری داده های مختلف خواهند توانست قسمت های مختلفی از زندگی انسان را تحث تأثیر قرار دهند.
در ریاضیات، کاردینالیتی یا عدد اصلی یک مجموعه، یک اندازه گیری برای «تعداد عناصر مجموعه» است. برای مثال مجموعه A = {۲، ۴، ۶} شامل ۳ عنصر بوده و در نتیجه دارای کاردینالیتیِ ۳ است. دو روش در مورد کاردینالیتی وجود دارد – یکی که مجموعه ها را مستقیماً با استفاده از توابع دوسویه و توابع یک به یک مقایسه می کند و دیگری که از اعداد اصلی بهره می برد. کاردینالیتی یک مجموعه همچنین اندازه آن خوانده می شود، جائیکه با دیگر مفاهیمِ اندازه خلط نشود. کاردینالیتی یک مجموعه "A" را معمولاً با |"A"|، با یک نوار عمودی در هر طرف نشان می دهند؛ این همان نماد قدر مطلق است و معنای آن بستگی به زمینه بحث دارد. معادلاَ، کاردینالیتی یک مجموعه "A" ممکن است با n("A"), card(A) یا A# نشان داده شود. اعداد اصلی. رابطهٔ "دارای عدد اصلی یکسان بودن" را هم-شماری (یه انگلیسی: ) می گویند و آن یک رابطه هم ارزی روی رده تمام مجموعه هاست. بنابر این، رده هم ارزی از یک مجموعه "A "تحت این رابطه متشکل از تمام آن مجموعه هاییست که دارای کاردینالیتی یکسانی با "A "هستند. دو راه برای تعریف «کاردینالیتی یک مجموعه» وجود دارد: با فرض اصل انتخاب، کاردینالیتی مجموعه های
نامتناهی به صورت زیر مشخص می شوند: برای هر عدد ترتیبی formula_2، formula_3 کوچکترین عدد اصلی بزرگتر از formula_4 است. مجموعه های متناهی، شمارا و ناشمارا. اگر اصل موضوع انتخاب برقرار باشد، قاعده تثلیث برای کاردینالیتی برقرار خواهد بود. بنابراین ما می توانیم تعاریف زیر را ارائه دهیم: نکته. گاهی برای نمایش عدد اصلی یا کاردینالیتی مجموعهA از نمادهایی دیگری نیز استفاده می کنند. این نمادها در ادامه معرفی شده اند. بدیهی است به کار بردن هر یک از آن ها معادل با عدد اصلی مجموعهA است.
تیرکِش دروازه قلعه () یک نوع مزغَل محوطه بالای دروازه و برج دفاعی قلعه است. تیرکِش ها دارای دیواره کنگره ای و دهانه باز در کف بودند که برای فروریختن روغن داغ، سُرب و قیر مذاب بر سر مهاجمین در هنگام محاصره و هجوم به برج و باروی قلعه کارایی بسیار مفیدی داشت. اغلب اوقات این شیوه و تاکتیک تلفات و خسارات سنگینی بر جای می گذاشت. تیرکش ها در اصل جزو استحکامات دیوار تدافعی محسوب می شوند.
نرده دفاعی () یک نوع بسیار قدیمی و متداول از استحکامات می باشد که شامل نرده محکم از تیرپایه یا تخته تنه درختان است. نرده دفاعی اغلب به دور قلعه های اولیه و بدوی و گاهی دهکده ها و اقامت گاه های کوچک کشیده می شد. این شیوه از استحکامات در میان یونانیان و رومیان باستان کاربرد بسیار داشت که بیشتر اوقات در جهت حفاظت از اردوگاه های نظامی ایجاد می گردید. مورخ تاریخی تیتوس لیویوس، اشاره می کند که این شیوه از یونان باستان به روم منتقل گردید و پس از آن در طول جنگ دوم مقدونیه به دفعات مورد استفاده قرار گرفت
به روشی که برای اعمال محاسبات ساده، اعداد در ارزش های مکانی مختلف قرار داده می شوند و محاسبات از قوانین معینی پیروی می کنند، الگوریسم یا خوارزمیک گری گفته می شود. سیستم ارزش های مکانی جایگزین عمدهٔ سایر سیستم های محاسباتی است. سیستم های محاسباتی قدیمی تر (مانند عددنویسی رومی) معمولاً از نمادهای مختلف و متعدد برای نمایش مقدارهای مختلف ریاضیاتی استفاده می کردند و برخی از این سیستم ها برای محاسبات نیازمند ابزاری مانند چرتکه بودند. تعریف. الگوریسم به سیستم ده دهی هندی – عربی نگارش و کار کردن با اعداد و ارقام گفته می شود که در آن نشانه ها ( یعنی ده رقم از 0 تا 9) برای توضیح دادن مقادیر با استفاده از یک سیستم مقادیر جایگزین بکار می روند. در این سیستم هر نشانه ای ، ارزشی ده برابر بیشتر از نشانه سمت راستش دارد. ریشه شناسی. کلمه الگوریسم از نام دانشمند ایرانی خوارزمی (الخوارزمی) به وجود آمده است. لغت «خوارزمی» به معنی «اهل خوارزم» است که نام شهری در نقشه قدیم ایران (ایران بزرگ) بوده و در نقشهٔ کنونی در ازبکستان واقع است. خوارزمی ریاضیدان، منجم، جغرافی دان و محقق بیت الحکمه (واقع در شهر بغداد) قرن سوم هجری است. او در ق
رن نهم میلادی مقاله ای به زبان عربی نوشت که در قرن دوازدهم میلادی با نام «Algoritmi de numero Indorum» به زبان لاتین ترجمه شد. این عنوان به معنای «رساله خوارزمی در مورد اعداد هندی» است که نام «الخوارزمی» در زبان لاتین توسط مترجم به «Algoritmi» (الگوریتمی) تغییر یافته است. در اواخر قرون وسطی، خوارزمی مخصوصاً به واسطه کتاب دیگرش، الجبر والمقابله، پرخواننده ترین ریاضیدان در اروپا محسوب می شد. در همین دوره کلمه «الگوریسموس» که از نام خوارزمی مشتق شده به معنای «سیستم عددی دهدهی» رواج یافت که امروزه هم کلمه «الگوریسم» با همین معنا در زبان انگلیسی وجود دارد. کلمه الگوریتم نیز از کلمه الگوریسم مشتق شده و به معنای مجموعه ای از قوانین مشخص کننده یک روش محاسباتی است. گاهی اوقات الگوریسم نیز در این معنی به خصوص در متون قدیمی تر به کار رفته است. تبدیل نام الخوارزمی به الگوریسم و سپس الگوریتم احتمالاً تحت تأثیر واژه یونانی arithmos (به معنای عدد) و arithmetic (به معنای محاسباتی) بوده است. برخی منابع هم کلمه لگاریتم را هم در تبدیل الگوریسم و الگوریتم بی تأثیر ندانسته اند. تاریخچه. با توسعهٔ محاسبات اعداد صحیح در سیستم ده ده
ی در هند، خوارزمی و سایر ریاضیدانان قرون وسطی در اسلام (ایرانی و عربی), روش های محاسباتی دهدهی را مستند کرده و پیشرفت دادند. (می توانید به بخش «همچنان نگاه کنید» رجوع کنید). این تلاش ها به ایجاد مفهوم کسر اعشاری و ممیز اعشاری انجامید. این سیستم در اروپا توسط لئوناردو پیزا که امروزه به عنوان فیبوناچی شناخته می شود، رواج پیدا کرد.
در علم رایانه الگوریتم جریان داده ها الگوریتمی ست برای پردازش جریان داده ها که به صورت توالی از آیتم ها به عنوان ورودی هستند و از یک یا تعداد محدودی گذرگاه می توانند مورد بررسی قرار بگیرند. در واقع این الگوریتم دنباله ای از داده را به عنوان ورودی دریافت کرده و یک سری تابع روی آن ها اعمال می کند. این الگوریتم حافظه مورد نیاز (کمتر از اندازه واقعی خود ورودی) و زمان پردازش هر آیتم را هم محدود می کند. این محدودیت ها به این معناست که این الگوریتم جواب تقریبی بر اساس یک خلاصه یا «طرحی» از جریان داده ها در حافظه تولید می کند. تاریخچه. اگرچه مطالعه الگوریتم جریان توسط مونرو و پاترسون دراوایل ۱۹۸۰ آغاز شد اما توسط و نایجل مارتین در ۱۹۸۲–۱۹۸۳ باعث شد موضوعات مرتبط به الگوریتم های جریان برای اولین بار به رسمیت شناخته شود و در یک مقاله در سال ۱۹۹۶ توسط نوگا آلون، یوسی ماتیاس، و ماریو محبوب شد. نویسندگان این مقاله بعداً جایزه گودل در سال ۲۰۰۵ را «برای سهم بنیادی شان نسبت به الگوریتم های جریانی» کسب کردند. از آن زمان کار زیادی حول الگوریتم های جریان داده انجام شد که طیف متنوعی از زمینه های علوم کامپیوتر از قبیل تئوری، پایگ
اه داده، شبکه و پردازش زبان طبیعی را گسترش داد. الگوریتم های نیمه جریانی در سال ۲۰۰۵ به عنوان یک فرمت از الگوریتم های جریانی ارائه شد که برای تعداد ثابت یا لگاریتمی از گذرگاه ها روی مجموعهٔ داده ها امکان پذیر است. مدل ها. در مدل جریان داده ها، برخی یا همه داده های ورودی که قابل عملیات هستند، برای دسترسی تصادفی از روی دیسک یا حافظه در دسترس نیستند، اما به عنوان یک جریان داده پیوسته سریع تر می رسند. جریان را می توان به صورت دنباله ای از نقاط تعریف کرد که می تواند تنها یک بار یا تعداد کمی در دسترس قرار بگیرد. بسیاری از ادبیات جریانی با آمار کامپیوتری روی داده های توزیعی که برای ذخیره کردن بسیار بزرگ هستند، مرتبط است. برای این دسته از مشکلات یک بردار a = (formula_1 , … , formula_2) تعریف می کنیم که به صفر مقداردهی اولیه می کنیم که در یک جریان داده آمادهٔ به روزرسانی می باشد. هدف از این الگوریتم محاسبه توابعی از a با استفاده از فضای بسیار کمتری نسبت به فضایی که دقیقاً اشغال می کند، است. دو مدل رایج برای به روزرسانی هر جریان وجود دارد، به نام "مدل درخواست نقدی" (به انگلیسی:cash register) و "مدل گردان (به انگلیسی tu
rnstile). در مدل درخواست نقدی، هر به روزرسانی به فرم (i,c) می باشد به طوری که formula_1 توسط c عدد صحیح مثبت افزایش می یابد. در مدل گردان هیچ کدام ازformula_4ها منفی نیستند. چندین مقاله نیز مدل «پنجره کشویی» را مطرح گرده اند. در این مدل، تابع مورد نظربرای محاسبه بیش از یک پنجره با اندازه ثابت در جریان داده دارد. هنگامی که جریان داده پیشرفت کند، یک آیتم از انتهای این جریان حذف شده و یک آیتم جدید جای آن را می گیرد. علاوه بر مشکلاتی که در فرکانس بالا ایجادمیشود، مشکلات دیگر نیز بررسی شده است. تعدادی از مسائل گراف، با ماتریس همسایگی یا فهرست همسایگی که به صورت جریانی تعریف شده باشند، حل شده است. تعدادی از مشکلات این حوزه نیز به order(حجم و ترتیب و تعداد آیتم ها) یک جریان بستگی دارد. (مثلاً توابع نامتقارن) به طور مثال شمارش تعداد در یک توالی داده مثلاً یک آرایه و یافتن طولانی ترین زیررشته صعودی . در واقع الگوریتم های مطرح برای رسیدن به این خواسته ها به طول رشته داده بستگی دارد و هرچه تعداد آیتم های این توالی داده ها بیشتر باشد، زمان اجرای الگوریتم و رسیدن به مطلوب سؤال یشتر می شود، در واقع مفهوم order به معنی میزا
ن زمان اجرای الگوریتم و تعداد عملیات های انجام شده در یک الگوریتم و پیچیدگی الگوریتم می باشد. با توجه به حجم داده ها، مدل جریان داده ها در پیدا کردن نابه جایی ها یک محیط طبیعی برای طراحی کارآمد است. ما مجموعه ای از الگوریتم های جریانی کارآمد، برای تخمین تعداد نابه جایی ها در یک جایگشت به دست می آوریم. بهترین order برای این الگوریتم ها الگوریتم قطعی (deterministic) است که درformula_5 انجام می شود (عبارت formula_5 به این مفهوم است که وقتی طول رشته داده ما n باشد زمان اجرای الگوریتم و همان order الگوریتم یک ضریبی از formula_7 می باشد). تحلیل و ارزیابی. عملکرد یک الگوریتم در جریانی از داده ها توسط سه عامل اساسی اندازه گیری می شود: این الگوریتم ها شباهت های بسیاری با الگوریتم برخط دارند، زیرا هر دو نیاز به تصمیم گیری و پردازش و اجرای عملیات دارند قبل از اینکه تمام داده ها در دسترس باشند، یعنی در ابتدای شروع کار الگوریتم، ورودی این الگوریتم ها به طور کامل در اختیار الگوریتم نیست و به صورت ترتیبی و مرحله مرحله انجام می شود اما این شباهت به معنی یکسانی نیست. الگوریتم های جریان داده ها تنها حافظهٔ در دسترس را محدود کر
ده اند اما آن ها ممکن است انجام یک عمل را به تأخیر بیندازند تا یک گروه از نقاط برسند، در حالی که الگوریتم های برخط به محض اینکه نقطه ای برسد، عملیات را انجام می دهند. در واقع الگوریتم های جریانی حافظهٔ در دسترس شان را می توانند تغییر دهند و حافظه شان از formula_8 است اما حافظهٔ در دسترس الگوریتم های برخط ثابت و از formula_9 می باشد. در نتیجه این تفاوت ها داریم که الگوریتم های جریانی به طور نهایی می توانند اجرای درست عملیات خود را آزمایش کنند اما آزمایش کردن برای الگوریتم برخط هرمرحله انجام می شود اگر الگوریتمی تقریبی باشد، دقت جواب فاکتور کلیدی می شود. دقت پاسخ اغلب به صورت (formula_10 , formula_11) بیان می شود که در آن اشتباه و خطای پاسخ از formula_11 با احتمال کمتر است. کاربردها. الگوریتم جریان داده ها چندین کابرد در حوزه شبکه رایانه ای از قبیل کنترل پیوندهای شبکه برای ، شمارش تعداد جریان های متمایز، برآورد توزیع اندازه جریان و غیره دارد. هم چنین تعدادی کابرد در زمینهٔ پایگاه داده دارد مانند تخمین اندازه . به عنوان مثال در زمینه ارتباطات :۳ میلیارد تماس های تلفنی در آمریکا هر روز ۳۰ میلیارد ایمیل های روزانه
، ۱ میلیارد اس ام اس وجود دارد که ذخیره تمام این داده ها در حافظه با دسترسی تصادفی برای پردازش غیرممکن است؛ که راه حل این مسئله پردازش داده ها به عنوان یک جریان و بردازش روی این داده ها می باشد. چندمسئله حل شده با الگوریتم جریان داده ها. ممان فرکانسی. k مین ممان فرکانسی از مجموعه فرکانس ها به اسم a ایگونه تعریف می شود: formula_13 اولین ممان formula_14 به سادگی مجموع فرکانس هاست (به عنوان مثال، تعداد کل). رخدادformula_15 برای محاسبه خواص آماری از داده ها، مانند شاخص جینی مورد استفاده است. formula_16 به عنوان فرکانس عضو پرفرکانس ترین تعریف می شود. مقاله بدوی از آلون، ماتیاس و Szegedy به مشکل برآورد لحظات فرکانس پرداخته است. محاسبه ممان فرکانسی. یک روش مستقیم برای پیدا کردن ممان های فرکانس نیاز به حفظ یک ثبات formula_17 برای همه عناصر متمایزformula_18 که عضو (۱٬۲٬۳٬۴، …، N) می باشد که به حداقل حافظه با حدودformula_19 نیاز دارند. اما ما باید محدودیت فضا مواجه هستیم و نیاز به یک الگوریتم است که در حافظه بسیار پایین تر محاسبه کند. به این می توان با استفاده از تقریب به جای ارزش های دقیق دست یافت. یک الگوریتمی که محا
سبه می کند یک تقریب (formula_10 , formula_11) از formula_22 که formula_11 به عنوان پارامتر تقریب و formula_10 به عنوان پارامتر اطمینان است. . محاسبه formula_25 عناصر متمایز در جریان داده. الگوریتم FM-Sketch. فلاجولت وهمکاران در روش احتمالاتی از شمارش که از یک مقاله نوشتهٔ رابرت موریس الهام گرفته شده بود، شمارش تعداد زیادی از حوادث در ثبات های کوچک را معرفی کرد. موریس در مقاله خود می گوید که اگر نیاز به دقت، کاهش یافته است، یک شمارنده formula_26 می تواند با یک شمارنده formula_7 جایگزین شود که در formula_28 بیت ذخیره می شود. فلاجولت وهمکاران این روش را با استفاده از تابع هش formula_29 که عناصر را به صورت یکنواخت در فضای هش توزیع می کند (یک رشته عدد باینری به طول formula_30)، بهبود بخشیدند. formula_31 فرض کنید bit(y,k) نشان دهنده بیت k ام در عدد باینری y است : formula_32 فرض کنید formula_33 نشان دهنده کم ارزش ترین بیت ۱ در نمایش باینری عدد formula_34 با یک قرارداد و تعریف مناسب از formula_35 می باشد. formula_36 فرض کنید A یک دنباله ای از داده ها به طول M است که کاردینالیتی مورد نیاز را مشخص می کند. فرض کنید BITM