Информатиканың іргелі негіздері


Іздестіру, таңдау және сұрыптау алгоритмдеріне талдау жасау



бет64/67
Дата30.01.2022
өлшемі1,13 Mb.
#116311
1   ...   59   60   61   62   63   64   65   66   67
Байланысты:
лекция ИТН

Іздестіру, таңдау және сұрыптау алгоритмдеріне талдау жасау.

Практикалық есептерді шешуге арналған алгоритмдерді қолдану кезінде біз есепті шешу алгоритмін орынды таңдау мәселесімен кездесеміз. Таңдау мәселесін шешу салыстырмалы бағалар жүйесін құрумен байланысты. Ол өз кезегінде алгоритмнің формальды моделіне сүйенеді.

Ары қарай жалпы мәселеге қолданылатын Пост анықтамасына сүйене отырып, дұрыс және финитті алгоритмдерді, яғни жалпы мәселенің 1-шешімін беретін алгоритмдерді қарастырамыз. Формальды жүйе ретінде адрестік жадыны және жоғарғы деңгей тіліне сәйкестендірілген «элементар» амалдар жиынтығын қолдайтын фонНеймандық архитектуралы процессорды қамтитын абстрактілі машинаны қарастырамыз.

Ары қарай талдау мақсатында келесі ережелерді орнатамыз:



  • әр команда бекітілген уақыттан артық орныдалмайды;

  • алгоритмнің бастапқы берілгендері әрбіреуі биттен болатын машиналық сөздермен беріледі.

  • Нақты мәселе жадының N сөзімен беріледі, осылайша,алгоритм кірісінде = N* бит ақпарат. Кей жағдайларда әсіресе матрицалық есептерді қарастырғанда N алгоритм кірісінің сызықтық өлшемін бейнелейтін ұзындық өлшемі болып табылатынын атап өтейік.

Жалпы мәселені шешу алгоритмін жүзеге асыратын программа әрбіреуі биттер – = М* бит ақпарат болатын М машиналық инструкциядан тұрады.

Сонымен қатар, алгоритм абстрактілі машинаның келесі қосымша ресурстарын талап ете алады:



  • – аралық нәтижелерді сақтауға арналған жады;

  • – есептеу процесін ұйымдастыруға арналған жады (рекурсиялық шақырулар мен қайтаруларды жүзеге асыруға қажетті жады).

Жадының N сөзімен берілген нақты мәселені шешу кезінде тек финитті алгоритмдерді қарастыру шартында алгоритм абстрактілі.



Достарыңызбен бөлісу:
1   ...   59   60   61   62   63   64   65   66   67




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет