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
فرض کنید عنصري در آرایه n عنصري، بیش ازn/3 بار تکرار شده باشد. بهترین الگـوریتم براي یافتن این عنصر با هزینه حافظه مصرفی (1)O داراي چه هزینه زمانی است؟
Anonymous Quiz
34%
O(n)
18%
O(1)
31%
O(log n)
18%
گزینه 1 و 2
🔥2
اولین سوالی که ممکن است پیش بیاید این است که شبکه های عصبی چیست؟
شبکه عصبی مصنوعی (ANN) سیستمی است که مبتنی بر شبکه عصبی بیولوژیکی مانند مغز است. مغز تقریباً 100 میلیارد نورون دارد که از طریق سیگنال های الکتروشیمیایی با یکدیگر ارتباط برقرار می کنند. نورون ها از طریق اتصالاتی به نام سیناپس به هم متصل می شوند. هر نورون هزاران ارتباط با نورون های دیگر دریافت می کند و دائماً سیگنال های دریافتی را برای رسیدن به بدن سلولی دریافت می کند. اگر مجموع سیگنال های حاصل از آستانه معینی فراتر رود، پاسخی از طریق آکسون ارسال می شود. ANN تلاش می کند تا آینه محاسباتی شبکه عصبی بیولوژیکی را بازسازی کند، اگرچه قابل مقایسه نیست زیرا تعداد و پیچیدگی نورون ها و موارد استفاده شده در یک شبکه عصبی بیولوژیکی چندین برابر بیشتر از شبکه های عصبی مصنوعی است.
وظیفه شبکه عصبی این است که بیاید برای مسائلی که فرمول براشون تعریف شده بیاد و روابط بین فاکتورهای مختلف را ایجاد کند ولو به صورت نسبی و یا همراه با خطا.پ
#هوش_مصنوعی
📣👨💻 @AlgorithmDesign_DataStructuer
شبکه عصبی مصنوعی (ANN) سیستمی است که مبتنی بر شبکه عصبی بیولوژیکی مانند مغز است. مغز تقریباً 100 میلیارد نورون دارد که از طریق سیگنال های الکتروشیمیایی با یکدیگر ارتباط برقرار می کنند. نورون ها از طریق اتصالاتی به نام سیناپس به هم متصل می شوند. هر نورون هزاران ارتباط با نورون های دیگر دریافت می کند و دائماً سیگنال های دریافتی را برای رسیدن به بدن سلولی دریافت می کند. اگر مجموع سیگنال های حاصل از آستانه معینی فراتر رود، پاسخی از طریق آکسون ارسال می شود. ANN تلاش می کند تا آینه محاسباتی شبکه عصبی بیولوژیکی را بازسازی کند، اگرچه قابل مقایسه نیست زیرا تعداد و پیچیدگی نورون ها و موارد استفاده شده در یک شبکه عصبی بیولوژیکی چندین برابر بیشتر از شبکه های عصبی مصنوعی است.
وظیفه شبکه عصبی این است که بیاید برای مسائلی که فرمول براشون تعریف شده بیاد و روابط بین فاکتورهای مختلف را ایجاد کند ولو به صورت نسبی و یا همراه با خطا.پ
#هوش_مصنوعی
📣👨💻 @AlgorithmDesign_DataStructuer
👏2
This media is not supported in your browser
VIEW IN TELEGRAM
خب امروز میخواهیم در مورد کد هافمن حرف بزنیم و با ویژگی های آن در ساختمان داده آشنا شویم.
اولین ویژگی آن این است که آن طوری طراحی شده که هیچ کدی پیشوند کد دیگری نباشد. در مثال بالا یکسری کاراکتر وجود دارد و در زیر هر کدام فراوانی آن نوشته شده این ابتدا دو کاراکتری که فراوانی کمتری دارد را در کنار هم قرار میدهیم و فراوانی آن ها را جمع میبنیدم و نود پیدا رو در درخت درست میکنیم و بعد دوباره فراوانی نود ها یی که جمع آن ها از همه کمتر است را پیدا میکنم و جمع میزنیم همین کار را تا زمانی که به طور کامل درخت را تشکیل دادیم ادامه میدهیم.
📣👨💻 @AlgorithmDesign_DataStructuer
اولین ویژگی آن این است که آن طوری طراحی شده که هیچ کدی پیشوند کد دیگری نباشد. در مثال بالا یکسری کاراکتر وجود دارد و در زیر هر کدام فراوانی آن نوشته شده این ابتدا دو کاراکتری که فراوانی کمتری دارد را در کنار هم قرار میدهیم و فراوانی آن ها را جمع میبنیدم و نود پیدا رو در درخت درست میکنیم و بعد دوباره فراوانی نود ها یی که جمع آن ها از همه کمتر است را پیدا میکنم و جمع میزنیم همین کار را تا زمانی که به طور کامل درخت را تشکیل دادیم ادامه میدهیم.
📣👨💻 @AlgorithmDesign_DataStructuer
👌2
در یک گراف همبند با n رأس و m یال، وزن یالها 1 یا 2 هستند. بهترین الگـوریتم بـراي یافتن درخت پوشاي کمینه این گراف داراي چه زمان اجرایی است؟
Anonymous Quiz
17%
O(n)
21%
O(m)
55%
O(n log m)
7%
O(log m)
👍2
از الگوریتم های دیگری که میخواهیم در مورد آن صحبت کنیم الگوریتم های مبتنی بر جستجوی آگاهانه می باشند. این الگوریتم ها علاوه بر فرضیات موجود از اطلاعات خاص مسأله بهوه می بند در واقع میتوان گفت به سمت هدف به پیش میروند و بین هدف و غیر هدف تمیایز قاعل میشوند.
مثال هایی از جستجوی آگاهانه :هيوریستيک , جستجوی حریصانه , A* و...
که در مورد هر کدام از موارد ذکر شده صحبت خواهیم کرد.
📣👨💻 @AlgorithmDesign_DataStructuer
مثال هایی از جستجوی آگاهانه :هيوریستيک , جستجوی حریصانه , A* و...
که در مورد هر کدام از موارد ذکر شده صحبت خواهیم کرد.
📣👨💻 @AlgorithmDesign_DataStructuer