41.Қатарда іздеу. Боуер -мур алгоритмі



бет7/9
Дата10.06.2022
өлшемі114.5 Kb.
#267687
1   2   3   4   5   6   7   8   9
Байланысты:
Емтихан сұрақтары Алгоритмдер 41-50
1 сынып кмж, 7 3тоқ бжб 1 (2), Темірха Саят, 1554379220, 3 Информатика 8 сынып ПҚКО Алгоритм трассировкасы Презентация, 7 сынып, Веб-беттегі мультимедия, қорытынды аттестаттау, 423590, 9 сынып №2 БЖБ (4), 8 3тоқ бжб 1 (1), балаға қойылатын сұрақтар, ана туралы ән, Ағайынбыз бәріміз әні
P=NP проблемасы
P класының табиғи тұйықтығы бар (полиномдардың қосындысы мен көбейтіндісі де полином).
NP класы (полиномды уақытта тексерілетін есептер)
Алғаш Эдмондс жұмыстарында қарастырылып, күрделілілік кластарын енгізген соң, күрделілік теориясының негізгі проблемасы Р NP айтылды. Мәнісі: Шешімі полиномды күрделілікпен тексерілетін барлық есептерді полиномды уақытта шешуге бола ма? Қазіргі кезде екеуінің тең не тең еместігінің теориялық түрде дәлелдеуі жоқ, тек жорамал бар: Р класы NP класының ішкі жиыны, яғни NP Р жиыны бос емес. Бұл жорамал негізінде ТУР-толық есептер класы қарастырылады.
Класс NPC класы (ЖР-толық есептер)
NP-толықтық ұғымын алғаш Кук (Stephen Cook, 1971) пенЛевиным (1973) тәуелсіз түрде енгізді. Ол бір есепті екіншісіне келтіруге негізделді:
Егер бірінші есеп пен оны шешетін, нақты проблемаларда дұрыс жауап беретін алгоритм бар болса, ал екінші есептің алгоритмі белгісіз болса, онда екінші есепті бірінші есептің терминдерімен түрлендіріп, бірінші есептің алгоритмімен шешуге болады.
NPC класы мен NP-толық есептері екі шарттың орындалуын талап етеді:
3) есеп NP класына тиесілі болу керек
4) оған NP класының барлық есептері полиномды түрде келтірілуі тиіс.
Теорема NPC класына тиесілі полиномды шешу алгоритмі бар есеп бар болса, онда Р класы NP класымен тең болады, яғни P = NP ([2]).
Полиномиалды есептерге мысал.Қарапайым идея бояу туралы есеп үшін ықтимал алгоритмді алуды мүмкін еткізеді. Ол одан да қарапайым есеп үшін полиномиалды шешімді қолданады. Кездейсоқ түрде әрбір төбе үшін оны бояй алатын бірнеше түстер белгілейік. Әрбір төбе үшін сәйкес келетін жұбын табу 2/3 құрайды, ал онда осындай «алдын ала бояуды» табу ықтималдылығы әрбір төбе үшін (2/3) болып келеді. Ал егер әрбір төбе үшін екі түстің бірін таңдау қажет болса, онда полиномиалды алгоритм қолдануға болады
50.Cи тілінде пішімдеп енгізу-шығару функциялары: рrintf( s), scanf(s).

Бағдарламалаудың негізгі міндеті – ақпаратты өңдеу, сондықтан кез келген программалау тілінде ақпаратты енгізу және шығару құралдары болады. Си тілінде енгізу/шығару мәлімдемелері жоқ.


Ақпаратты енгізу және шығару стандартты кітапхананың функциялары арқылы жүзеге асырылады. Қарастырылып отырған функциялардың прототиптері stdio.h файлында. Бұл кітапханада функциялар бар
printf () – ақпаратты көрсету үшін
scanf () - ақпаратты енгізу үшін.
Си тілінде сыртқы ортамен мәліметтер алмасу енгізу-шы­ға­ру функция­лары кітапханасын пайдалану арқылы орындалады. Ол тақы­рып файлы ретінде былай жазылады:


Достарыңызбен бөлісу:
1   2   3   4   5   6   7   8   9




©melimde.com 2022
әкімшілігінің қараңыз

    Басты бет
Сабақтың тақырыбы
бойынша жиынтық
жиынтық бағалау
Сабақ тақырыбы
Сабақтың мақсаты
ғылым министрлігі
тоқсан бойынша
бағдарламасына сәйкес
бағалауға арналған
Сабақ жоспары
Реферат тақырыбы
жиынтық бағалауға
сәйкес оқыту
арналған тапсырмалар
Қазақстан республикасы
білім беретін
оқыту мақсаттары
бағалау тапсырмалары
республикасы білім
Жалпы ережелер
жиынтық бағалаудың
рсетілетін қызмет
бекіту туралы
тоқсанға арналған
Қазақстан тарихы
мерзімді жоспар
Қазақстан республикасының
арналған жиынтық
қызмет стандарты
болып табылады
жалпы білім
арналған әдістемелік
Мектепке дейінгі
оқыту әдістемесі
бағалаудың тапсырмалары
Қазақ әдебиеті
пәнінен тоқсанға
Инклюзивті білім
нтізбелік тақырыптық
Зертханалық жұмыс
Әдістемелік кешені
білім берудің
республикасының білім
туралы жалпы
Қазақстанның қазіргі
Қысқа мерзімді
Жұмыс бағдарламасы
атындағы жалпы
қазақ тілінде
қазіргі заман
туралы хабарландыру