30 آبان 1389, 09:05 ب.ظ
صفحهها: 1 2
10 آذر 1389, 09:39 ب.ظ
ادغام 2 هیپ که جمعاً n عنصر دارد از مرتبه(O(n هست.
12 آذر 1389, 02:35 ب.ظ
به یاد داشته باشید که پیمایش های BFS , DFS منحصر بفرد نیستند.
18 آذر 1389, 10:11 ب.ظ
(10 آذر 1389 09:39 ب.ظ)Masoud05 نوشته شده توسط: [ -> ]ادغام 2 هیپ که جمعاً n عنصر دارد از مرتبه(O(n هست.
لطفاَ به لینک زیر یه نگاهی بندازین:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
توجه: این فایل زبان اصلیه اما ترجمه اون خیلی راحته . حجمش هم حدوداً 88 کیلو بایته
01 دى 1389, 02:38 ب.ظ
ادغام دو هیپ نا متوازن را می توان درLgn انجام داد.
02 دى 1389, 02:46 ب.ظ
یک آرایه نزولی یک هیپ است ولی عکس آن لزوماً صحیح نیست.
علت (از خودم): در آرایه نزولی، به ازای هر i<j مقدار درون خانه i از j بزرگتر است پس لزوماً والد گره i که اندیسی کوچکتر از i دارد( چراکه در سطح بالاتری از درخت نسبت به گره i قرار گرفته )
باید مقدارش بزرگتر از i باشد. اما یک هیپ لزوماً یک آرایه نزولی نیست چراکه فرض کنید در سطح 2( بعد از ریشه، ریشه سطح1 فرض شده )کافی است مقادیر کوچکتر از ریشه باشد و قیدی نداریم که فرزند راست نسبت به فرزند چپ مقدارش کمتر یا بیشتر باشد، پس ممکن است مقدار زیر درخت چپ از راست بزرگتر باشد که باعث میگردد هنگام نمایش در آرایه مقدار درون اندیس i+1 از مقدار درون اندیس i بزرگتر باشد( نزولی نیست)
نکته بالا برای MaxHeap بود اما برای MinHeap هم وضیعتی به همین صورت داریم فقط با این تفاوت که آرایه صعودی است.
علت (از خودم): در آرایه نزولی، به ازای هر i<j مقدار درون خانه i از j بزرگتر است پس لزوماً والد گره i که اندیسی کوچکتر از i دارد( چراکه در سطح بالاتری از درخت نسبت به گره i قرار گرفته )
باید مقدارش بزرگتر از i باشد. اما یک هیپ لزوماً یک آرایه نزولی نیست چراکه فرض کنید در سطح 2( بعد از ریشه، ریشه سطح1 فرض شده )کافی است مقادیر کوچکتر از ریشه باشد و قیدی نداریم که فرزند راست نسبت به فرزند چپ مقدارش کمتر یا بیشتر باشد، پس ممکن است مقدار زیر درخت چپ از راست بزرگتر باشد که باعث میگردد هنگام نمایش در آرایه مقدار درون اندیس i+1 از مقدار درون اندیس i بزرگتر باشد( نزولی نیست)
نکته بالا برای MaxHeap بود اما برای MinHeap هم وضیعتی به همین صورت داریم فقط با این تفاوت که آرایه صعودی است.
06 دى 1389, 11:54 ب.ظ
ساخت هیپ از مرتبه (O(n می باشد( به روش پایین به بالا)
از هیپ برای مرتب سازی عناصر به نحو زیر استفاده می شود
1- بسته به نوع مرتب سازی یک هیپ می سازیم که به زمان( O(n نیاز دارد . در واقع برای مرتب سازی صعودی یک هرم کمینه و برای مرتب سازی نزولی یک هرم بیشینه می سازیم.
2- n عنصر را به ترتیب از هیپ حذف می کنیم که به زمان nlogn نیاز دارد
پس مرتبه کل بصورت( O(nlognمی باشد( جمع 2 عمل بالا)
از هیپ برای مرتب سازی عناصر به نحو زیر استفاده می شود
1- بسته به نوع مرتب سازی یک هیپ می سازیم که به زمان( O(n نیاز دارد . در واقع برای مرتب سازی صعودی یک هرم کمینه و برای مرتب سازی نزولی یک هرم بیشینه می سازیم.
2- n عنصر را به ترتیب از هیپ حذف می کنیم که به زمان nlogn نیاز دارد
پس مرتبه کل بصورت( O(nlognمی باشد( جمع 2 عمل بالا)
07 دى 1389, 12:03 ق.ظ
نکات زیر در مورد Heap در واقع تمرینات بخش 6.1 CLRS هست:
1. مینیمم تعداد گرهها در یک heap به ارتفاع h برابر است با
2. ماکزیمم تعداد گرهها در یک heap به ارتفاع h برابر است با
3. در یک Max-Heap کوچکترین عنصر همیشه یک برگ است.
4. در یک آرایهی heap که n عنصر دارد، برگها در اندیس های n/2 به بعد آرایه قرار دارند، یعنی اندیس برگها عبارت است از
1. مینیمم تعداد گرهها در یک heap به ارتفاع h برابر است با
2. ماکزیمم تعداد گرهها در یک heap به ارتفاع h برابر است با
3. در یک Max-Heap کوچکترین عنصر همیشه یک برگ است.
4. در یک آرایهی heap که n عنصر دارد، برگها در اندیس های n/2 به بعد آرایه قرار دارند، یعنی اندیس برگها عبارت است از
07 دى 1389, 12:04 ق.ظ
نکته مهم ولی ساده از min-heap برای استخراج متوالی minها , از max heap برای استخراج متوالی maxها استفاده میشود و heap در امر جستجو کارایی ندارد!
07 دى 1389, 12:12 ق.ظ
(07 دى 1389 12:04 ق.ظ)afagh1389 نوشته شده توسط: [ -> ]نکته مهم ولی ساده از min-heap برای استخراج متوالی minها , از max heap برای استخراج متوالی maxها استفاده میشود و heap در امر جستجو کارایی ندارد!خود هیپ به تنهایی معنی نداره، در واقع هرگاه اسم هیپ میاد منظور یکی از این 2 حالت بیشینه و یا کمینه هست . برای مرتب سازی هم در ارسال 7 توضیح داده شده
در ضمن اگه مشخص نباشه نوع هیپ چیه معمولاً منظور هیپ بیشینه است اما در مسائلی مثل صف اولویت و یا ادغام لیست های مرتب منظور هیپ کمینه است
07 دى 1389, 11:30 ب.ظ
تمرین 12.5.3 CLRS:
عمل حذف در BST جابه جایی پذیر نیست.
عمل حذف در BST جابه جایی پذیر نیست.
07 دى 1389, 11:39 ب.ظ
(07 دى 1389 11:30 ب.ظ)sepid نوشته شده توسط: [ -> ]تمرین 12.5.3 CLRS:عمل درج نیز جا به جایی پذیر نیست . دقیقاً به همین علته که ارتفاع درخت BST بین log n و n هست
عمل حذف در BST جابه جایی پذیر نیست.
اما در Treap عمل درج و حذف جابه جا پذیره چراکه با هر نوع جایگشت از ورودیها درخت حاصل شکل منحصر بفردی دارد.
02 اردیبهشت 1391, 02:04 ق.ظ
گراف دوبخشی
گرافهای دوبخشی به گرافهایی گفته میشوند که رأسها به دو دسته مجزا قابل افراز هستند
بگونهای که تمامی یالهای گراف بین گرههای بین دو دسته مختلف باشند.
مثالی از یک گراف دو بخشی
خواص مهم
یک گراف دو بخشی است اگر و فقط اگر تمامی دورهای از طول زوج باشند.
بنابراین به عنوان مثال یک گراف دو بخشی نمیتواند شامل یک گراف کامل با ۳ رأس باشد.
یک گراف دو بخشی است اگر و فقط اگر ۲-رنگ پذیر باشد.
گراف پترسن
گراف پترسن یک گراف بدون جهت با ۱۰ رأس و ۱۵ یال است. گرافی کوچک که مثال و مثال نقض مفیدی برای خیلی از مسائل در نظریه گراف است. این گراف به جولیوس پترسن نسبت داده شده ولی در حقیقت برای اولین بار ، ۱۲ سال زودتر در سال ۱۸۸۶ به وجود آمده بود.
تعداد رأسها:۱۰ تعداد یالها: ۱۵ قطر:۲ مینیمم طول دور:۵
عدد رنگی:۳ اندیس رنگی:۴ منتظم غیرمسطح
گراف پترسن، گراف مکمل گراف خط است. همچنین گراف کنزر است به این معنا که اگر برای هر کدام از زیرمجموعههای دو عضوی یک مجموعهٔ ۵ عضوی یک رأس در نظر بگیریم و بین هر دو رأسی که زیرمجموعهها ی نظیرشان ناسازگار باشند یک یال وصل کنیم، گراف پترسن ساخته میشود.
گراف پترسن هم با گراف کامل و هم با گراف دوبخشی کامل همومورف است.
مسیرها و دورهای همیلتونی
گراف پترسن مسیر هامیلتونی دارد ولی دور هامیلتونی ندارد. گراف پترسن کوچکترین گراف شبه هامیلتونی است یعنی اگرچه دور هامیلتونی ندارد، هر کدام از رأسهایش که حذف شوند میتوان یک دور هامیلتونی در آن پیدا کرد.
عدد تقاطع گراف پترسن ۲ است .
گراف پترسن همچنین میتواند در صفحه به گونهای رسم شود که همهٔ یالها طول یکسان برابر واحد داشته باشند.[شکل ۳]
نامگذاری به نام:*******عدد تقاطع گراف**گراف پترسن در صفحه******* گراف پترسن شبه ****** عدد رنگی گراف
جولیوس پترسن*******پترسن ۲ است**میتواند به گونهای رسم****** هامیلتونی است ****** پترسن ۳ است
******************************شود که طول هر
****************************** یال برابر واحد باشد
منبع :به نظر قبلا از ویکی پدیا گرفتم
گرافهای دوبخشی به گرافهایی گفته میشوند که رأسها به دو دسته مجزا قابل افراز هستند
بگونهای که تمامی یالهای گراف بین گرههای بین دو دسته مختلف باشند.
مثالی از یک گراف دو بخشی
خواص مهم
یک گراف دو بخشی است اگر و فقط اگر تمامی دورهای از طول زوج باشند.
بنابراین به عنوان مثال یک گراف دو بخشی نمیتواند شامل یک گراف کامل با ۳ رأس باشد.
یک گراف دو بخشی است اگر و فقط اگر ۲-رنگ پذیر باشد.
گراف پترسن
گراف پترسن یک گراف بدون جهت با ۱۰ رأس و ۱۵ یال است. گرافی کوچک که مثال و مثال نقض مفیدی برای خیلی از مسائل در نظریه گراف است. این گراف به جولیوس پترسن نسبت داده شده ولی در حقیقت برای اولین بار ، ۱۲ سال زودتر در سال ۱۸۸۶ به وجود آمده بود.
تعداد رأسها:۱۰ تعداد یالها: ۱۵ قطر:۲ مینیمم طول دور:۵
عدد رنگی:۳ اندیس رنگی:۴ منتظم غیرمسطح
گراف پترسن، گراف مکمل گراف خط است. همچنین گراف کنزر است به این معنا که اگر برای هر کدام از زیرمجموعههای دو عضوی یک مجموعهٔ ۵ عضوی یک رأس در نظر بگیریم و بین هر دو رأسی که زیرمجموعهها ی نظیرشان ناسازگار باشند یک یال وصل کنیم، گراف پترسن ساخته میشود.
گراف پترسن هم با گراف کامل و هم با گراف دوبخشی کامل همومورف است.
مسیرها و دورهای همیلتونی
گراف پترسن مسیر هامیلتونی دارد ولی دور هامیلتونی ندارد. گراف پترسن کوچکترین گراف شبه هامیلتونی است یعنی اگرچه دور هامیلتونی ندارد، هر کدام از رأسهایش که حذف شوند میتوان یک دور هامیلتونی در آن پیدا کرد.
عدد تقاطع گراف پترسن ۲ است .
گراف پترسن همچنین میتواند در صفحه به گونهای رسم شود که همهٔ یالها طول یکسان برابر واحد داشته باشند.[شکل ۳]
نامگذاری به نام:*******عدد تقاطع گراف**گراف پترسن در صفحه******* گراف پترسن شبه ****** عدد رنگی گراف
جولیوس پترسن*******پترسن ۲ است**میتواند به گونهای رسم****** هامیلتونی است ****** پترسن ۳ است
******************************شود که طول هر
****************************** یال برابر واحد باشد
منبع :به نظر قبلا از ویکی پدیا گرفتم
03 اردیبهشت 1391, 01:58 ق.ظ
این مطلب در مورد پیمایش گراف هاست .
04 اردیبهشت 1391, 05:48 ق.ظ
درخت های جست و جوی دودویی ( BST = Binary Search Tree )
یک درخت جستجوی یک درخت دودویی است که ممکن است تهی باشد. اگر درخت تهی نباشد خصوصیات زیر را برآورده می کند :
- هر عنصر دارای یک کلید است و دو عنصر نباید دارای کلید یکسان باشند ، در واقع کلیدها منحصر به فردند.
- کلیدهای واقع در زیردرخت غیرتهی چپ باید کمتر از مقدار کلید واقع در ریشه زیردرخت راست باشد.
- کلیدهای واقع در زیردرخت غیرتهی راست باید بزرگتر از مقدار کلید واقع در ریشه زیردرخت چپ باشد.
- یک درخت جستجوی یک درخت دودویی است که ممکن است تهی باشد. اگر درخت تهی نباشد خصوصیات زیر را برآورده می کند :
- زیردرختان چپ و راست نیز خود درختان جستجوی دودویی میباشند.
جستجوی یک درخت دودویی
- فرض کنید خواسته باشیم دنبال عنصری با کلید key بگردیم. ابتدا از ریشه (root) شروع می کنیم ، اگر ریشه تهی باشد ، درخت جستجو فاقد هر عنصری بوده و جستجو ناموفق خواهد بود. در غیر این صورت keyرا با با مقدار کلید ریشه مقایسه کرده
- اگر key کمتر از مقدار کلید ریشه باشد ، هیچ عنصری در زیردرخت راست وجود ندارد که دارای کلیدی برابر key باشد ، بنابراین زیردرخت چپ ریشه را جستجو می کنیم.
- اگر key بزرگتر از مقدار کلید ریشه باشد ، زیردرخت راست را جستجو می کنیم.
درج عنصری به داخل درخت جستجوی دودویی
برای درج عنصر جدیدی به نام key ، ابتدا باید مشخص نمود که آیا کلید با عناصر موجود متفاوت است یا خیر. برای انجام این کار باید درخت را جستجو کرد، اگرجستجو ناموفق باشد ، عنصر را در محلی که جستجو خاتمه پیدا نموده است ، درج می کنیم.
زمان لازم برای جستجوی num در یک درخت برابر (O(h می باشد به نحوی که h برابر با عمق یا ارتفاع درخت است. بقیه الگوریتم نیاز به زمان (Θ(۱ دارد. بنابراین زمان کل مورد نیاز insert_node برابر با (Θ(h می باشد.
زمانی که یک گره برگ با دو فرزند حذف می شوند ، گره را با بزرگترین عنصر در زیر درخت چپ و یا کوچکترین عنصر در زیردرخت راست آن گره جایگزین و تعویض کرد.
عمل حذف در زمان (O(h انجام می گیرد ، به نحوی که h عمق درخت می باشد.
****** درختان جستجو با بیشترین عمق ، درختان جستجوی متعادل نامیده می شوند.
****** درختان جستجوی متعادلی وجود دارند که عمل جستجو ، درج و حذف را در زمان (O(h ممکن می سازند
از جمله درختان red_black ، ۲-۳ ، AVL
نقل قول: جستجوی کلید در درخت دودویی
کد:
void search ( node _ pointer tree ,
keytype keyin,
node _ poiner & p)
{
bool found ;
p = tree;
found = false;
while (! found)
if ( p - > key == keyin )
found = true ;
else if ( keyin < p - > key )
p = p -> left ;
else
p = p - > right ;
}
نقل قول: تعیین یک درخت جست وجوی بهینه برای مجموعه ای از کلید ها، هر یک با احتمالی مشخص
کد:
void optsearchtree ( int n ,
const float p[];
float & minavg,
index R[][])
{
index i , j , k , diagonal ;
float A [1..n + 1] [0..n];
for ( i = 1 ; i ≤ n ; i ++) {
A [i] [i -1] = 0
A [i] [i] = p [i];
R [i] [i] = i ;
R [i] [ i – ۱ ] = ۰;
}
A[ n + 1 ] [n] = 0 ;
R[ n + 1 ] [n] = 0 ;
for (diagonal = 1;diagonal ≤ n – ۱; diagonal++)
for ( i = 1; i ≤ n – diagonal ; i ++) {
j = i + diagonal ;
A[i][j] = minimum(A[i][k-1]+A[k+1][j])+∑pm
R[i][j] = a value of k that gave the minimum;
}
minavg = A [1][n];
}
نقل قول: ساخت درخت جست و جوی دودویی بهینه
کد:
node _ pointer tree ( index i , j )
{
index k ;
node _ pointer p ;
k = R [i] [j];
if ( k == 0 )
return NULL;
else {
p = new nodetype ;
p - > key = key [k] ;
p - > left = tree (i , k – 1);
p - > right = tree ( k+1 , j);
return P;
}
}
صفحهها: 1 2