payamvha/North_RAG huggingface dataset:
وراثت چامسکی یا سلسله‌مراتب چامسکی یا سلسله‌مراتب چامسکی-شوتزنبرگر در زمینه‌های علوم کامپیوتر و زبان‌شناسی، به خصوص در زمینهٔ زبان‌های صوری، یک سلسله مراتب نگهدارندهٔ کلاس‌های دستور زبان صوری است. سلسله‌مراتب گرامرها توسط نوآم چامسکی در سال ۱۹۵۶ توصیف شده است. در نام گذاری این سلسله مراتب، از اسم مارسل-پل شوتزنبرگر نیز به پاس نقش اساسی وی در توسعهٔ نظریهٔ زبان‌های رسمی (زبان صوری)، استفاده شده است. سلسله‌مراتب چامسکی در اصل امکان درک و بکارگیری مدل علوم کامپیوتر را فراهم می‌کند. این مدل به برنامه‌نویس‌ها
را فراهم می‌کند. این مدل به برنامه‌نویس‌ها اجازه می‌دهد که اهداف زبان‌شناسی مفهوم‌دار را به صورت سیستماتیک به انجام برسانند. دستور زبان‌های رسمی (صوری). دستور زبانی رسمی از این نوع، از یک مجموعه‌ای متناهی از قواعد تولید تشکیل شده است ("سمت چپ" formula_1 "سمت راست") که هر سمت آن، خود شامل رشته‌ای از نمادهای زیر می‌باشد: گرامر رسمی یک زبان رسمی را تعریف (یا تولید) می‌کند، که مجموعه‌ای (معمولاً متناهی) از رشته‌هایی با طول متناهی از نمادها هستند، که ممکن است با اعمال قواعد تولید به رشته‌ای دیگر از نمادها که از
اعمال قواعد تولید به رشته‌ای دیگر از نمادها که از ابتدا فقط حاوی نماد آغازین بوده‌اند، ساخته شوند. یک قاعده می‌تواند با جایگزین کردن یک رخداد از نمادها در سمت چپ قاعده با رخدادی که در سمت راست ظاهر می‌شود، به رشته‌ای از نمادها اعمال شود. رشته‌ای از کاربردهای قاعده را «اشتقاق» می‌خوانند. چنین گرامری زبان رسمی را تعریف می‌کند: همهٔ واژه‌هایی که تنها از نمادهای پایانه‌ای تشکیل شده باشند که با اشتقاقی از نماد آغازین، قابل دسترسی باشند. ناپایانهها معمولاً با حروف بزرگ، پایانه‌ها با حروف کوچک، و نماد آغازین با
بزرگ، پایانه‌ها با حروف کوچک، و نماد آغازین با formula_2 نمایش داده می‌شوند، مثلاً گرامری با پایانه‌های formula_3 ، ناپایانه‌های formula_4، قواعد تولید: و نماد آغازین formula_2، زبان همهٔ واژه‌هایی با شکل formula_26 را تعریف می‌کند (یعنی formula_27 نسخه از formula_28 و به دنبال آن formula_27 کپی از formula_15). مورد بعدی گرامر ساده‌تری است که زبان مشابهی را تعریف می‌کند: پایانه‌های formula_3، ناپایانهٔ formula_32، نماد آغازین formula_2 ، قواعد تولید به عنوان مثالی دیگر، گرامری برای یک زیرمجموعهٔ سرگرمی از
مثالی دیگر، گرامری برای یک زیرمجموعهٔ سرگرمی از زبان انگلیسی، به صورت زیر داده شده است: پایانه‌های formula_39 ، ناپایانه‌های formula_40 ، قواعد تولید و نماد آغازین formula_41 . مثالی از اشتقاق این است: سایر رشته‌هایی که می‌توانند از این گرامر مشتق شوند "ideas hate greate linguists" و "ideas generate" هستند. این جملات بی‌معنی هستند، اما از لحاظ ساختاری صحیحند. جمله‌ای که از لحاظ ساختاری نادرست باشد، مثل "ideas ideas great hate"، نمی‌تواند از گرامر مشتق شود. به عنوان مثالی مشابه، “Colorless green ideas sleep
عنوان مثالی مشابه، “Colorless green ideas sleep furiously” از چامسکی در سال ۱۹۵۷ را ببینید؛ برای یافتن مثال‌های زبانی طبیعی‌تر و مسائل گرامرهای رسمی در این زمینه، بخش‌های گرامر ساختار عبارت و قواعد ساختار عبارت را ببینید. وراثت. سلسه مراتب چامسکی شامل سطح‌های زیر است؛ توجه داشته باشید که مجموعه گرامرهای متناظر با زبان‌های بازگشتی عضو این سلسله مراتب نمی‌باشد؛ می‌تواند به درستی بین نوع صفر و نوع اول باشد. هر زبان به طور منظم مستقل از متن است، هر زبان مستقل از متن (شامل رشته تهی نباشد) حساس به متن است، هر
از متن (شامل رشته تهی نباشد) حساس به متن است، هر زبان حساس به متن بازگشتی است و هر زبان بازگشتی به صورت بازگشتی شمارش پذیر است. این شمول‌ها مناسب همه هستند، به این معنی که زبان‌های شمارش پذیر بازگشتی ای وجود دارند که حساس به متن نیستند، زبان‌های حساس به متن ای که مستقل از متن نیست و زبان‌های مستقل از متن که منظم نیست. خلاصه. جدول زیر خلاصه هر یک از چهار نوع چامسکی از گرامرها، کلاسی که آن زبان تولید می‌کند، نوع اتوماتی که تشخیص می‌دهد و شکل قوانینی که دارد است.
پیمایش گراف به معنی بازدید از تک‌تک رأس‌های گراف به نحوی خاص است. مسئلهٔ پیمایش درخت حالت خاصی از پیمایش گراف است. برای این کار الگوریتم‌هایی چند هست. جستجوی اول سطح. جست و جوی اول سطح (Breadth_first search) یکی از ساده‌ترین الگوریتم‌ها برای جست و جوی گراف و نوعی پایه برای بسیاری از الگوریتم‌های مهم گراف است. الگوریتم درخت پوشای مینیمم( prim )و الگوریتم کوتاه‌ترین مسیرها از مبدأ(source) واحد( دایجسترا )،از ایده ای مشابه جستجوی اول سطح استفاده می‌کنند. گراف (G=(V,E و رأس مبدأ مشخص s داده شده‌است، جستجوی اول
و رأس مبدأ مشخص s داده شده‌است، جستجوی اول سطح به صورت اصولی یال‌های G را برای پیدا کردن رئوسی که از s قابل دستیابی اند، مرور می‌کند. این الگوریتم فاصله (کمترین تعداد یال‌ها) هر رأس قابل دستیابی از s را محاسبه می‌کند. همچنین «درخت اول سطح» ریشهٔ s که شامل تمامی رئوس قابل دستیابی می‌باشد را تولید می‌کند. برای هر رأس v قابل دستیابی از s مسیر واقع در درخت جستجوی اول سطح از s به v متناظر با کوتاه‌ترین مسیر (shortest path) از s‌به v در G می‌باشد، به عبارت دیگر مسیری شامل کمترین تعداد یال. الگوریتم برای هر دو
مسیری شامل کمترین تعداد یال. الگوریتم برای هر دو گراف جهت دار و بدون جهت اعمال می‌شود. در ادامه جستجوی اول سطح، هر رأس را با سفید، خاکستری یا سیاه رنگ می‌کند. همهٔ رئوس در ابتدا سفید هستند امات ممکن است بعد خاکستری و آن گاه سیاه شوند. یک رأس اولین باری که در طول جستجو ملاقات می‌گردد، کشف می‌شود، که در آن زمان غیر سفید می‌شود، بنابراین رئوس سیاه و خاکستری کشف شده‌اند اما جستجوی اول سطح بین آن‌ها تمایز قائل می‌شود تا اطمینان حاصل کند که جستجو به شکل اول سطح پیش می‌رود. اگر (E (u,v و رأس u سیاه باشد آنگاه رأس
می‌رود. اگر (E (u,v و رأس u سیاه باشد آنگاه رأس v سیاه یا خاکستری است؛ به عبارت دیگر همهٔ رئوس مجاور رئوس سیاه کشف شده‌اند. رئوس خاکستری ممکن است رأس مجاور به رنگ سفید داشته باشند؛ آن‌ها مرز بین رئوس کشف شده و کشف نشده را نشان می‌دهند. جستجوی اول سطح یک درخت اول سطح را می‌سازد، که در آغاز تنها شامل ریشه‌است که رأس منبع s می‌باشد. هر وقت رأس سفید v در مرحلهٔ پویش لیست همجواری رأس کشف شده u، کشف شود رأس v‌و یال (u,v)‌به درخت اضافه می‌شوند. می‌گوییم u ما قبل یا پدرparent) v در درخت جستجوی اول سطح است. از آن
یا پدرparent) v در درخت جستجوی اول سطح است. از آن جایی که هر رأس حداکثر یک بار کشف می‌شود، حداکثر یک پدر دارد رابطهٔ جد و نتیجه (نسل) در درخت جستجوی اول سطح به شکل معمول نسبت به ریشهٔ s تعریف می‌شود: اگر u‌در مسیری از درخت از s به v واقع باشد آنگاه u جد v‌و v نتیجهٔ u است. روال جستجوی اول سطح (BFS) زیر فرض می‌کند که گراف ورودی (G=(V,E با استفاده از لیست همجواری نمایش داده می‌شود. چندین ساختمان دادهٔ اضافی همراه هر رأس در گراف نگهداری می‌شود. رنگ هر رأس V u در متغیر color[u] و ما قبل U در متغیر ذخیره
V u در متغیر color[u] و ما قبل U در متغیر ذخیره می‌شود. اگر u فاقد ماقبل باشد (برای مثال u=s یا u کشف نشده با شد) آن گاه فاصله از منبع s تا رأس u که توسط الگوریتم محاسبه می‌شود در d[u] ذخیره می‌گردد. الگوریتم همچنین از صف اولین ورودی اولین خروجیFirst in_First Out) Q برای مدیریت مجموعه رئوس خاکستری استفاده می‌کند. برای مشاهدهٔ روند بهتری از الگوریتم به این پیوند مراجعه کنید! ۱ (Algorithm BFS(G,v) ۲ Input : G=(V,E), v(a vetex of G) ۳ Output : depends on the application ۴ begin ۵ mark v ۶ put v in the queue ۷
۴ begin ۵ mark v ۶ put v in the queue ۷ while the queue in not empty do ۸ remove first vertex w from the queue ۹ perform preWORK on w ۱۰ for all edge (w,x) such that x is unmarked do ۱۱ mark k ۱۲ put x in the queue ۱۳ end نتایج جستجوی اول سطح ممکن است به ترتیب ملاقات رئوس همجواری رأس مورد نظر بستگی داشته باشد: درخت اول سطح ممکن است تغییر کند اما فاصلهٔ d محاسبه شده توسط الگوریتم تغییر نمی‌کند. جستجوی اول عمق. همانند جستجوی اول سطح، هنگامی که رأس v در طی پویش لیست همجواری رأس u که قبلاً کشف شده، کشف می‌گردد
لیست همجواری رأس u که قبلاً کشف شده، کشف می‌گردد جستجوی اول عمق این رویداد را با قرار دادن u در فیلد ماقبل v یعنی ثبت می‌کند. بر خلاف جستجوی اول سطح که زیر گراف ماقبل آن، یک درخت را تشکیل می‌دهد، زیرگراف ماقبل تولید شده به وسیلهٔ جستجوی اول عمق ممکن است از چندین درخت تشکیل شده باشد، چون جستجو ممکن است از چند مبدأ تکرار شود. بنابراین زیرگراف ماقبل جستجوی اول عمق اندکی متفاوت با زیرگراف ماقبل جستجوی اول سطح تعریف می‌شود: فرض می‌کنیم که زیرگراف ماقبل جستجوی اول عمق، جنگل اول عمق تشکیل شده از چندین درخت اول
اول عمق، جنگل اول عمق تشکیل شده از چندین درخت اول عمق را شکل می‌دهد. یال‌ها در، یال‌های درختی نامیده می‌شوند. همانند جستجوی اول سطح، رئوس در طی جستجو جهت مشخص شدن وضعیت شان رنگ می‌شوند. هر رأس در آغاز سفید است، وقتی در جستجو کشف می‌شود، خاکستری می‌گردد و وقتی خاتمه می‌یابد، سیاه رنگ می‌شود، به عبارت دیگر وقتی لیست همجواری آن به‌طور کامل بررسی می‌گردد. این تکنیک تضمین می‌کند که هر رأس در دقیقاً یک درخت اول عمق خاتمه می‌یابد که به موجب آن درخت‌ها متمایز هستند. علاوه بر ایجاد جنگل اول عمق، جستجوی اول عمق هر
علاوه بر ایجاد جنگل اول عمق، جستجوی اول عمق هر رأس را برچسب دهی زمانی نیز می‌کند. هر رأس v دارای دو برچسب زمانی می‌باشد: وقتی رأس v در ابتدا کشف می‌گردد (خاکستری می‌گردد) اولین برچسب d]v] ثبت می‌شود و دومین برچسب زمانی f[v] زمانی ثبت می‌شود که جستجو، بررسی لیست همسایگی v را خاتمه دهد (و v را سیاه رنگ کند) این برچسب‌های زمانی در بسیاری از الگوریتم‌های گراف استفاده می‌شوند و به‌طور کلی در استدلال در مورد رفتار جستجوی اول عمق مفید هستند. روال جستجوی اول عمق(DFS) زیر، زمان کشف رأس را در متغیر d]v] و زمان
زیر، زمان کشف رأس را در متغیر d]v] و زمان خاتمهٔ رأس u را در متغیر f]u] ثبت می‌کند. این برچسب‌های زمانی اعداد صحیح بین ۱ تا ۲|V| هستند، چون برای هر یک از |V| رأس یک رویداد کشف و یک رویداد خاتمه وجود دارد. برای هر رأس u داریم: d[u] &lt; f[u رأس u قبل از d[u]، white و بین d]u] و f[u]، Gray و بعد از f[u]، Black می‌باشد. شبه کد زیر الگوریتم اصلی جستجوی اول عمق است. گراف ورودی G ممکن است جهت دار یا بدون جهت باشد. متغیر time یک متغیر سراسری است که برای برچسب دهی زمانی استفاده می‌شود. dfs(graph G) list L = empty
زمانی استفاده می‌شود. dfs(graph G) list L = empty tree T = empty choose a starting vertex x search(x) while(L is not empty) remove edge (v, w) from beginning of L if w not yet visited add (v, w) to T search(w) search(vertex v) for each edge (v, w) add edge (v, w) to the beginning of L ویژگی‌های جستجوی اول عمق. جستجوی اول عمق باعث می‌شود اطلاعات با ارزشی از ساختار گراف بدست آوریم. شاید اساسی‌ترین ویژگی جستجوی اول عمق این است که زیرگراف ما قبل به راستی یک جنگل از درخت‌ها را شکل می‌دهد، چون ساختار درخت‌ها ی
از درخت‌ها را شکل می‌دهد، چون ساختار درخت‌ها ی اول عمق، بازتاب دهندهٔ ساختار فراخوانی بازگشتی DFS_Visit می‌باشد. به عبارت دیگر اگر و فقط اگر DFS_Visit)v) در طی جستجوی لیست همجواری u فراخوانی شده باشد، به علاوه، رأس v نتیجهٔ رأس u در جنگل اول عمق است اگر و فقط اگر v در طی زمانی که u خاکستری است کشف شود. ویژگی مهم جستجوی اول عمق این است که زمان‌های کشف و خاتمه ساختار پرانتزی دارند. اگر کشف رأس u را با پرانتز چپ«u)» و خاتمه را به وسیلهٔ پرانتز راست «(u» نشان دهیم، آن گاه کشف‌ها و خاتمه‌ها یک عبارت خوش فرم در
آن گاه کشف‌ها و خاتمه‌ها یک عبارت خوش فرم در جمله ایجاد می‌کنند که پرانتزها به‌طور صحیح تو در تو می‌باشند.
بزرگترین عدد اول شناخته شده، بزرگترین عدد صحیحی می‌باشد که می‌دانیم عددی اول است. اقلیدس ثابت کرد که بینهایت عدد اول وجود دارد، بنابراین همیشه عدد اولی بزرگتر از بزرگترین عدد اول شناخته شده وجود دارد. بسیاری از ریاضی‌دانان و محققین تفننی سرگرم جستجوی بزرگترین عدد اول شناخته شده هستند؛ این ممکن است مفید نیز باشد چرا که جایزه‌هایی به وسیله بنیاد مرز الکترونیک برای کشف اعداد اول ارائه شده‌است. از آنجایی که اجرای FFT آزمون لوکاس-لمر برای اعداد مرسن سریعتر از هر آزمون دیگری برای انواع دیگر اعداد اول است، بسیاری
آزمون دیگری برای انواع دیگر اعداد اول است، بسیاری از بزرگترین اعداد اول شناخته شده عدد اول مرسن هستند؛ در میان ۱۰ بزرگترین عدد اول شناخته شده تا دسامبر ۲۰۰۷، ۶ عدد جزو اعداد مرسن بودند. آخرین ۱۳ عدد اولی که کشف شده‌اند عدد اول مرسن بودند. استفاده از کامپیوترهای الکترونیکی کشف‌ها را شتاب بخشیده‌اند، به طوری که همهٔ اعداد اول کشف شده از ۱۹۵۱ تاکنون به وسیلهٔ این کامپیوترها کشف شده‌اند. تعداد ارقام بزرگترین عدد اول شناخته شده در سال ۱۹۹۹ از مرز یک میلیون گذشت و باعث دریافت جایزه‌ای ۵۰٬۰۰۰ دلاری شد. در ژانویه
و باعث دریافت جایزه‌ای ۵۰٬۰۰۰ دلاری شد. در ژانویه سال ۲۰۱۳ میلادی بزرگ‌ترین عدد اول شناخته‌شده تا آن زمان که ۱۷٫۴۲۵٫۱۷۰ رقم دارد، توسط پروژهٔ GIMPS کشف شد: این عدد توانست سه سال این رکورد را به نام خود ثبت کند. این پروژه در جشن ۲۰ امین سالگرد افتتاح خود در ۷ ژانویه ۲۰۱۶ اقدام به معرفی یک عدد اول جدید کرده‌است.که تا سال ۲۰۱۷ بزرگترین عدد اول شناخته شده این عدد بود: این عدد ۲۲ میلیون و ۳۳۸ هزار و ۶۱۸ رقم دارد. پروفسور «کریس کوپر» از دانشگاه میزوری به عنوان داوطلب بر فرایند کشف و محاسبه این عدد نظارت
عنوان داوطلب بر فرایند کشف و محاسبه این عدد نظارت داشته‌است و البته «اسکات کورووسکی» و «آرون بلاسر» نیز از GIMPS در این فرایند و کشف این عدد همکاری داشته‌اند. این سومین رکورد پروفسور کوپر در کشف اعداد اول است. برای کشف این عدد ۳۱ روز محاسبه رایانه‌ای بر روی یک رایانه با پردازشگر اینتل i۷-۴۷۹۰ زمان صرف شده‌است و این رایانه برای کشف این عدد، عدد ۲ را و ۱۱۲۳۱۲۳۹۳۳ بار در خود ضرب کرده و سپس ۱ را از آن کم کرده‌است. در نهایت نتیجه به دست آمده به عنوان یک عدد اول تأیید شده‌است. رکورد فعلی. بزرگ ترین عدد اول
اول تأیید شده‌است. رکورد فعلی. بزرگ ترین عدد اول شناخته شده تا حالا عدد formula_1 است که ۲۴٬۸۶۲٬۰۴۸ رقم دارد و در دسامبر ۲۰۱۸ توسط پروژه GIMPS پیدا شد. ۱۲۰ رقم اول و آخر این عدد بدین قرارند: تاریخچه. جدول زیر تاریخچه بزرگترین اعداد اول شناخته شده به‌ترتیب سال پیدا شدن را نشان می‌دهد. در زیر M همان تابع مرسن است که به‌صورت formula_2 تعریف می‌شود.
کلاس پیچیدگی در نظریه پیچیدگی محاسباتی به مجموعه مسائلی گفته می‌شود که دارای پیچیدگی شبیه به هم هستند و تعریفی به شکل زیر دارند: برای مثال کلاس NP مجموعه‌ای از مسئله‌های تصمیم‌گیری هستند که توسط ماشین تورینگ غیرقطعی در زمان چندجمله‌ای حل می‌شوند در حالی که PSPACE مجموعه‌ای از مسئله‌های تصمیم‌گیری هستند که توسط ماشین تورینگ قطعی در فضای چندجمله‌ای حل می‌شوند.بعضی از کلاس‌های پیچیدگی مجموعه‌هایی از مسئله‌های تابع هستند مانند FP. روابط بین کلاس‌های پیچیدگی. جدول زیر بعضی از کلاس‌های پیچیدگی که از مسئله تصمیم
زیر بعضی از کلاس‌های پیچیدگی که از مسئله تصمیم مشتق می‌شوند را نشان می‌دهد. اگر X با خط پررنگ به Y در زیر خود وصل باشد، Y زیرمجموعه اکید X است و با خط تیره وصل باشد، Y زیرمجموعه یا مساوی X است. مهم‌ترین کلاس‌ها. تا کنون نزدیک به 500 کلاس پیچیدگی معرفی شده‌اند که در اینجا مهم‌ترین آنها را می‌آوریم:
در ریاضیات، ماتریس هادامارد یک ماتریس مربعی است که همهٔ درایه‌هایش +۱یا −۱ هستند ردیف‌ها از دو طرف متعامد هستند به این معناست که هر دو ردیف متفاوت در یک ماتریس هادامارد بردار عمودی هستند این گونه ماتریس‌ها اکثراً به‌طور مستقیم برای کد تصحیح خطا با استفاده از کد هادامارد و همچنین توسط امارگران برای تخمین واریانس استفاده می‌شود ویژگی‌ها. ماتریس هادامارد دارای درایه‌های ۱ و -۱ می‌باشد و فرم یک ماتریس هادامارد از مرتبهٔ n به صورت زیر بیان می‌شود:formula_1 که "In" ماتریس همانی "n" × "n" می‌باشد بنابراین
که "In" ماتریس همانی "n" × "n" می‌باشد بنابراین formula_2 می‌باشد. فرض کنید که M یک ماتریس مرکب از مرتبهٔ n باشد که همهٔ درایه‌هایش کراندار|"Mij"| ≤۱ برای هر "i", "j" بین ۰وn. بنابراین دترمینان هادامارد بیان می‌کند: مرتبهٔ یک ماتریس هادامارد از مرتبهٔ ۱و۲یا مضربی از ۴ می‌باشد ساختار sylvester. مثالهایی از ماتریس هادامارد اولین بار توسط جیم جوزف سیلوستر در سال ۱۸۶۷ ساخته شد. اگر ماتریس هاداماردH از مرتبهٔ n باشد آنگاه به صورت:formula_4 جزءبندی شده‌است یک ماتریس هادامارد از مرتبهٔ 2n است این کار می‌تواند به
هادامارد از مرتبهٔ 2n است این کار می‌تواند به صورت تکرای انجام و منجر به دنباله‌ای از ماتریس‌های زیر که ماتریس‌های والش نامیده می‌شوند. and برای formula_8 که formula_9 ضرب کرونکر(kroncker product) می‌باشد. سیلوستر ماتریس‌های هادامارد را از مرتبهٔ ۲"k" که k هر عدد صحیح نامنفی، ارائه کرد. ماتریس‌های سیلوستر چند ویژگی خاص دارند این ماتریس‌ها متقارن و بی اثر اند مقادیر در اولین ستون واولین ردیف همگی مثبت هستند مقادیر در دیگر ستون‌ها و ردیف‌ها به صورت هموار به مثبت و منفی تقسیم می‌شوند. ساختار تناوبی. اگر
به مثبت و منفی تقسیم می‌شوند. ساختار تناوبی. اگر مقادیر ماتریس هادامارد را با استفاده از گروه هم‌ریختی با formula_10 متناظر کنیم می‌توانیم ساختار تناوبی ماتریس هادامارد را توصیف کنیم ابتدا ماتریس formula_11 را formula_12در نظر می‌گیریم که ستون‌هایش اعداد"n" بیتی به ترتیب صعودی مرتب شدند formula_11 را می‌توان به صورت بازگشتی تعریف کنیم با استقرا:formula_14 می‌توان با استقرا نشان داد که تصویر ماتریس هادامارد تحت هم ریختی بالا به صورت:formula_16 است. فرضیه هادامارد. مهم‌ترین سؤالی در مورد ماترس هادامارد،
هادامارد. مهم‌ترین سؤالی در مورد ماترس هادامارد، موجودیت انهاست فرضیه هادامارد پیشنهاد می‌کند که یک ماتریس هادامارد از مرتبهٔ 4k برای هر عدد مثبت k وجود دارد ساختار سیلوستر در سال ۱۸۶۷ ماتریس‌های از مرتبهٔ ۱٬۲٬۴٬۸٬۱۶٬۳۲ و غیره ارائه کرد پس ماتریس هادامارد از مرتبهٔ ۱۲و ۲۰ توسط هادامارد (در سال ۱۸۹۳) ساخته شد بعداً در سال ۱۹۳۳، ریماند پالی نشان داد که چگونه یک ماتریس هادامارد از مرتبهٔ q+1 کهq یک عدد اول به پیمانه ی ۴ برابر ۳، ساخت او همچنین ماتریس‌هایی از مرتبه 2(q+۱) برای عدد اول q که به پیمانهٔ ۴ بربر ۱،
2(q+۱) برای عدد اول q که به پیمانهٔ ۴ بربر ۱، ساخت. فرضیهٔ هادامارد به پالی نسبت داده شد. کوچکترین مرتبه‌ای که با روش پالی و سیلوستر ساخته نمی‌شود ۹۲ است روش‌های متعدد دیگری تا به حال برای ساختن ماتریس‌های هادامارد ارائه شده در حال حاضر ۶۶۸ کوچکترین مرتبه‌ای است که هیچ ماتریس هاداماردی برایش ساخته نشده‌است. منابع. ویکی‌پدیای انگلیسی
در ریاضیات یک عدد ابرتام ، عددی صحیح مانند n است که در رابطهٔ زیر صدق کند که در آن σ تابع تقسیم کننده می‌باشد. اولین اعداد ابرتام عبارتند از :۲، ۴، ۱۶، ۶۴، ۴۰۹۶، ۶۵۵۳۶، ۲۶۲۱۴۴. اگر n یک عدد ابرتام زوج باشد باید به شکل توانی از ۲ مانند ۲"k" باشد به طوری که۲"k"+۱-۱ یک عدد اول مرسن باشد. هنوز مشخص نیست که آیا عدد ابرتام فردی وجود دارد یا نه. یک عدد ابرتام فرد مانند n باید مربع کامل باشد به طوری هم n و هم (σ(n حداقل بر ۳ عدد اول متمایز بخشپذیر باشند. هیچ عدد ابرتام فردی کوچکتر از ۷x۱۰"۲۴" وجود ندارد. اعداد کامل
فردی کوچکتر از ۷x۱۰"۲۴" وجود ندارد. اعداد کامل و ابرتام زیر مجموعه‌ای از دسته‌ای بزرگتر از اعداد به نام (m،k)-کامل هستند که در رابطهٔ زیر صدق می‌کنند با این نماد گذاری اعداد کامل (۱،۲)-کامل هستند و اعداد ابرتام (۲،۲)-کامل می باشند. دسته‌های دیگری از اعداد (m،k)-کامل عبارتند از : منابع. English Wikipedia : Superperfect Numbers
در فلسفه و علوم بلاغی، اصل حسن ظن (به انگلیسی: Principle of charity) تلاشی است برای در نظر گرفتن معقول‌ترین و قابل دفاع‌ترین تعبیر ممکن از مدعای گوینده. به عبارتی دیگر تلاش برای بهترین تعبیر ممکن از سخن گوینده به شکلی که با منظور او یکی باشد. در واقع هدف از این اصل متدولوژیک پرهیز از نسبت دادن دروغ و مغالطه‌های منطقی به مدعای دیگری است تا وقتی که تعبیر عقلانی دیگری از آن مدعا وجود دارد. برای مثال تصور کنید کسی در حال بلند کردن یک جعبه از روی زمین است و می‌گوید: «این جعبه یک تن وزن دارد». شنونده این سخن
«این جعبه یک تن وزن دارد». شنونده این سخن می‌تواند با توجه به معنی تحت الفظی کلمات، گوینده را به مغالطه و دروغ‌گویی متهم کند. درحالیکه بر اساس اصل حسن ظن باید به جای این برداشت، منظور گوینده را در نظر بگیرد که به احتمال بسیار زیاد اشاره به سنگینی جعبه دارد. به گفتهٔ سیمون بلک‌برن (۱۹۹۴): «این مفسر را مجبور می‌کند حقیقت یا عقلانیت را در مدعا بیشینه کند.» اصل هم‌دلی در سال ۱۹۵۸–۵۹ توسط نیل ال. ویلسون نام‌گذاری شد و ویلارد فان اورمان کواین و دانلد دیویدسن صورت‌بندی‌های مختلف این اصل را ارائه داده‌اند. دیویدسن
مختلف این اصل را ارائه داده‌اند. دیویدسن گاهی آن را اصل سازگاری عقلانی نیز می‌خواند. او این اصل را بدین صورت جمع‌بندی می‌کند: «ما از طریق تفسیرآراء و افکار دیگران به روشی که به کم‌ترین تناقض ممکن بینجامد بیش‌ترین درک را از آن‌ها به دست می‌آوریم.» از سوی دیگر کواین این اصل را تلاشی برای فهم استدلال‌های منطقی می‌داند مخصوصاً زمانی که مطمئن نیستیم معنای سخن گوینده را کاملاً درک کرده‌ایم. از زمان کواین و دیگران، فلاسفه دست‌کم چهار روایت مختلف از این اصل را ارائه داده‌اند. اصل انسانیت –که متممی برای اصل هم‌دلی
داده‌اند. اصل انسانیت –که متممی برای اصل هم‌دلی است– می‌گوید هنگام تفسیر سخن دیگری باید فرض کنیم باورها و خواسته‌های او به نوعی با هم و با حقیقت پیوستگی دارند و «ما گزاره‌هایی را به گوینده نسبت می‌دهیم که اگر خودمان در آن شرایط می‌بودیم به کار می‌بردیم.» اصل انسانیت در سال ۱۹۷۳ توسط ریچارد گرندی نام‌گذاری شد.
در علوم رایانه مسئلهٔ جمع زیرمجموعه‌ها از اهمیت مهمی در تئوری پیچیدگی و رمزنگاری برخوردار است، مسئله این است که اگر مجموعه‌ای از اعداد صحیح داشته باشیم ایا زیرمجموعه ناتهی وجود دارد که جمع اعضایش برابر ۰ شود؟ برای مثال در مجموعه {۱٬۳،-۲،-۵٬۹٬۴} زیرمجموعه‌ای مانند {-۵،-۲٬۳٬۴} وجود دارد که جمع اعضایش برابر ۰ است. مسئله جمع زیرمجموعه‌ها NP است و احتمالا یکی از اسانترین انان است. صورت دیگر این مسئله این است که ایا زیرمجموعه ناتهی از مجموعه‌ای از اعداد صحیح وجود دارد که جمع اعضایش برابر عدد صحیح s شود؟ مسئله
دارد که جمع اعضایش برابر عدد صحیح s شود؟ مسئله دیگری که به نام subset sum problem معروف است این مسئله‌است که درمجموعه‌ای از اعداد طبیعی، اگر مجموع اعضای زیر مجموعه‌ها را در نظر گیریم، عدد که بیشترین تکرار را دارد، چند بار تکرار می‌شود؟ پورکتر در سال ۱۹۸۲ این مسئله را برای مجموعهٔ {۱٬۲٬۳…} حل کرد. برای n=1٬۲،… جواب برابر است با ۱، ۱، ۲، ۲، ۳، ۵، ۸، ۱۴، ۲۳،… و تعداد اعداد متفاوت ایجاد شده برای n=1٬۲،… برابر است با ۲، ۴، ۷، ۱۱، ۱۶، ۲۲، ۲۹، ۳۷، ۴۶، ۵۶،... برای مثال برای n=3، زیر مجموعه‌های مجموعه {۱٬۲٬۳}می
مثال برای n=3، زیر مجموعه‌های مجموعه {۱٬۲٬۳}می بینیم: formula_1 formula_2 formula_3 formula_4 formula_5 formula_6 formula_7 formula_8 پس عددی که بیشتر از همه ظاهر می‌شود عدد ۳ است که ۲ بار تکرار می‌شود و ۷ عدد متفاوت ایجاد می‌شود. این مسئله را می‌توان با استفاده از توابع مولد حل نمود. اگر formula_9 تعداد روش‌های انتخاب m عدد از میان Mعدد formula_10 باشد بصورتی که جمعشان برابر s باشد و اگر تابع مولد زیر را داشته باشیم: formula_11 با نوشتن بر حسب توان‌های y داریم: formula_12 formula_13 برای مثال فرض کنید
y داریم: formula_12 formula_13 برای مثال فرض کنید می‌خواهیم m شی را از {۱٬۲٬۳٬۴٬۵} انتخاب کنیم؛ تابع مولد به صورت زیر است: و برای مثال انتخاب m=3 دارای تابع مولد زیر است: formula_14 formula_15 پس تعداد روش‌های انتخاب ۳ عدد از میان ۵ عدد که جمعشان عددی بین ۱۲٬۱۱،…،۶ باشد ضرایب formula_16 است که همان formula_17 می‌باشد که برابر ۱٬۱٬۲٬۲٬۲٬۱٬۱ است. ۶ formula_18(۱، ۲، ۳) ۷ formula_18(۱، ۲، ۴) ۸formula_18 (۱، ۲، ۵)، (۱، ۳، ۴) ۹formula_18 (۱، ۳، ۵)، (۲، ۳، ۴) ۱۰formula_18 (۱، ۴، ۵)، (۲، ۳، ۵) ۱۱formula_18 (۲، ۴،
(۱، ۴، ۵)، (۲، ۳، ۵) ۱۱formula_18 (۲، ۴، ۵) ۱۲formula_18 (۳، ۴، ۵) منابع. http://mathworld.wolfram.com/SubsetSumProblem.html http://www.math.sunysb.edu/~scott/blair/Subset_sum_problems_are.html https://web.archive.org/web/20080307085025/http://www-fs.informatik.uni-tuebingen.de/~reinhard/krypto/English/4.5.1.e.html لینک‌ها. www.cs.dartmouth.edu/~ac/Teach/CS۱۰۵-Winter۰۵/Notes/nanda-scribe-۳.pdf www.cs.umass.edu/~barring/cs۶۱۱/lecture/۱۸.pdf
لم زرن یکی از مفیدترین اصولی است که هم ارز اصل انتخاب است، اصلی است که اولین بار در سال ۱۹۱۴ مطرح شد و به نام لم زرن معروف است، لم زرن به صورت زیر مطرح می‌شود: اگر formula_1 یک مجموعه مرتب جزئی باشد، بطوریکه هر زیر مجموعه کاملاً مرتب آن، دارای کران بالا (در A) باشد، آنگاه A دارای عضو ماکزیمال است. اثبات. با توجه به اصل ماکزیمالی هاسدورف، formula_2 دارای زیر مجموعه کاملاً مرتبی مانند B است که نسبت به رابطه شمول formula_3 ماکزیمال است. بنا به فرض، B دارای یک کران بالا به نام u است. نشان می‌دهیم که u یک عضو
کران بالا به نام u است. نشان می‌دهیم که u یک عضو ماکزیمال از A است.اگر عضوی مانند formula_4 وجود داشته باشد، بطوریکه formula_5، آنگاه formula_6، زیر مجموعه کاملاً مرتبی از Aاست که شامل زیر مجموعه ماکزیمال کاملاً مرتب B می‌باشد. در نتیجه می‌بایست formula_7 باشد که نتیجه می‌دهد formula_8. این ثابت می‌کند که u عضو ماکزیمال مجموعه formula_2 است. لم فوق نمونه‌ای از یک خاصیت وجودی است که ادعا می‌کند عضو ماکزیمال در مجموعه مرتب جزئی خاص وجود دارد.اما اثبات این قضیه، روشی را برای تعیین این عضو ماکزیمال ارائه
قضیه، روشی را برای تعیین این عضو ماکزیمال ارائه نمی‌دهد. به عنوان کاربرد لم زرن، قضیه زیر را بیان و اثبات می‌کنیم. قضیه. اگر A،Bدو مجموعه غیر تهی باشند، آنگاه تابع یک به یکی از Aبه Bو یا یک تابع یک به یک از Bبه A وجود دارد. اثبات فرض می‌کنیم X مجموعه تمام زوجهای مرتب formula_10 کهformula_11 زیر مجموعه‌ای از A و همچنین formula_12 تابعی یک به یک است، باشند. رابطه formula_13را روی X به طریق زیر تعریف می‌کنیم : formula_14 مسلما این رابطه ترتیبی جزئی است. به منظور استفاده از لم زرن، باید مطمئن شویم که هر زیر
استفاده از لم زرن، باید مطمئن شویم که هر زیر مجموعه کاملاً مرتب formula_15 از X دارای یک کران بالاست. formula_16 یک حدس خوب برای کران بالای مجموعه T، است. قرار می‌دهیم: formula_17 آنگاه formula_18 طوری است که اگرformula_19، آنگاه formula_20 برای اثبات خوش تعریف بودن formula_18، فرض می‌کنیم که x به زیر مجموعه دیگری مانند formula_22 هم باشدformula_23. آنگاه formula_24 یا formula_25، که در هر حالت داریم formula_26، که نشان می‌دهدformula_27، خوش تعریف است. حال نشان می‌دهیم که formula_18 تابعی یک به یک است.برای
می‌دهیم که formula_18 تابعی یک به یک است.برای این منظور فرض می‌کنیم، به ازای formula_29 خواهیم داشت formula_30. آنگاه دو زوج مرتب formula_31 چنان وجود دارند کهformula_32. دوباره مثل قبل : formula_24 یا formula_25 بدون اینکه در اثبات خللی وارد شود، فرض می‌کنیم formula_24. از فرض اخیر نتیجه می‌شود formula_36، که و لذا با توجه به یک به یک بودن formula_37 داریمx=y.به این ترتیب اثبات یک به یک بودن formula_27 تکمیل می‌شود. بنابراین: به ازای هر formula_39، داریم formula_40. پس formula_41 در شرایط لم زرن صدق