А ш ы қ саба қ Пән: "Информатикадан олимпиадалық есептерді шешу әдістемесі"
жүктеу/скачать 32,36 Kb.
|
- Бұл бет үшін навигация:
- Негізгі білімді нақтылау кезеңі (2-3 мин)
- Қайталау сұрақтары
- Теориялық мәліметтерді қайталау: Динамикалық бағдарламалау дың мәні келесідей
- Динамикалық бағдарламалау әдісінің стратегиясы
| Конференция – сабақтың жүру барысы:
Ұйымдастыру кезеңі (1-2 мин) Конференцияның басында эмоционалды көңіл-күй, сенім, ынтымақтастық және шығармашылық атмосферасы қалыптастырылады. Сабақтың тақырыбымен таныстыру оқытушының кіріспе сөзінен басталады. Негізгі білімді нақтылау кезеңі (2-3 мин) Конференцияда тақырып бойынша білімді қорытындылауға және бекітуге, студенттердің тақырып туралы түсінігін кеңейтуге, өткен сабақтарды еске түсіруге және студенттермен қысқаша талқылауға тырысу керек. Қайталау сұрақтары: Динамикалық бағдарламалау есептерді шешудің неше тәсілін ұстанады? «Фибоначчи сандары» есебін шешу алгоритмін түсіндір. Теориялық мәліметтерді қайталау: Динамикалық бағдарламалаудың мәні келесідей: Есеп бір сипаттағы есептерге келтіріледі. Басқаша айтқанда, ол тәуелді (қабатталуы мүмкін) ішкі есептерге бөлінеді. Әрбір ішкі есеп бір рет бөлек шешіледі. Барлық ішкі есептердің шешімдерінің оңтайлы мәндері есте сақталады, бұл бұрын кездескен ішкі есептерді қайтадан шешпеуге мүмкіндік береді. Динамикалық бағдарламалау әдісінің стратегиясы - бұл есепті қарапайым есептерге дейін азайту әрекеті. «Қарапайым есеп» ұғымын әртүрлі тәсілдермен түсінуге болады: кейбір шектеулер алынып тасталғандықтан, есеп оңайырақ болуы мүмкін. Есеп қалай өзгертілсе де, егер бұл өзгеріс қарапайым есептің шешіміне әкелетін болса, онда осы қарапайым есептің негізінде түпнұсқаны шешуге болады. Динамикалық бағдарламалау - ішкі есептер тізбегін құрастыру арқылы есептерді шешу әдісі: тізбектің бірінші элементі (мүмкін бірнеше элементтер) тривиальды - жай, қарапайым - шешімге ие; осы тізбектің соңғы элементі бастапқы есеп болып табылады; осы тізбектегі әрбір есепті төменгі номерлі ішкі есептердің шешімін пайдаланып шешуге болады. Басқаша айтқанда, Т есебін динамикалық бағдарламалау әдісі арқылы шешу үшін T1, T2, ... Tn ішкі есептерінің белгілі бір тізбегі Т1 есебінің шешімі бұрыннан бар болатындай етіп құрастырылады, T = Tn, және ең бастысы, T1, T2, ... Ti-1 есептерінің шешімдерін біле отырып, кез келген i = 2..n үшін Ti есебінің шешімін шығаруға болады. ДБ әдісінің тиімділігінің дәлелі математикалық индукция принципінен тікелей шығады. Шынында да, егер қандай да бір есеп үшін осы қасиеттерді қанағаттандыратын жоғарыда аталған тізбекті құрастыра алатын болсақ, онда T1 біле отырып, T2 есебін (i=2 үшін), ал T1 және T2 есептерінің шешімд ерінен Т3 (Т3) есебінің шешімін оңай есептей аламыз. i=3 үшін) орындалады және т.б. i мәнін арттыру арқылы және i мәні n мәніне жеткенше бұрын шешілген есептер арқылы Ti есебінің шешімін табамыз, ал Tn есебінің шешімі - бастапқы есептің шешіміне эквивалент болады. жүктеу/скачать 32,36 Kb. Достарыңызбен бөлісу:
|