در یک درخت جستجوی باینری کدام عمل در 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هاي خیلی بـزرگ روزهـاي باقیمانده از عمر خرس ما تابع کدام یک از گزینه ها خواهد بود؟
تابع به دست آمده برای سوال بالا کدام یک از گزینه های زیر می باشد؟
Anonymous Quiz
14%
O(n*n)
43%
O(n)
29%
O(log n)
15%
O(n^2)
یکی دیگر از الگوریتم های جست و جوی ناآگاهانه که میخواهیم در مورد آن صحبت کنیم جست جوی هزینه یکنواخت (UCS) می باشد در این جستجو هر بار کم هزینه ترین گره گسترش نیافته را گسترش میدهد. در این الگوریتم از یک صف اولویت دارم استفاده می شود.
نکته:این الگوریتم کامل می باشد اگر هزینه تمان عمل هایی که در ان انجام میدهیم مثبت باشد.
نکته: این الگوریتم بهینه می باشد اگر هزینه تمام عمل ها مثبت باشد.
پیچدگی زمانی و مکانی این الگوریتم به صورت نمایی میباشد.
یکی دیگر از نکاتی که باید به آن توجه کرد این است که این الگوریتم در تمام جهت ها گسترش پیدا میکند و بدون توجه به هدف نودهای خود را گسترش میدهد.
📣👨💻 @AlgorithmDesign_DataStructuer
نکته:این الگوریتم کامل می باشد اگر هزینه تمان عمل هایی که در ان انجام میدهیم مثبت باشد.
نکته: این الگوریتم بهینه می باشد اگر هزینه تمام عمل ها مثبت باشد.
پیچدگی زمانی و مکانی این الگوریتم به صورت نمایی میباشد.
یکی دیگر از نکاتی که باید به آن توجه کرد این است که این الگوریتم در تمام جهت ها گسترش پیدا میکند و بدون توجه به هدف نودهای خود را گسترش میدهد.
📣👨💻 @AlgorithmDesign_DataStructuer
👍2