زمان کنونی: ۰۸ آذر ۱۴۰۳, ۱۱:۵۰ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

سوالات تخصصی(نرم ,سخت, هوش)-۸۹

ارسال:
۰۹ خرداد ۱۳۸۹, ۰۶:۳۶ ب.ظ (آخرین ویرایش در این ارسال: ۱۰ خرداد ۱۳۸۹ ۰۱:۰۷ ب.ظ، توسط admin.)
سوالات تخصصی(نرم ,سخت, هوش)-۸۹
ضمن تشکر از آقای تنهایی که سبب شدند دانشجویان مشتاق و علاقمند در این فروم گرد بیایند
سوال ۳۴ تخصصی نرم افزار یکی از سوالات مورد بحث است در کارشناسی ارشد علوم کامپیوتر ۸۷ سوال ۸۶ مشابه به این سوال بود ولی ابعاد ماتریس n*n نبود در کتابی که شامل حل سوالات کنکور علوم کامپیوتر تالیف آقای مقسمی بود جواب این مساله n log n ذکر شده بود ولی در کنکور امسال ۲n آمده است دوستان نظری در این رابطه دارند یا نه ؟
تصویر سوال[/url]
۰
۰
یافتن تمامی ارسال‌های این کاربر
 سپاس‌گزاری شده توسط: ali_computer69
ارسال:
۱۰ خرداد ۱۳۸۹, ۱۱:۲۸ ق.ظ
سوالات تخصصی(نرم ,سخت, هوش)-۸۹
این الگوریتم به این صورت هست که ابتدا ستون اول را با توجه با اینکه اعداد مرتب هستند با جستجوی دودویی جستجو کنیم و بعد ستون دوم و ... درنهایت هم ستون nام (البته سطر به سطر هم میشه پیش رفت). از آنجایی که n تا ستون داریم و n بار جستجوی دودویی را اجرا میکنیم پس مرتبه‌ی این الگوریتم nlogn خواهد بود.
حال باید به این فکر کنیم که جستجوهای دودویی در این الگوریتم(که n بار اجرا می شود) هر بار دنبال چه عددی هستند؟ آیا این الگوریتم جواب درست می دهد؟ پاسخ آن خیر است، با این الگوریتم به جواب نمی رسیم.
۰
۰
یافتن تمامی ارسال‌های این کاربر
 سپاس‌گزاری شده توسط: ali_computer69
ارسال:
۱۰ خرداد ۱۳۸۹, ۱۱:۵۸ ق.ظ (آخرین ویرایش در این ارسال: ۱۰ خرداد ۱۳۸۹ ۱۲:۴۷ ب.ظ، توسط mahdieh-Z.)
RE: سوالات تخصصی(نرم ,سخت, هوش)-۸۹
تو گزینه های اعلام شده از طرف سنجش برای این سوال علوم کامپیوتر سال ۸۷ هم همون ۲n اومده و اینکه اگه از این الگوریتم (پایین توضیحش دادم) استفاده بشه به جواب میرسیم(۲n) و اگه از جستجوی دودویی استفاده بشه مرتبه الگوریتم بدتر میشه!

متن الگوریتم هم تو همون علوم کامپیوتر سال ۸۷ اومده بود اینکه در بدترین حالت باید مثلا تا آخر سطر اول بره جلو و بعد بیاد پایین تا آخر سطر آخر... (همون ۲n)
چیزی که از توصیف کلی الگوریتمش یادم مونده استفاده از مرتب بودن هم تو سطر هست هم تو ستون!
شما از اولین خونه از آخرین سطر شروع میکنید(به سمت بالا) و تو این ستون با مقایسه با بعدی اگه x کوچکتر از محتویات اون خونه بود جلو میرید (اگه مساوی بود که پیدا شده) ولی اگه بزگتر بود میریم سراغ ستون بعدی سطر پایین...
 امیدوارم شکل زیر کمک کنه منظورم رو برسونم(عددهایی که دورشون دایرست ترتیب مقایسه‌ها رو نشون میده)

اگه کسی مثال نقض بده برای الگوریتم عالی میشه!


فایل‌(های) پیوست شده


آب را گل نکنیم: شاید این آب روان می رود پای سپیداری، تا فروشوید اندوه دلی...
۰
۰
یافتن تمامی ارسال‌های این کاربر
 سپاس‌گزاری شده توسط: lida , ali_computer69
ارسال:
۱۰ خرداد ۱۳۸۹, ۱۲:۴۲ ب.ظ (آخرین ویرایش در این ارسال: ۱۰ خرداد ۱۳۸۹ ۱۲:۴۷ ب.ظ، توسط mdgh.)
سوالات تخصصی(نرم ,سخت, هوش)-۸۹
الگوریتمی که مرتبه آن ۲n است از جستجوی دودویی استفاده نمی کند.
۰
۰
یافتن تمامی ارسال‌های این کاربر
 سپاس‌گزاری شده توسط: ali_computer69
ارسال:
۱۰ خرداد ۱۳۸۹, ۱۲:۵۲ ب.ظ
سوالات تخصصی(نرم ,سخت, هوش)-۸۹
سلام دوستان
این سوال به نظر من جای هیچ بحثی نداره
با این الگوریتم گزینه ۱ صحیح خواهد بود:
عدد مورد جستجو رو x در نظر میگریم،
جستجو رو از عدد موجود در آخرین سطر ستون اول شروع میکنیم، مقدار x رو با این عدد مقایسه میکنیم، اگه این عدد از x بزرگتر بود، در همون ستون، یک سطر به عقب برمیگردیم، و اگه از x کوچکتر بود، در همون سطر، یک ستون به جلو حرکت میکنیم، در این حالت بدترین حالت ۲n خواهد شد.
زمانی nlogn صحیح خواهد بود که ماتریس یا فقط سطرها مرتبط شده باشن، یا فقط ستون ها، ولی در اینجا هم سطر و هم ستون مرتب شده،
برا فهمش هم میتونید از عکس mahdieh-Z استفاده کنید،
۰
۰
یافتن تمامی ارسال‌های این کاربر
 سپاس‌گزاری شده توسط: ali_computer69


موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  دانلود سوالات تخصصی گرایش فناوری اطلاعات آزمون دکتری ۹۱(کد ۲۳۵۸) Lonely Palm ۲ ۶,۴۶۱ ۲۶ دى ۱۴۰۲ ۰۲:۳۳ ب.ظ
آخرین ارسال: bijibuji
  بررسی سوالات تخصصی دکتری هوش masoomeh_s ۱ ۲,۲۵۷ ۰۱ اسفند ۱۴۰۰ ۰۱:۰۹ ب.ظ
آخرین ارسال: vejdani
  کدام زبان برای هوش مصنوعی بهتر است؟ فرق بین زبان های هوش مصنوعی چیست؟ azam2075 ۳ ۶,۰۷۱ ۱۴ مهر ۱۴۰۰ ۰۷:۲۱ ب.ظ
آخرین ارسال: علیصا
  درخواست جزوه زبان تخصصی دکتر مظفری commasoud ۲۵ ۲۲,۵۴۲ ۱۹ مهر ۱۳۹۹ ۰۳:۰۷ ب.ظ
آخرین ارسال: miss meri
Rainbow ارشد هوش بهشتی یا نرم علم وصنعت aria_irani ۰ ۲,۶۴۷ ۱۴ شهریور ۱۳۹۹ ۰۶:۵۶ ب.ظ
آخرین ارسال: aria_irani
  جواب سوالهای تخصصی دکتری هوش مصنوعی سال ۹۸ Lootus ۱ ۲,۸۲۰ ۲۹ بهمن ۱۳۹۸ ۰۱:۴۳ ب.ظ
آخرین ارسال: machine86
  منابع تخصصی شغل تحلیل گر سیستم Hamedudk ۱ ۳,۲۴۲ ۰۷ آبان ۱۳۹۸ ۰۱:۰۸ ق.ظ
آخرین ارسال: marvelous
  ترجمه تخصصی چه معیار هایی دارد hightrans ۲ ۳,۵۱۶ ۰۴ آبان ۱۳۹۸ ۰۴:۲۶ ب.ظ
آخرین ارسال: marvelous
  معماری روزانه تربیت مدرس (۳۰۶ معماری+۲۷۱ هوش+۳۲۵ نرم)(رتبه اولی) m.1373 ۳ ۵,۰۵۹ ۱۳ مهر ۱۳۹۸ ۱۲:۳۱ ب.ظ
آخرین ارسال: imali
  هوش رباتیک دانشگاه تهران و هوش امیرکبیر s.izadi ۲۹ ۳۱,۰۹۲ ۲۳ تیر ۱۳۹۸ ۰۱:۴۴ ق.ظ
آخرین ارسال: asmagh

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close