سوال ۱۱۲ میشه [tex]O(n k \lg k)[/tex]
شما فاصله ها رو حساب میکنی، بعد عدد K ام رو بدست میاری، بعد یه پارتیشن حول عدد K ام اعمال میکنی و اون k عدد سمت چبش رو سورت میکنی با مرتبه Klgk

سوال۱۱۱

این غیر ممکنه طبق یه قضیه تو گراف که تعداد رئوس با درجه فرد زوج هست.

کمترین تعداد مقایسه برای مرتب سازی ۶ عدد میشه ۱۰ تا [tex]\left \lceil \lg6! \right \rceil = 10[/tex]

گزینه ۳ اگه VE باشه درسته که همون الگوریتم بلمن فورد هستش.

سلام میدونم جواب به این سوال داده شده ولی من می خواهم یه خورده مفصل تر توضیحشو بدم که توضیح دکتر یوسفیم هست چون توضیح قشنگی هست می نویسم: (البته می خواهم واسه خودمم با نوشتن در اینجا یه ریویو بشه!)
سوال ۱۱۲ رو که مثلشو پارسال هم داده بودن,این مساله رو با پیدا کردن kامین کوچکترین می توان انجام داد بعد این به ترتیب فاصله هاشون sort هم می خواهد پس می شه گزینه سه پیدا کردن k امین کوچکترین با مرتبه n و sort کردن با مرتبه klogk
پارسال رادیکال n امی رو خواسته بودن ولی امسال کاملشو خواستن!
n تا نقطه در صفحه داریم بعد از این k تا نقطه ای که به مبدا نزدیک هستنو بر اساس فاصله هاشون به دست بیاریم!
خوب باید اول تک تک نقاط رو فاصله هاشونو تا مبدا پیدا کنیم فاصله نقطه (x,y) تا مبدا چقدره؟
رادیکال x^2+y^2ولی به هر حال مهم نیست و مهم اینه که فاصله یافتن مرتبش ۱ هست!شما یه نقطه رو بخواهی تا مرکز فاصلشو بگیری با مرتبه ۱ می شه و این فرموله بعد این فاصله ها رو در یک آرایه می ریزیم!پس تک تک نقاط رو فاصله ها رو تا مبدا با این فرموله گرفته و می ریزیم در آرایه پس الان در آرایه n تا عنصر هست و n تا هم زحمت کشیدیم!چون n تا نقطه رو فاصله گرفتیم!بعد این آرایه n عنصری که الان داخلش آرایه هاست رو میایید k امین کوچکترینشو به دست میارید و partition می کنید که اینم هزینش تتا n که با این کار آرایه k تا کوچک ها میان اول آرایه ولی نکته مهمی که گفته شده و باید بهش توجه بشه و اگه توجه نشه تست منفی زده می شه:گفته به ترتیب فاصله هایشان این الان sort می خواهد که بر اساس k عنصر میشه k log k و اگر sort در کار نبود می شد n!یعنی :
n+klogk

و حالا سوال ۱۱۳:
جمله اولش:هیچ گرافی وجود نداره که تعداد گره های فردش فرد باشه,گره های فرد همیشه تعدادشون زوج است(این اصل اول گراف است)
جمله دومش:nعنصر کم کم در بدترین حالت logn! مقایسه می خواهد!یعنی گسی نمی تونه کمتر از این مرتبه عمل مقایسه و sort رو انجام بده!و به ازای n=6 سقفش میشه ۷۲۰ بین ۹ و ۱۰ میشه ۱۰!
جمله سوم:چند تا فرمول خیلی مهمی که دکتر یوسفی در این مورد گفتنو می نویسم:اول جمله سوم درست است!
کوهتاترین مسیرهای هم مبدا یا single source
BFS در گراف های بدون وزن یا وزن یکسان کار می کند: (n+e) لیست و n^2 ماتریس
درِDAG و با BFS این کارو می توان انجام داد: (با هر وزنی مثبت یا منفی) : (n+e) لیست و n^2 ماتریس
DAG( یعنی گراف جهت دار بدون سیکل)
بلمن فورد هم هر وزنی رو جواب می دهد: (ne) لیست و n^3 ماتریس
دایجسترا هم فقط وزن مثبت رو جواب می دهد: (eloge) لیست و n^2 ماتریس


موفق باشید.....

الان دوستان میدونن و جواب نمیدن، یا هیشکی نمیدونه؟

ممنونم
اما در مورد سوال ۱۱۲ سوالم اینه که چرا گزینه ی چهار نشد؟

و در مورد سوال ۱۱۳ موارد ب و ج چی میشه پس؟

خب یه سوال دیگه
مدیونین اگه بخندین ا
اون k جلوی لگاریتم یعنی چی؟ چرا n نیست؟

(۰۷ بهمن ۱۳۹۲ ۰۸:۰۶ ب.ظ)m-behdad نوشته شده توسط:  خب یه سوال دیگه
مدیونین اگه بخندین ا
اون k جلوی لگاریتم یعنی چی؟ چرا n نیست؟

خب وقتی شما K تا عدد رو مرتب میکنی مرتبش میشه klgk

(دوست من سوال پرسیدن عیب نیست! بلکه با همین سوال پرسیدن هاست که آدم یه چیزی میفهمه!)

(۰۷ بهمن ۱۳۹۲ ۰۸:۱۷ ب.ظ)Riemann نوشته شده توسط:  

(07 بهمن ۱۳۹۲ ۰۸:۰۶ ب.ظ)m-behdad نوشته شده توسط:  خب یه سوال دیگه
مدیونین اگه بخندین ا
اون k جلوی لگاریتم یعنی چی؟ چرا n نیست؟

خب وقتی شما K تا عدد رو مرتب میکنی مرتبش میشه klgk

(دوست من سوال پرسیدن عیب نیست! بلکه با همین سوال پرسیدن هاست که آدم یه چیزی میفهمه!)

اینجا که دکمه ی تشکرش غیب شده
مرسی دوست خوبم

بچه ها چرا توی سوال ۱۱۳ پارسه گفته مورد سوم درسته؟ مگه این زمانش ne نمیشه؟
تو رو خدا یکی اینو جواب بده!!

(۱۴ بهمن ۱۳۹۲ ۰۱:۳۱ ق.ظ)zahra412 نوشته شده توسط:  بچه ها چرا توی سوال ۱۱۳ پارسه گفته مورد سوم درسته؟ مگه این زمانش ne نمیشه؟
تو رو خدا یکی اینو جواب بده!!

دوست من گراف جهت دار وزن دار بدون دور یعنی همون dag
dag هست خاطرت که کوتاهترین مسیرا توش از مرتبه ان بعلاوه ای هست

(۱۴ بهمن ۱۳۹۲ ۰۸:۱۱ ب.ظ)atharrashno نوشته شده توسط:  

(14 بهمن ۱۳۹۲ ۰۱:۳۱ ق.ظ)zahra412 نوشته شده توسط:  بچه ها چرا توی سوال ۱۱۳ پارسه گفته مورد سوم درسته؟ مگه این زمانش ne نمیشه؟
تو رو خدا یکی اینو جواب بده!!

دوست من گراف جهت دار وزن دار بدون دور یعنی همون dag
dag هست خاطرت که کوتاهترین مسیرا توش از مرتبه ان بعلاوه ای هست

مرسی دوستم
فقط نخند اگه بپرسم مگه dag وزن داره؟ من همش فکر میکنم ندارره که.....؟؟؟؟ اینم ج بده مرسی

نمیخندم دوست من
دگ وزن داره خیلی هم وزنش قشنگه!
اگر گراف وزن نداشت همین سوال را از بی اف اس مشد حل کرد

(۱۶ بهمن ۱۳۹۲ ۰۲:۳۱ ب.ظ)atharrashno نوشته شده توسط:  دگ وزن داره خیلی هم وزنش قشنگه!
اگر گراف وزن نداشت همین سوال را از بی اف اس مشد حل کرد

مرسی لطف کردی
"آیتم تشکر غیب شده بود "