11-Дәріс. Тақырып: Комбинаторика элементтері
жүктеу/скачать 60.65 Kb.
|
1 2
11-Дәріс.Тақырып Комбинаторика элементтері|
11-Дәріс.Тақырып: Комбинаторика элементтері Мақсаты: Комбинаторика элементтерімен қосу, көбейту және амалдарды орындаумен танысу Жоспар:1.Қосу, көбейту ережелері.Орналастыру және теру. 2.Орналастыру және функционалдық бейнелер.Алмастыру және теру. 3.Қосылу мен шығару формулалары. Бернулли теоремасы Комбинаторика 17 ғасырда Кардано, Паскаль, Галилео, Ферма, Лейбниц, Бернулли сияқты ғалымдардың еңбектерінің арқасында пайда болды деп есептеледі. Олар нақты терминдерді енгізді бұл ғылым үшін және бірқатар іргелі заңдар мен комбинаториканың алғашқы формулаларын дәлелдеді. Мысалы, Бернулли теоремасы, ол тек бір-бірінен тәуелсіз және бірдей шарттарда кез келген рет қайталануы мүмкін кездейсоқ тәжірибелер мен тәжірибелерді қарастырған жөн. Бұл теорема комбинаторика мен ықтималдықтар теориясының ғылым ретінде одан әрі дамуын анықтады деп жалпы қабылданған. Жиілік тұрақтылығы Комбинаторика элементтерін зерттеуге көшпес бұрын, белгілі бір ойларды ұсынатын нақты мысал келтірейік – сүйек лақтыру. Қарапайымдылық үшін бір сүйекті қарастырайық. Бұл алты қырлы текше, оның әр жағы нөмірленген. Егер біз n лақтырылатын тәжірибелер қатарын жүргізсек және Г1 – 1 саны бар жиектің тамшыларының саны деп есептесек, Г2 - 2 санымен және т.б. лақтыру санының ұлғаюымен n жиілігі Г1/n, Г2 /n, …, Г 6/n, эксперимент басында кездейсоқ болып көрінетін, әбден белгілі мәндерге ие болады. Жақсы теңдестірілген сүйек үшін әр қырының жиілігі үлкен дәлдікпен бірдей болады. Тағы бір мысал – монета тәжірибесі. Сонымен, ғалым Пирсон 24 000 тиын лақтыруды жүргізгеннен кейін монеталардың бір жағының құлау жиілігі 0,5-ке жақындаған сайын, соғұрлым дәлірек лақтырылады деген қорытындыға келді. Осылайша ол елтаңбаның жоғалуы үшін 0,5005 ықтималдық алды. Бұл принципжиілік тұрақтылығы да теорияның негіздерінің бірі болып табылады. Тарихи жазба Ықтималдықтар теориясы мен комбинаторика 20 ғасырда ең белсенді түрде дамыды. Бұл мәселеге орыс және кеңес математиктері үлкен үлес қосты. Олардың ішінде, мысалы, Колмогоров, Чебышев, Ляпунов, Марков. Олар қолдану аясын едәуір кеңейтті, үлкен сандар заңын, орталық шек теоремасын, ықтималдықтар теориясының аксиоматикасын зерттеді және сипаттады. Мұның бәрі тұтас бір ғылымға негіз болды. Бүгінгі таңда физика, химия, биология және басқа да көптеген салаларда, әсіресе олардың практикалық саласында комбинаторика мен ықтималдықтар теориясы элементтерінің маңыздылығын асыра бағалау қиын. Комбинаторика элементтері Әдете комбинаторлық деп берілген элементтерден немесе екі шектеулі жиын арасындағы қандай да бір бейнелеулердің санынан құрылуын мүмкін болатын шектеулі жиындардың немесе белгілі бір қасиеті бар кортеждердің (әртүрлі комбинациялардың) саны табуға арналған есепті айтады. Мысалы: топта 30 студен бар осы топтан жарысқа қатынасын 3 студентті қанша тәсілмен іріктеп алуға болады. Жалпы кез –келген комбинаторлық есепті шектеулі жиындар және оларды бейнелеулер жайындағы есепке келттіруге болады, сондықтан камбинаториканы (шектеулі жиындарға амалдар қолдану жиындарды реттеу және жиындарды бөлу, элементердің жиынды орналасу реті және жиын элементерін қандайда бір тәртіп бойынша орналастыру тәсілдерінің санын анықтау сияқты мәселелерді зерттейтіндіктен) жиындар теорисяның бөлігі деп қарастыруға болады. Көптеген комбинаторлық есептерді шешу қосынды және көбейтінді ережелері деп аталатын қарапайым екі ережеге негізделген . Қосынды ережесі екі немесе одан көп шектеулі жиындардың бірігуі элементердің санын, ал көбейтінді ержесі олардың декарттық көбейтіндісі элеменнтерінің санын табуға көмек береді. Бірнеше шектеулі жиындардың бірігу жиыны элементердің санын табу мәселесі де осыған ұқсас қарастырылады. Комбинаторикада көбейтінді ережесін былай тұжырымдайды: “Егер х элементін к тәсілмен, ал у элементті m тәсілменн таңдап алу мүмкін болса, онда реттелген (х,у) парды кm тәсілмен таңдап алуға болады”. Комбинаторика есептерінің мысалдары Комбинаторика - белгілі бір шарттарды ескере отырып, кез келген элементтер жиынынан тұратын мүмкін комбинациялар санын бағалау. Ол үшін қажетті есепті ыңғайлы және жылдам шешуге мүмкіндік беретін комбинаторикада формулалар алынды. Бірақ бұл формулаларды көрсетпес бұрын, оларға әкелген сұрақтардың кейбір мысалдарын қарастырайық. 1-тапсырма. Әлем чемпионатының плей-офф кезеңіне 16 команда қатысады. Олар бір-біріне неше жолмен орындарды бөле алады? Мысалы: (3, 1, 2, 4..16) - №3 команда бірінші орында, №1 команда екінші орында, т.б. (16, 1, 2, 3, 4..15) - №16 команда бірінші орында, … (1..7, 9, 8, 10..16) - команданың бірінші орындарында 1, 2, 3, … Мұның барлығы опциялардың мысалдары. Бұл мәселенің айқын шешімі - бәрін жазу мүмкін комбинациялар. Дегенмен, бұл көп уақытты қажет етеді, өйткені олардың саны бірдей болады, өйткені 16 цифрды орындарда қайта реттеу жолдары бар. Комбинаторика элементтері осы сияқты мысалдарды бірден шешеді. 2-мәселе. Осы 16 команданың ішінде тек үшеуі ғана жүлде ала алады. Жеңімпаздар қанша әдіспен анықталады? Бұл жағдайда тапсырманың алдыңғы тапсырмадан айырмашылығы - турнирлік кестенің қандай болатыны және финалға шыққандардың реті қандай екендігі мүлдем маңызды емес. Шынында да, барлық командалардың арасынан жүлделі орындарға таласатын тек үшеуін табу маңызды. Яғни, жиындар {3, 2, 1}, {5, 12, 7}, {8, 1, 2}, т.б. сияқты болуы мүмкін. 3-мәселе. Сұрақты сәл басқаша қойсақ ше: плей-оффқа қатысатын 16 командаға медальдарды бөлудің қанша жолы бар? Екінші тапсырмадан айырмашылық толығымен анық болмауы мүмкін. Дегенмен, енді жүлделі орындарға таласатын үш команданы таңдап қана қоймай, олардың қайсысы қандай орын алатынын анықтауымыз керек. Басқаша айтқанда, егер екінші тапсырма үшін, мысалы, жиындар (5, 12, 1) және (1, 12, 5) баламалы болса, енді командалар реті салмаққа ие болады. Шынында да, бірінші жағдайда №5 команда алтынды алады, ал екінші жағдайда №1 команда. Комбинаторика жиынының ақырғы элементтерінен құралатын әр түрлі қосудың түрлерін қарастырады. жүктеу/скачать 60.65 Kb. Достарыңызбен бөлісу:
|
1 2