فایل شاپ
فروش مقاله،تحقیقات و پروژه های دانشجویی،دانلود مقالات ترجمه شده،پاورپوینتفایل شاپ
فروش مقاله،تحقیقات و پروژه های دانشجویی،دانلود مقالات ترجمه شده،پاورپوینتترکیبات و نظریه های گراف
| دسته بندی | ریاضی |
| بازدید ها | 14 |
| فرمت فایل | doc |
| حجم فایل | 268 کیلو بایت |
| تعداد صفحات فایل | 18 |
ترکیبات و نظریه های گراف
در این مقاله می خواهیم به دو مبحث بزرگ از ریاضیات گسسته با نامهای ترکیبات و نظریه‌ی گراف بپردازیم که در این دوران شاهد پیشرفت چشمگیر آنها می باشیم .
این دو مبحث بدلیل آنکه دارای کاربرد وسیعی در علم کامپیوتر و برنامه سازی های کامپیوتری می‌باشند حائز اهمیت فراوان می باشند .
1-ترکیبات :
شاید در نگاه اول ترکیبات یک بخش معماگونه و سطحی از ریاضیات به نظر برسد که دارای کاربرد چندانی نبوده و فقط مفهوم های انتزاعی را معرفی می کند ولی این شاخه از ریاضیات دارای گستره‌ی وسیع بوده و دارای شاخه های زیادی نیز می باشد .
ابتدا به مسأله ای زیبا از ترکیبات برای آشنا شدن بیشتر با این مبحث ارائه می کنیم .
سوال : یک اتاقی مشبک شده به طول 8 و عرض 8 داریم که خانه‌ی بالا سمت چپ و خانه‌ی پایین سمت راست آن حذف شده است (مانند شکل زیر)
حال ما دو نوع موزاییک داریم . یکی 2*1 ( ) و دیگری 1×2 ( ) سوال این است که آیا می توان این اتاق را با این دو نوع موزائیک فرش کرد .
احتمالاً اگر شخص آشنایی با ترکیبات نداشته باشد می گوید «آری» و سعی می کند با کوشش و
خطا اتاق را فرش کند ولی این کار شدنی نیست ؟! و اثبات جالبی نیز دارد .
اثبات : جدول را بصورت شطرنجی رنگ می کنیم مانند شکل زیر :
حال با کمی دقت متوجه می شویم که هر موزائیک یک خانه از خانه های سیاه و یک خانه از خانه‌های سفید را می پوشاند یعنی اگر قرار باشد که بتوان با استفاده از این موزائیک ها جدول پوشانده شود باید تعداد خانه های سیاه با تعداد خانه های سفید برابر باشد ولی این گونه نیست زیرا تعداد خانه های سفید جدول برابر 32 و تعداد خانه های سیاه برابر 30 می باشد . در نتیجه این کار امکان امکان پذیر نیست .
این مسأله مربوط به مسائل رنگ آمیزی در ترکیبات بوده که دارای دامنه‌ی وسیعی از مسائل دشوار و پیچیده می باشد در زیر چند نمونه از مسائل آسان و سخت را بیان می کنیم .
1-ثابت‌کنید هیچ جدولی را نمی توان به موزائیک هایی به شکل و پوشاند .
(راهنمایی: ثابت کنید حتی سطر اول جدول را هم نمی توان پوشاند)
2-ثابت کنید یک مهره‌ی اسب نمی تواند از یک خانه‌ی دلخواه صفحه‌ی n*4 شروع به حرکت کند و تمام خانه ها را طی کند .
3-یک شبکه‌ی n*m از نقاط داریم یک مسیر فراگیر مسیری است که از خانه‌ی بالا سمت چپ
شروع به حرکت کرده و از همه‌ی خانه هر کدام دقیقاً یک بار عبور کند و به خانه‌ی سمت راست پایین برود ثابت کنید شرط لازم و کافی برای وجود یک مسیر فراگیر در شبکه‌ی n*m آن است که لااقل یکی از m یا n فرد باشد (مرحله‌ی دوم المپیاد کامپیوتر ایران) در شکل زیر یک مسیر فراگیر را برای جدول 5*4 می بینیم .
B
4-ثابت کنید شرط لازم کافی برای پوشش جدول n*m با موزائیک های 2*1 یا 1*2 آن است که یا m یا n زوج باشند .
حال می‌خواهیم یک مبحث مهم از ترکیبات به نام استقراء را معرفی کنیم.
استقراء بعنی رسیدن ازجزء به کل و هم ارز است با اصل خوشترتیبی زیر مجموعه‌ها( اصل خوشتربینی بیان می‌کند که هر مجموعه متناهی از اعداد عضوی به نام کوچکترین عضو دارد).
برای اثبات حکمی به کمک استقراء لازم است:
1) حکم را برای یک پایة دلخواه(که معمولاً کوچک باشد) ثابت کنیم.
2) حکم را برای یک k دلخواه فرض می‌گیریم.
3) به کمک قسمت 2 حکم را برای ثابت می‌کنیم.
بسیاری از گزاره‌ها به کمک این استقراء که در ظاهر ساده است ثابت می‌شود:
یک مثال ساده:
ثابت کنید: .
برای که داریم و حکم برقرار است:
فرض کنیم برای درست باشد حکم را برای ثابت می‌کنیم داریم:
که این قسمت طبق فرض بردار می‌باشد
و برای نیز حکم مسأله برقرار است.
یک مثال سخت:
این سئوال در المپیاد کامپیوتر امسال مطرح شده و ما فقط یک قسمت آنرا بطور خلاصه بیان می‌کنیم.
سئوال: در روز A دارای تعداد مجموعه می‌باشد بطوریکه هیچ مجموعهای زیرمجموعة دیگری نیست یعنی اکر )
حل شایان در روز B می‌آید از روی مجموعه‌های A تمام مجموعه‌هایی را نمی‌سازیم که دارای دو شرط زیر می‌باشند:
1- هر مجموعهای دلخواه در روز B با تمام مجموعه‌ها در روز A اشتراک دارد.
2-اگر از یک مجموعة دلخواه در روز B یک عضو را حذف کنیم آنگاه دیگر شرط 1 برقرار نباشد( که به این شرط، شرط مینیمالی می‌گوئیم:
حال فراز در روز C از روی مجموعه‌های B تمام مجموعه‌هایی با دو شرط بالا را می‌سازد ثابت کنید ( یعنی تمام مجموعه‌های روز اول در روز سوم نیز تولید شده‌اند)
اثبات: ابتدا لم زیر را ثابت می‌کنیم:
لم: به ازای هر مجموعة دلخواه در روز A مثل در روز B n تتا مجموعه وجود دارند بطوریکه هر کدام از آنها دقیقاً یکی از اعضای را دارند( ممکن است اعضای دیگری نیز داشته باشند ولی هر کدام دقیقاً یکی از را دارند.)
اثبات لم: با استقراء روی تعداد مجموعه‌های روز اول حکم را ثابت می‌کنیم. برای یک مجموعه در روز A وضعیت مجموعه‌ها در روزهای C,B,A مشخص شده‌اند:
تحقیق ریاضیات گسسته
| دسته بندی | ریاضی |
| بازدید ها | 27 |
| فرمت فایل | doc |
| حجم فایل | 77 کیلو بایت |
| تعداد صفحات فایل | 29 |
ریاضیات گسسته
مقدمه:
تاریخچه ریاضیات گسسته
پیشرفتهای سریع تکنولوژی در نیمه دوم قرن یبستم به ویژه پیشرفتهای شگفت آور علوم کامپیوتر، مسائل جدید را مطرح کردندکه طرح و حل آنها روشها و نظریه های تازه ای می طلبد. طبیعت متناهی و گسسته بسیاری از این مسائل موجب شده است که روشها و قواعد گوناگون شمارش از اهمیت خاصی بر خوردار شوند. توفیق مفاهیم لازم برای بررسی این مسائل به کار گیری منطق ریاضی و نظریه مجموعه ها را اجتناب ناپذیر ساخته است.
معادلات تفاضلی، روابط بازگشتی، توابع مولد، از دیگراجزایی هستند ک در حل مسائل مورد بحث نقشی اساسی دارند از طرف دیگر هنگام بررسی مسائل مربوط به مدارها، شبکه های حمل و نقل، ارتبا طات بازاریابی و غیره نقش جایگزین ناپذری گرا فها قا طعانه آشکار می شود.
ریاضیات گسسته مقدماتی متنی فشرده برابر یک دوره ریاضیات گسسته در سطحی مقدماتی برای دانشجویان کارشناسی علوم کامپیوتر و ریاضیات است. مولفه های اساسی برنامه کار ریا ضیات گسسته در سطحی مقد ماتی عبارتند از : ترکیبات نظریه گرا فها همراه با کار بردهایی در چند مسئاله استاندارد بهینه سازی شبکه ها، الگوریتمهایی برای حل این مسائل مهم اتحادیه سازندگان ماشینهای محاسبه و مهم کمیته برنامه ریزی یرای کارشناسی ریا ضی بر نقش حیاتی یک دوره درسی روشهای گسسته در سطح کارشناسی که دانشجویان را به حیطه ریاضیات ترکیباتی و ساختارهای جبری و منطقی وارد کند و روی ارتباط متقابل علوم کامپیوتر و ریاضیات تأکید داشته باشد صحه گذاشته اند.
جایگاه و ضرورت آموزش ریاضیات گسسته در نظام جدید دبیرستانی
در جریان تغییر نظام آموزش دوره های کارشناسی ریاضی در سالهای اخیر در دانشگاهها و موسسات آموزش عالی شاهد بودیم که درسهای جدید به تنا سب گرایشهای این رشته جایگزین درسهایی از نظام قبلی شدند. درس ریا ضیات گسسته نیز به ارزش 4 واحد درسی در این راستا بعنوان یکی از واحدهای پایه همه گرایشهای دوره کارشناسی ریاضی در نظر گرفته شده است. در کتابهای درسی ریا ضی نظام جدید دبیرستان نیز شاهد گنجاندن مفاهیم پایه ای مربوط به مباحث مقدماتی ریاضیات گسسته مانند نظریه گراف و دنباله ها و آمار و احتمال و ... می باشیم.
همچنین در دوره پیش دانشگاهی نیز درسی جداگانه تحت عنوان ریاضیات گسسته در نظر گرفته شده است. از آنجا که این شاخه از ریاضی نیاز مند بحث و تبادل نظر از لحاظ آموزشی و تعیین جایگاه و ارتباط آن با سایر شاخه ها و موضوعات ریاضی می باشد.
مطالبی که در این قسمت از بحث طرح خواهد شد بیشتر بر اساس مقاله ای است که تحت عنوان »آموزش ریاضی گسسته در دوره دبیرستان« توسط پروفسور آ.کاتلین
در مجلة بین المللی ریاضیات، علم و تکنولوژی 1990 درج شده است.
» انقلاب کامپیوتری، ریاضیات گسسته را همانند حساب دیفرانسیل و انتگرال برای علم و تکنولوژی ضروری ساخته است.«
محتوای کلی ریاضیات گسسته
محتوای دقیق یک دوره ریاضیات گسسته هنوز تا حدودی به طور مبهم باقیمانده است، زیرا هم کتابهایی که تاکنون در این زمینه به رشته تحریر در آمده و هم برنامه های درسی که در این مورد از سوی برنامه ریزان مباحث درسی ریاضی تهیه وتنظیم می شود، دقیقاَ نتوانسته اند موضوعات و قلمرو مباحث این درس را مشخص نمایند. موضوعاتی از قبیل نظریه اعداد و آمار و احتمالات و جبر خطی آنالیز عددی و مباحسات و برنامه سازیهای کامپیوتری ضمن اینکه در ریاضیات پیوسته جای پای محکمی دارند، در ریاضیات گسسته نیز خودنمایی و شکوفای روز افزون دارند. با این حال می توان گفت که ریاضیات گسسته شامل مباحثی است که مراحل مربوط به تغییرات گسسته و کمیتهای گسسته را توصیف می کند، در مقابل کالکوس که مراحل تغییرات به طور پیوسته را دنبال می کند پس به طور دقیق می توان گفت که ریاضیات گسسته کالکوس( حسابان) نیست.
به طور کلی یک دوره ریاضیات گسسته را می توان شامل عناوین زیر دانست:
منطق راضی و نظریه مجموعه ها ، ساختار های جبری از قبیل مباحث مربوط به گروهها و حلقه ها و میدانها و کواتریونها، شببکه ها جبر یون، نظریه گراف، روشهای ترکیبات و شمارش، نظریه اعداد محاسبات و الگوریتمهای عددی و تجزیه و تحلیل آنها، استقرار و روابط بازگشتی معادلات تفاضلی،آمار و احتمال با فضاهای نمونه ای گسسته.
تفاوت ریاضیات گسسته و حساب دیفرانسیل و انتگرال ( ریاضیات پیوسته)
در اساسی ترین سطح، مدلی برای بیان تفاوت بین ریاضیات گسسته و ریاضیات پیوسته ( یعنی حساب دیفرانسیل و انتگرال و شاخه هایی از آنا لیز که به حساب دیفرانسیل و انتگرال وابسته اند) تفاوت بین اعداد صحیح و اعداد حقیقی است. اعداد حقیقی، پایه همه ریا ضیاتی هستند که مانند حساب دیفرانسیل و انتگرال با خواص توابع پیوسته سر و کار دارند. در حالیکه ریاضیات گسسته بیشتر با توابعی سر و کار دارند که بر مجموعه نقاط گسسته تعریف شده اند( مثل دنباله ها) واز بسیاری جنبه ها به طور کامل با ساختمان پرشکوه آنالیز که بر پایه حساب دیفرانسیل بنا شده است و به طور عمده به توابع پیوسته می پردازد، تفاوت دارد. می دانیم که سیستم های فیزیکی از تعداد زیادی ذرات گسسته – اتمها و مولکولها – تشکیل شده است، در عمل پیوسته فرض کردن ماده فرض بسیار مناسب و دقیقی است. این سبب می شوند که اکثر پدیده ها ی طبیعی سیستمهای فیزیکی که از طریق حساب دیفرانسیل و انتگرال مدل سازی می شوند نوعاَ به صورت معادلات دیفرانسیل درآیند. این عملکرد آنچنان موفقیت شگفت انگیزی داشته است ک نتایج حاصل از آن تقریباَبرای همه مقاصد و اهداف ذاتاَ دقیق اند و موفقیت مهندسی وصنعت در قرنهای اخیر در سراسز دنیا مرهون این مدل سازی زیبا و دقیق و کار بردی ریاضی است، خصوصاَ از زمانی که پیدایش حسابگرهای رقمی و سپس کامپیوترها امکان بررسی و حل عددی معادلات دیفرانسیل و دیگر معادلات را فراهم نمودند. این آغاز شکوفایی آنالیز عددی بود نمونه متعارف از مسائلی که با استفاده از تکنیکهای آنالیز عددی حل می شوند این است که فرمول بندی یک مساله فیزیکی را با استفاده از حساب دیفرانسیل و انتگرال در نظر بگیریم و سپس آن را به شکل گسسته تبدیل کنیم تا با روشهای عددی قابل حل باشد. چنانچه در نمودار سیکلی مدل سازی ریاضی برای مسائل فیزیکی بیان گردید مرحله نهائی این پروژه زمانی قابل استفاده برای مسائل فیزیکی خواهد بود که جواب یا پیش بینی حاصلها از الگوی ریاضی ارزش عملی دانسته باشد و این امر جز به وسیله آنالیز عددی و محاسبات عددی مربوط به آن و تجزیه تحلیل خطاهای وارده و استفادهاز اصل دقت متغیر در روشهای ریاضی امکان پذری ننخواهد بود. از طزفی نیاز به ریاضیات گسسته، محدود به آنالیز عددی میشد نمی توانستیم ادعا کنیم که چنین ریاضیاتی نقش مقایسه کردنی با حساب دیفرانسیل و انتگرال دارد. آنالیز عددی با وجود کار بردهای وسیع، آن موضوعی تخصصی است نمی تواند تأثیر چشمکیری بر روند دآموزشی ریاضیات بگذارد هر چند آنالیز عددی مهمترین محل تلاقی ریاضیات پیوسته گسسته است امروزه تنها یک جزء کوچک از کار بردهای ریاضیات گسسته را در‌بر‌می‌گیرد.
فهرست مطالب
- مقدمه
- جایگاه و ضرورت آموزش ریاضیات گسسته در نظام جدید دبیرستان 2
- محتوای کلی ریا ضیات گسسته 3
- تفاوت ریاضیات گسسته و حساب دیفرانسیل و ا نتگرال 4
- مرور تاریخی مباحث مهم ریاضیات گسسته 8
- مفهوم جاگشت 8
- اولین فن حدس زدن 8
- دیریکله 9
- تاریخچه اصل شمول و عدم شمول 9
- نظریه گراف 10
- مسئله پل کونیگسبرگ 10
- طریقه نمایش گراف 11
- گراف هامیلتونی 12
- رابطه های بازگشتی و مبادلات تفاضلی 19
- نمودار ترسیمی روشها و مدلهای گسسته و پیوسته ریاضی 25
- منابع 28
نامعادلات و نسبت های مثلثاتی
| دسته بندی | ریاضی |
| بازدید ها | 27 |
| فرمت فایل | doc |
| حجم فایل | 196 کیلو بایت |
| تعداد صفحات فایل | 28 |
نامعادلات و نسبت های مثلثاتی
نماد علمی:
نماد علمی مدلی جدید برای عدد نویسی است که از آن برای سهولت بخشیدن به امر نوشتن و خواندن اعداد بسیار بزرگ و یا بسیار کوچک مانند محاسبة جرم سیارات و یا یک اتم از عنصر، استفاده می کنند.
نماد علمی اعداد مثبت را به صورت می نویسند که در آن K عددی است اعشاری بین یک و ده و n نیز عددی صحیح است.
مثال: اعداد زیر را به صورت نماد علمی بنویسد.
(الف (ب
نامعادله:
اگر یک نامساوی شامل متغیر باشد به آن نامعادله گفته می شود.
روش حل نامعادله:
حل نامعادله از بسیاری جهات شبیه حل معادله می باشد، ولیکن با این تفاوت که در حل نامعادله برای مجهول محدوده ای به عنوان پاسخ (جواب) بدست می آید و در معادله یک مقدار مشخص و معینی برای مجهول حاصل می گردد.
:مثال
قوانین و نکات مهم در مورد نامساوی
1-به طرفین یک نامساوی می توان عددی را اضافه و یا کم نمود.
2-می توان طرفین یک نامساوی را در عددی مثبت ضرب یا بر آن تقسیم کرد.
3-اگر طرفین یک نامساوی را در یک عدد منفی ضرب (تقسیم) کنیم جهت نامساوی عوض می شود.
4-اگر طرفین یک نامساوی هم علامت باشند (مثبت یا منفی باشند) و طرفین را عکس کنیم. جهت نامساوی عوض می شود.
حل نامعادلات کسری:
برای حل نامعادلات کسری مانند معادلات گویا عمل می کنیم. یعنی دو طرف نامعادله را در کوچکترین مضرب مشترک مخرجها ضرب می نمائیم تا نامعادله از حالت کسری به خطی درآید.
نامعادلات توأم: این گونه نامعادلات یا بصورت دو نامعادله مجزا می شوند و یا اینکه ما باید آنها را به صورت دو نامعادله مجزا درآوریم. و روش حل آن بدین صورت است که هرکدام از نامعادلات را حل نموده و در نهایت بعد از بدست آوردن پاسخ آنها، اشتراک جوابهای آن دو را به عنوان جواب یا پاسخ اصلی بیان می کنیم.
مثال: نامعادلات توأم زیر را حل نمائید.
مثلثات
درجه (D): اگر یک دایره را به 360 قسمت مساوی تقسیم کنیم؛ به هر قسمت یک درجه گویند.
گراد (G): اگر یک دایره را به 400 قسمت مساوی تقسیم کنیم؛ به هر قسمت یک گراد گویند.
رادیان (R): یک رادیان زاویه ای است که کمان مقابل به آن برابر شعاع دایره باشد. یعنی هر دایره رادیان است.
رابطة مقابل برقرار است
مثال 1:
100 گراد چند درجه و چند رادیان است؟
مثال 2:
مقدار زاویه ای را بر حسب رادیان بیابید که اگر به اندازه اش بر حسب درجه 15 واحد اضافه شود اندازة آن برحسب گراد بدست آید.
نسبتهای مثلثاتی:
برای بدست آوردن نسبتهای مثلثاتی، یک زاویه را با جهت مثبت محور xها درنظر می گیریم. و آنها را به صورت پائین تعریف می کنیم. «باید توجه داشت که نقطه A نقطه یا اختیاری برروی ضلع زاویه است و طول پاره خط OA برابر r فرض شده که همواره مثبت است»: