خب امشب میخواهیم در مورد برنامه ریزی پویا یا همان Dynamic Programing صحبت کنیم خب در قطعه کد اولی که کد بازگشتی اعداد بازگشتی می باشد همان طور که میدانیم بر خلاف ظاهرش که در تعداد خط کمی نوشته شده است اما دارای پیچیدگی زمانی نمایی می باشد. ما کلا از پیچیدگی زمانی بدمان میاید پس میاییم برای اینکه آن را از نمایی در بیاریم متوصل میشیم به برنامه ریزی پویا که در قطعه کد دوم از این راه نوشته شده است که از نمایی به پیچیدگی خطی رسیدیم.
نکته: در کدهایی که به صورت بازگشتی نوشته می شود ما میاییم به صورت بالا به پایین عمل میکنیم یعنی اگر از لحاظ درخت بگوییم یعنی از ریشه شروع می کنیم تا به برگ برسیم ولی در برنامه ریزی پویا به صورت پایین به بالا عمل میکنیم یعنی از برگه ها حرکت میکنیم و به ریشه میرسیم.
برنامه ریزی پویا کاربردهای فراوانی در ساختمان داده و خیلی جاهای دیگر دارد زیرا سعی میکند تا حد مقبولی پیچیدگی را کاهش دهد زیرا کلا در کامپیوتر و برنامه هایی که نوشته می شود سعی میشود که کمترین پیچیدگی را بر روی آن اعمال کنیم.
ممنون میشم برای دوستانتون بفرستید تا از مطالب بهره ببرند😉👋
📣👨💻 @AlgorithmDesign_DataStructuer
نکته: در کدهایی که به صورت بازگشتی نوشته می شود ما میاییم به صورت بالا به پایین عمل میکنیم یعنی اگر از لحاظ درخت بگوییم یعنی از ریشه شروع می کنیم تا به برگ برسیم ولی در برنامه ریزی پویا به صورت پایین به بالا عمل میکنیم یعنی از برگه ها حرکت میکنیم و به ریشه میرسیم.
برنامه ریزی پویا کاربردهای فراوانی در ساختمان داده و خیلی جاهای دیگر دارد زیرا سعی میکند تا حد مقبولی پیچیدگی را کاهش دهد زیرا کلا در کامپیوتر و برنامه هایی که نوشته می شود سعی میشود که کمترین پیچیدگی را بر روی آن اعمال کنیم.
ممنون میشم برای دوستانتون بفرستید تا از مطالب بهره ببرند😉👋
📣👨💻 @AlgorithmDesign_DataStructuer
👌4👍3
مسائل جستجو(Search Problems):
بعد از اینکه در مورد انواع عامل ها صحبت کردیم میخواهیم در مورد مسائل جستجو بحث کنیم. کلا در ریاضیات نظریه و مباحث های محاسباتی جستجو نوعی از مسائل محاسباتی می باشد که با یک رابطه دودویی نشان داده می شود. به طور شهودی بخواهیم در موردآن صحبت کنیم مشکلمون در پیدا کردن یک ساختاری مانند y هست در شی یا محیطی مانند x می باشد. به طور واضح تر بخواهیم در مورد ان بحث کنیم یعنی یک محیط داریم و میخواهیم با استفاده از اون دانشی که داریم به اون هدف مورد نظرمون در اون محیط برسیم.
📣👨💻 @AlgorithmDesign_DataStructuer
بعد از اینکه در مورد انواع عامل ها صحبت کردیم میخواهیم در مورد مسائل جستجو بحث کنیم. کلا در ریاضیات نظریه و مباحث های محاسباتی جستجو نوعی از مسائل محاسباتی می باشد که با یک رابطه دودویی نشان داده می شود. به طور شهودی بخواهیم در موردآن صحبت کنیم مشکلمون در پیدا کردن یک ساختاری مانند y هست در شی یا محیطی مانند x می باشد. به طور واضح تر بخواهیم در مورد ان بحث کنیم یعنی یک محیط داریم و میخواهیم با استفاده از اون دانشی که داریم به اون هدف مورد نظرمون در اون محیط برسیم.
📣👨💻 @AlgorithmDesign_DataStructuer
در یک درخت جستجوی باینری کدام عمل در O(1) انجام می شود؟
Anonymous Quiz
60%
بررسی تهی بودن درخت
11%
حذف یک عنصر
15%
پیدا کردن کمترین مقدار
15%
درج کردن یک عنصر جدید
This media is not supported in your browser
VIEW IN TELEGRAM
چراغ راهنمایی که هیچ وقت سبز نمیشود !
مگر اینه موارد ایمنی در پشت چراغ قرمز رعایت شود.
در این پروژه ی پردازش تصویر ، سوژه اصلی یک موتور سوار هست و ملاک اصلی عملکرد چراغ راهنما بر اساس موارد ایمنی مربوط به موتور سوار هست.
اگر چنانچه موتور سوار، موارد ایمنی را رعایت کند، چراغ سبز می شود.
📣👨💻 @AlgorithmDesign_DataStructuer
مگر اینه موارد ایمنی در پشت چراغ قرمز رعایت شود.
در این پروژه ی پردازش تصویر ، سوژه اصلی یک موتور سوار هست و ملاک اصلی عملکرد چراغ راهنما بر اساس موارد ایمنی مربوط به موتور سوار هست.
اگر چنانچه موتور سوار، موارد ایمنی را رعایت کند، چراغ سبز می شود.
📣👨💻 @AlgorithmDesign_DataStructuer
👌7🤩2
در ادامه مطلبی که در مورد جستجو گقته شد حال میخایم در مورد الگوریتم هایی بحث کنیم تحت عنوان استراتژی های ناآگاهانه که به آن ها نیز Uniformed Search هم گفته میشود. این الگوریتم تنها از اطلاعات موجود در تعریف سوال برای جستجو استفاده می کند که تنها میتواند حالت های هدف را از حالت های غیر هدف تشخیص دهد.
انواع جستجوی ناآگاهانه:
جستجوی سطحی
جستجوی عمقی
جستجوی عمقی محدود
جستوجوی هزینه یکنواخت
جستجوی عمق کننده تکرای
در مورد همه موارد بالا یکی توضیح خواهیم داد.
📣👨💻 @AlgorithmDesign_DataStructuer
انواع جستجوی ناآگاهانه:
جستجوی سطحی
جستجوی عمقی
جستجوی عمقی محدود
جستوجوی هزینه یکنواخت
جستجوی عمق کننده تکرای
در مورد همه موارد بالا یکی توضیح خواهیم داد.
📣👨💻 @AlgorithmDesign_DataStructuer
🔥3👍1👏1
This media is not supported in your browser
VIEW IN TELEGRAM
الگوریتم Dijkstra که از آ شروع میکند و میخواهد به ح که مقصد هست برسد.
📣👨💻 @AlgorithmDesign_DataStructuer
📣👨💻 @AlgorithmDesign_DataStructuer
👍3💯1
یک درخت جستجوی دودوی با کلمه "SEARCH"(از چپ به راست) بسازید. تعداد متوسط برای پیدا کردن یک کاراکتر در این درخت برابر است با:
Anonymous Quiz
27%
2.83
36%
2.4
21%
2.6
15%
6
This media is not supported in your browser
VIEW IN TELEGRAM
Breadth-First-Search-Algorithm
اولین الگوریتم جستجوی ناآگاهانه که در مورد آن صحبت میکنیم جستجوی سطحی می باشد. این الگوریتم هر بار سطحی ترین نود را گسترش می دهد. نحوه ی پیاده سازی آن صف می باشد(FIFO) می باشد به این معنی که هرچی که اول امد همون اول هم خارج بشه و نود جدید به آخر صف نیز اضافه می شود.
خب میخواهیم در مورد کامل بودن این الگوریتم حرف بزنیم. این الگوریتم کامل می باشد به این معنی که در صورت وجود راه حل, پیدا کردن راه حل را تضمین میکند بله درصورتی که میزان گسترش محدود باشد.
این الگوریتم تقریبا بهینه می باشد به این معنی که همراه کم هزینه ترین مسیر را پیدا میکند که تقریبا در این الگوریتم اتفاق می افتد.
#هوش_مصنوعی
📣👨💻 @AlgorithmDesign_DataStructuer
اولین الگوریتم جستجوی ناآگاهانه که در مورد آن صحبت میکنیم جستجوی سطحی می باشد. این الگوریتم هر بار سطحی ترین نود را گسترش می دهد. نحوه ی پیاده سازی آن صف می باشد(FIFO) می باشد به این معنی که هرچی که اول امد همون اول هم خارج بشه و نود جدید به آخر صف نیز اضافه می شود.
خب میخواهیم در مورد کامل بودن این الگوریتم حرف بزنیم. این الگوریتم کامل می باشد به این معنی که در صورت وجود راه حل, پیدا کردن راه حل را تضمین میکند بله درصورتی که میزان گسترش محدود باشد.
این الگوریتم تقریبا بهینه می باشد به این معنی که همراه کم هزینه ترین مسیر را پیدا میکند که تقریبا در این الگوریتم اتفاق می افتد.
#هوش_مصنوعی
📣👨💻 @AlgorithmDesign_DataStructuer
👍4🔥2
T(n)=T(n/8)+3b
T(1)=1
پیچیدگی رابطه بازگشتی بالا کدام یک از گزینه ها می باشد؟
T(1)=1
پیچیدگی رابطه بازگشتی بالا کدام یک از گزینه ها می باشد؟
Anonymous Quiz
30%
O(n)
14%
O(n/2)
42%
O(log n)
15%
O(n log n)
Depth-first search (DFS)
یکی دیگر از جستجو های ناآگاهانه که میخواهیم در مورد آن صحبت کنیم جستجوی عمقی می باشد. این الگوریتم ناآگاهانه به این صورت عمل میکند که در جهت گسترش بده که عمیق ترین گره در آن وجود داشته باشد. این الگوریتم به صورت LIFO می باشد یعنی با استفاده از پشته قابل پیاده سازی می باشد. این الگوریتم کامل نمی باشد یعنی برای پیدا کردن راه حل برای رسیدن به هدف مورد نظر آن را پیدا نکند و این خیلی بد نظر می اید.
در مورد بهینه بودن هم این الگوریتم بهینه نمی باشد یعنی اگر راه حل را نیز پیدا کند با کمترین هزینه به هدف نمی رسد و هزینه زیادی را برای پیدا کردن هدف صرف میکند.
پیچیدگی آن نمایی می باشد زیرا باید تا آخرین عمق برای پیدا کردن هدف برود.
از نظر پیچیدگی مکانی به صرفه می باشد زیرا پیچیدگی مکانی آن خطی می باشد.
#هوش_مصنوعی
📣👨💻 @AlgorithmDesign_DataStructuer
یکی دیگر از جستجو های ناآگاهانه که میخواهیم در مورد آن صحبت کنیم جستجوی عمقی می باشد. این الگوریتم ناآگاهانه به این صورت عمل میکند که در جهت گسترش بده که عمیق ترین گره در آن وجود داشته باشد. این الگوریتم به صورت LIFO می باشد یعنی با استفاده از پشته قابل پیاده سازی می باشد. این الگوریتم کامل نمی باشد یعنی برای پیدا کردن راه حل برای رسیدن به هدف مورد نظر آن را پیدا نکند و این خیلی بد نظر می اید.
در مورد بهینه بودن هم این الگوریتم بهینه نمی باشد یعنی اگر راه حل را نیز پیدا کند با کمترین هزینه به هدف نمی رسد و هزینه زیادی را برای پیدا کردن هدف صرف میکند.
پیچیدگی آن نمایی می باشد زیرا باید تا آخرین عمق برای پیدا کردن هدف برود.
از نظر پیچیدگی مکانی به صرفه می باشد زیرا پیچیدگی مکانی آن خطی می باشد.
#هوش_مصنوعی
📣👨💻 @AlgorithmDesign_DataStructuer
👏2⚡1
آرایه مجموعه ای از عناصر داده مشابه است که در مکان های حافظه به هم پیوسته ذخیره شده و با استفاده از یک نام یا فهرست مشترک به آنها دسترسی پیدا می کند. به عبارت دیگر، آرایه مجموعه ای از متغیرهای هم نوع داده است که با یک نام به آنها دسترسی پیدا می کند.
📣👨💻 @AlgorithmDesign_DataStructuer
📣👨💻 @AlgorithmDesign_DataStructuer
🎉1👌1
int sum = N;
for (int i = 0; i < 1000000; i++) {
for (int j = 1; j <= i; j++) { sum += N; } for (int j = 1; j <= i; j++) { sum += N; } for (int j = 1; j <= i; j++) { sum += N; } } System.out.println(sum); پیچیدگی زمانی کد بالا کدام گزینه می باشد؟
for (int i = 0; i < 1000000; i++) {
for (int j = 1; j <= i; j++) { sum += N; } for (int j = 1; j <= i; j++) { sum += N; } for (int j = 1; j <= i; j++) { sum += N; } } System.out.println(sum); پیچیدگی زمانی کد بالا کدام گزینه می باشد؟
Anonymous Quiz
24%
O(1)
19%
O(N)
35%
O(N^3)
23%
O(N^2)
🤔7
Algorithm design & data structure
int sum = N;
for (int i = 0; i < 1000000; i++) {
for (int j = 1; j <= i; j++) { sum += N; } for (int j = 1; j <= i; j++) { sum += N; } for (int j = 1; j <= i; j++) { sum += N; } } System.out.println(sum); پیچیدگی زمانی کد بالا کدام گزینه می باشد؟
for (int i = 0; i < 1000000; i++) {
for (int j = 1; j <= i; j++) { sum += N; } for (int j = 1; j <= i; j++) { sum += N; } for (int j = 1; j <= i; j++) { sum += N; } } System.out.println(sum); پیچیدگی زمانی کد بالا کدام گزینه می باشد؟
خب نکته ایی که در این سوال هست این است در حلقه فور اول شرط خاتمه را 1000000 قرار دادم که این نشان دهنده ای یک عدد ثابت می باشد که میتوان پیچیدگی خودش و هر چیزی که در داخل حلقه اول قرار دارد را 1 گرفت پس میتوان نوشت :
T(n)=O(1)
T(n)=O(1)
👍2
حداکثر تعداد دوران در درج یک عنصر در یک درخت قرمز سیاه با n عنصر برابر است با:
Anonymous Quiz
9%
1
30%
2
48%
log n
13%
n
یکی دیگر از الگوریتم های جستجوی ناآگاهانه افزایش عمق به صورت تکراری می باشد. در این الگوریتم میایم DFS را با عمق یک اجرا می کنیم اگر جواب پیدا نشد میایم DFS را با عمق دو اجرا میکنیم باز اگر به جواب نرسیدیم عمق بعدی را پیمایش میکنیم تا به هدف برسیم.
در واقع این الگوریتم ترکیبی است از DFS و BFS که میایم یک عمق پیمایش میکند و در اون عمق سطحی هم پیمایش میکند. در واقع امدیم از پیچیدگی زمانی BFS و پیچیدگی مکانی DFS که هر کدام در این پیچیدگی ها خوب هستند استفاده کردیم تا به یک الگوریتم بهینه و کاملی برسیم.
#هوش_مصنوعی
📣👨💻 @AlgorithmDesign_DataStructuer
در واقع این الگوریتم ترکیبی است از DFS و BFS که میایم یک عمق پیمایش میکند و در اون عمق سطحی هم پیمایش میکند. در واقع امدیم از پیچیدگی زمانی BFS و پیچیدگی مکانی DFS که هر کدام در این پیچیدگی ها خوب هستند استفاده کردیم تا به یک الگوریتم بهینه و کاملی برسیم.
#هوش_مصنوعی
📣👨💻 @AlgorithmDesign_DataStructuer
👍2
ماتریس مجاورت:
در واقع ماتریس مجاورت یک بردار n در n می باشد که اگر یالی بین i و j وجود داشته باشد 1 می شود در غیر این صورت 0.
یک مثال برای درک بهتر بخواهیم بزنیم این است که در مثال بالا 4 نود داریم پس باید بردار 4 در 4 بکشیم همان طور که میبینید V0 و V0 یالی بین آن ها نیست پس صفر قرار می دهیم ولی اگر بین V0 و V1 را ببینید یالی وجود دارد پس آن را 1 قرار میدهیم و به همین صورت ادامه میدهیم.
📣👨💻 @AlgorithmDesign_DataStructuer
در واقع ماتریس مجاورت یک بردار n در n می باشد که اگر یالی بین i و j وجود داشته باشد 1 می شود در غیر این صورت 0.
یک مثال برای درک بهتر بخواهیم بزنیم این است که در مثال بالا 4 نود داریم پس باید بردار 4 در 4 بکشیم همان طور که میبینید V0 و V0 یالی بین آن ها نیست پس صفر قرار می دهیم ولی اگر بین V0 و V1 را ببینید یالی وجود دارد پس آن را 1 قرار میدهیم و به همین صورت ادامه میدهیم.
📣👨💻 @AlgorithmDesign_DataStructuer
در یک زمستان سرد، خرس قطبی n قطعه گوشت دقیقاً به اندازههاي 1 تا n را در غاري ذخیره کرده است. او هر روز یکی از این قطعه گوشتها را بـه صـورت تـصادفی انتخـاب میکند. اگر اندازهي گوشت عدد فردي بود، آن را کاملاً میخورد. اگر زوج بود، آن را دقیقاً نصف میکند، یک نصف آن را میخورد و نصف دیگر را مجدداً در غار قرار مـیدهـد. اگـر گوشتی موجود نباشد، خرس میمیرد. با این الگوریتم، براي nهاي خیلی بـزرگ روزهـاي باقیمانده از عمر خرس ما تابع کدام یک از گزینه ها خواهد بود؟