Дәрістер тезистері 1 тақырып Жиындар теориясының элементтері Мақсаты
жүктеу/скачать 2,49 Mb.
|
- Бұл бет үшін навигация:
- 1 анықтама .
- 2 анықтама .
| 2 Есептелетін функциялар
натурал сандар жиынында берілген немесе оның ішкі жиыныда берілген және N жиынынан мәндер қабылдайтын, бір аргументке немесе бірнеше аргументке тәуелді функциясын қарастырамыз. 1 анықтама. функциясы есептелімді деп аталады, егер оның барлық аргументтерінің мәндерін есептейтін және тоқтаусыз жұмыс жасайтын алгоритм табылса. болсын. 2 анықтама. Егер кез келген элемент берілген М жиынына тиісті ме, жоқ па екенін анықтайтын алгоритм тбар болса, онда М жиыны шешілімді жиын деп аталады. Егер функциясы М жиыныда берілсе және {0,1} екі элементті жиыннан мәндер қабылдаса, онда функциясы М жиынының сипаттамалық функциясы деп аталады және келесі түрде анықталады: М жиыны шешілімді ó егер оның сипаттамалық функциясы есептелімді болса. 3 анықтама. МN жиыны саналамды (рекурсивті немесе алгоритмді) деп аталады, егер М жиыны немесе бос жиын болса немесе оның мәндер жиыны қандай да бір есептелімді функция болса, басқаша айтқанда оның барлық элементтерін тізбектеп табатын алгоритм табылса. Мысал. М={1,4,9,…..} натурал сандардың квадраттары жиынын қарастырамыз. Ол 1,2,3…. сандарын біртіндеп квадраттау арқылы алынады, яғни саналымды жиын. Басқаша айтқанда, М= жиыны есептелімді функцияның мәндер жиыны болып табылады. Бұл жиын шешілімді де болады: қандай да бір сан берілген жиынға тиісті ме жоқ па тексеру үшін, оны жай көбейткіштерге жіктеу керек. Кез келген шешілімді жиын саналымды, бірақ кері тұжырым дұрыс емес.
жүктеу/скачать 2,49 Mb. Достарыңызбен бөлісу:
|