Алгоритм ұғымын формалдау

Шекті уақыт ішінде егер расымен солай болса, сөйлемнің шынайы екендігін растайтын болмаса шексіз жұмыс істейтін алгоритм болатындығын білдіреді. Мысалы математиканың көп есебі барлық сан емес, санның нақты түріне ғана қолданылады.

Есептелу теориясында тоқтату проблемасы бұл шешімі болу проблемасы, оның мәнісі: алгоритм мен оның бастапқы деректері берілсін, осы деректермен алгоритмнің жұмысы аяқтала ма, жоқ тоқтаусыз жұмыс істей бере ме екендігін анықтау қажет.

1936 жылы Алан Тьюринг кез келген мүмкін болатын кірістік деректер үшін тоқтап қалудың проблемасын шешудің жалпы алгоритмі болмайтындығын дәлелдеді. Тоқтап қалу проблемасы Тьюринг машинасында шешілмейді.

Шешімі болмауды дәлелдеудің 2 әдісі бар: тікелей әдіс және жанама әдіс.

Алгоритмдер теориясында алынған нәтижелер екі аспектіде: теориялық және практикалық аспектілерде қолданылады. Теориялық аспект: Есептің алгоритмдік шешімі болатындығын немесе оны шешудің нақты алгоритмі болмайтындығына есепті зерттеу нәтижесінде алгоритмдер теориясының жауап беру мүмкіндігі теориялық аспектіге жатады. Алгоритмдік шешімі болмайтын есептер Тьюринг машинасын тоқтату есебіне келтіріледі. Ал алгоритмдік шешімі болатын есептер үшін олардың NP-толық есептер класына тиесілі ме екендігі анықталады. Егер тиесілі болса, онда бастапқы деректері үлкен болатын есептердің нақты шешімін алу үшін қанша уақыт кететінін анықтауға немесе оны шешудің жылдам нақты алгоритмі болмайтындығын айтуға мүмкіндік береді. Практикалық аспект: алгоритмдер теориясының, әсіресе асимптотикалық және практикалық талдаудың әдістері мен әдістемелері келесі мүмкіндіктерді береді: Берілген есепті шешуге арналған алгоритмдер жиынынан жасалатын программалық жүйедегі олардың ерекшелігін ескеретін тиімді алгоритмді таңдауға мүмкіндік береді. Күрделілік функциясы арқылы күрделі есептерді шешудің уақыттық бағалауларын алады. Белгілі уақыт ішінде қандай да бір есептің шешуі болмайтындығына шынайы баға беріледі. Ақпаратты өңдеу саласындаың маңызды деген есептерін шешудің тиімді алгоримтмдерін құру мен жетілдіру. Мысалы: алгоритмді жүзеге асыратын программаның орындалу уақытына немесе пайдаланатын минималды жад көлеміне шектеулер қойылғанда түрлі алгоритмдерден таңдау жасалынады; қиындық функциясы арқылы күрделі есептерді шешу уақыты анықталады; берілген уақыт ішінде есепті шешу мүмкін болмайтындығы шынайы бағаланады. Бұл қазіргі кезде криптографиялық әдістер үшін, ақпаратты өңдеу саласында практикалық жағынан маңызды есептерді шешудің тиімді алгоритмдерін жасау мен жетілдіру үшін аса сұранысқа ие болып отыр