ббк76. 0 Қ 54 Редакционная коллегия
жүктеу/скачать 14,62 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- «ҚОҒАМДЫ АҚПАРАТТАНДЫРУ»
- Таблица 1 Поиск простых чисел соседей
- Список использованной литературы
- ТАЛҒАТ А. СЫМСЫЗ ЖЕЛІЛЕР
- Кесте 1 Сымсыз желілердің санаттары
3. Bujlow, Tomasz, and Valentin Carela-Espanol. "Comparison of Deep Packet Inspection (DPI) Tools for Traffic Classification." (2013).
УДК 004 АЛТЫНБЕК С.А., ТУРГИНБАЕВА А.С. НҰРЛЫБЕКОВ Н.Т. ОДИН ИЗ МЕТОДОВ ГЕНЕРАЦИИ ПРОСТЫХ ЧИСЕЛ НА БОЛЬШИХ ИНТЕРВАЛАХ (Евразийский национальный университет имени Л.Н. Гумилева) В данной работе исследуется новый метод генерации псевдопростых чисел в заданном интервале, а так же сравнение скорости с другими методами поиска. Для этого сгенерированы псевдопростые числа с помощью известного теста на простоту Солевея- Штрассена, исследовано скорость генерации новым методом, а так же генерация старыми методами. Ключевые слова: простые числа, составные числа, числа близнецы, натуральные числа, последовательность чисел, признаки делимости. Проблемы генерации простых (псевдопростых) чисел в большом интервале, вот уже в течение многих лет затрагивают интересы научного мира. Нами был предложен новый метод генерирования простых чисел, который как нам кажется, работает более эффективно по сравнению со всеми существующими методами [1-3]. Для изучения скорости генерации простых чисел нами при помощи этого метода и других методик были генерированы n простых чисел, находящихся в числовом ряду натуральных чисел от 10 z до 10 z+1 . Для
определение простоты заданного числа мы использовали известный тест Солефея- Штрассена. Для этого рассмотрим известное асимптотическое равенство, которое имеет следующий вид:
( ) ∼
(1)
Здесь функция ( ) выражает количество простых чисел меньших или равных . Знак “ ∼” означает, что отношение соединенных им выражений с ростом стремится к 1. Данное асимптотическое равенство впервые было доказанное Гауссом еще в 1896 году. Оно иногда называется законом распределения простых чисел. Данное равенство имеет ряд приближений и поправок, которые были введены Гауссом, Лежандром, Риманом и др. [4,5]. Согласно этим приближениям плотность простых чисел по мере перехода в область больших натуральных чисел непрерывно падает. Следовательно, в начале числового ряда натуральных чисел простые числа встречаются часто, они располагаются теснее, затем по мере перехода в область больших натуральных чисел они встречаются все реже и реже. Это означает, что расстояние между самими близкими соседними простыми числами в области «ҚОҒАМДЫ АҚПАРАТТАНДЫРУ» V ХАЛЫҚАРАЛЫҚ ҒЫЛЫМИ-ПРАКТИКАЛЫҚ КОНФЕРЕНЦИЯ
360
больших натуральных чисел становится все больше и больше, нежели в начале числового ряда.
Основываясь на этом асимптотическом уравнении, введем понятие плотности (математического ожидание) появление простого числа в заданном интервале.
Так количество простых чисел в интервале между (a,b) исходя из формулы (1) будет −
Таким образом, плотность или появление следующего простого числа в интервале равна
; (2)
Исследуем формулу (2) статистическим методом в интервалах от 10 z до 10 z+1 , где = 10 … 500 и сопоставим с исходной формулой (2). Для этого из каждого интервала (a,b) будем находить, определенное количество случайных простых чисел соседей и вычислим среднее расстояние между ними. Поиск простых чисел будем проводить с помощью теста соловея-штрассена, количество проверок теста для одного числа возьмем равным 20. Мы специально не будем использовать ускоренные методы, такие как решето Эротосфена, заранее деление на список простых чисел и другие математические трюки. В этой работе при одинаковых параметрах поиска простых чисел, главный приоритет уделяется времени относительного поиска простого числа по сравнению с другими методами.
Интервал = 1 … 500 Количество простых чисел
соседей. Статистическо е вычисление формулы (2)
( , ) = − ln − ln
10-11 300 23,55333 25,61303 20-21
300 47,48667 48,62442 30-31
300 68,38667 71,64549 40-41
300 92,05333 90,4669 50-51
300 114,9933 117,6934 100-101
300 223,6
232,8198 200-201
500 435,476
463,0769 450-451
300 1052,196 1038,722 500-501
300 1197,028 1153,852
Если присмотрится на Таблицу 1, то из колонок 3 и 4 выявляются закономерности относительно числа . Из аналитической геометрии нам известна формула линейной функции между двумя точками = которая эквивалентна формуле = ∗ + . Угловой коэффициент k между любыми точками варьируется между диапазоном (2,85:3,05). Таким образом, вышеуказанные кривая заданная точками, мы можем аппроксимировать линейной функцией. Для простоты вычисление заменим формулу (2) линейной функцией, которая зависит от степени числа 10.
«ҚОҒАМДЫ АҚПАРАТТАНДЫРУ» V ХАЛЫҚАРАЛЫҚ ҒЫЛЫМИ-ПРАКТИКАЛЫҚ КОНФЕРЕНЦИЯ
361
Теперь перейдем к самой сути исследовательской работы. Пусть в заданном интервале нам необходимо найти n ( например n=1000) простых чисел. Есть множество способом находить простые числа. Для больших чисел проверять все простые делители, не целесообразно.
1. Все n чисел искать случайно (рандомно) и проверять с помощью теста на простату. 2. Взять какое либо нечетное число из интервала и проверять на простату. Если число составное, к данному числу добавить 2 и снова проверят полученное число. 3. В заданном диапазоне находим первое простое число с помощью функции random. Пусть будет это число . Следующие простое число ищем в окрестности + ∗ с помощью теста на простоту Солевея-Штрассена. Проверяем ближайшее нечетное число = + ∗ с помощью теста на простоту. 4. Используя матрицу Байбекова, генерировать простые числа.
Само собой есть, в числовой оси есть составные числа, между которыми нету ни одного простого числа, например между (n+1)!+2 и (n+1)!+n+1. Второй и третий метод при попадании в такие интервалы, естественно будет работать не правильно и более медленно чем первый метод(рандомный), но тут можно поставить таймер для страховки.
В большинстве случаев, статистическим методом, из методов, выигрывает 3 и 4 метод.
Особенно остановимся на 4 методе генерации простых чисел в большом интервале.
Для данной работы предположим Гипотеза 1 Матрица Байбекова имеет следующие свойства. ( !) < ( !) < ( !) < ( !) …
Доказательство этой Гипотезы оставим на последующие работы. Для вычислений возьмем самую первую таблицу Байбекова ( !), для генерации чисел.
Для ( !) сложность выполнимых операций по матрице Байбекова по сравнению первого метода, сокращается на 1,875 раза.
Программная реализация статистическим методом, так же показывает лучшие результаты.
1. D.N.Lehmer. List of Prime Numbers from 1 to 10006721, Hafner Publishing Co., New York, 1956 2. M.F.Jones, M.Lal, W.J.Blundon. Statistics on certain large primes, Math. Comp. 21, 1967, 103- 107.
Science, №7, 2015.
4. Д. Цагир. Первые 50 миллионов простых чисел. В кн.: W.Borho, D.Zagier, J.Rohlfs, H.Kraft, J.Jantzen. Lebendige zahlen. FÜnf exkursionen. Bonner Universitӓt. Birkhӓuser Verlag. Basel-Boston- Stuttgart. 1981. 42-72.
5. G.H.Hardy, E.M.Wright. An Introduction to the Theory of Numbers, 5 th ed., Oxford, 1979, 371-373.
6. D.C.Mapes. Fast method for computing the number of primes less than a given limit. Math. Comp. 17, 1963, 179-185
«ҚОҒАМДЫ АҚПАРАТТАНДЫРУ» V ХАЛЫҚАРАЛЫҚ ҒЫЛЫМИ-ПРАКТИКАЛЫҚ КОНФЕРЕНЦИЯ
362
ӘОЖ 621.38 ТАЛҒАТ А. СЫМСЫЗ ЖЕЛІЛЕР (Қазақ технология және бизнес университеті, Астана, Қазақстан)
Сымсыз сенсорлы желі түсінігі және бірінші прототипі Америка Құрама Штаттарында пайда болды. Сенсорлы желінің ғылыми-зерттеудің және дамуы Америка Құрама Штаттарында бірнеше жоғарғы оқу орындарында өткізілді. Барынша табыстысы Калифорния 4 штатының Беркли университетінің профессоры Кристофер Пистердің ғылыми-зерттеулері болды. Кристофер Пистердің ғылыми-зерттеулері және Берклиде құрастырылған үлгісі – smart dust, ол сирек кездесетін функционалдық мүмкіндіктерге ие болды, компаниялардың қызығушылығын тудырды, ZigBee альянсының мүшелерімен құрылған компаниялар Ember, Freescale Semiconductor, Honeywell, Invensys, Mitsubishi Electric, Motorola, Philips Electronics және Samsung энергияны аз тұтынатын ашық стандартты сымсыз желі
мониторингі және
басқаруды жүзеге
асыру мақсатында ZigBee протоколдарының жиынтығы жеті деңгейлі ашық жүйелердің өзара әрекеттесуін іске асырады. Екі төменгі деңгейі (физикалық және радио арна деңгейі) төменгі жылдамдықты IEEE 802.15.4-2003 дербес радио желілердің стандарты болып табылады [1]. Желінің келесі түрлері болады: Дәстүрлі сымды желілер: деректер витая жұбы, коаксиалды кабель, талшықты оптика, т.б. арқылы тасымалданатын кабельдердің құнын талап етеді Сымсыз желілер: деректер ауа арқылы берілетін, және сигналды қабылдау үшін ұялы пайдаланушылар үшін қол жетімді болып табылады Сымсыз сенсорлы желілер
- қазіргі
заманғы телекоммуникациялық технологияларды дамыту неғұрлым перспективалы бағыттардың бірі болып табылады. Сымсыз сенсорлы желі – бұл тармақталған желі қызмет көрсетілмейтін ықшам электрондық құрылымдардан тармақталған желі, осы сымсыз байланыстың көмегімен түйіннен түйінге ретрансляция арқылы негізгі станцияға сыртқы орта параметрлерін және ақпараттың жіберілуін жүзеге асырады [2]. Желілердегі байланысты жүзеге асыру үшін үшін қуат кабелі, телефон желісі, оптикалық талшықты кабель (оптикалық талшықты); радио (сымсыз желілер, WiFi) қолданылады.. Сымсыз сенсорлы желілердің жоғарыда аталған ерекшеліктері келесі бағыттар бойынша кешенді проблемаларды шешуге арналады: Телекоммуникациялық инфрақұрылым желілерінің мониторингі. Автожолдар магистралінің мониторингі (темір жол, метрополитен және т.б.), мұнай және газ құбырлары. Көлік жүк тасымалының мониторингі және талдау. Экологиялық биологиялық және медициналық бақылау. Автоматтандыру жүйесін және өмір қолдау жүйелері «Ақылды үй» . Төтенше жағдайлардың алдын алу және анықтау (сейсмикалық және жанартау қызметінің мониторингі, табиғи апаттар туындау уақтылы ескерту үшін атмосфера мен ауа райы болжамын талдау). Сымсыз желілерді қолдану тиімділік беретін аймақтар: қоймалар мен зауыттар; аурухана; көрме орталықтары мен конференц-зал;
«ҚОҒАМДЫ АҚПАРАТТАНДЫРУ» V ХАЛЫҚАРАЛЫҚ ҒЫЛЫМИ-ПРАКТИКАЛЫҚ КОНФЕРЕНЦИЯ
363
қонақүйлер, кафе, кітапханаларда интернетке қатынау; клиенттер мен серіктестер үшін корпоративтік желілерге қатынау; интернет провайдерлері: кабельмен қолжетімділік мүмкіндігі жоқ connect клиенттер [3] Сымсыз желілердің санаттары мен сипаттамалары төмендегі 1-кестеде берілген. Кесте 1 Сымсыз желілердің санаттары Типтері
Әрекет ету аумағы Стандарты Қолдану саласы Дербес
сымсыз желі Пайдаланушының тікелей жақын жерде Bluetooth, IEEE 802.15, IRDA Ауыстыру кабельдер перифериялық құрылғылар Жергілікті сымсыз желілер Ғимараттар мен кампустар аясында IEEE 802.15,Wi- Fi,HiperLAN Сымды желілер, мобильді ұзарту Аймақтық сымсыз желілер Қала шегінде IEEE 802.16, WIMAX
Ғимараттар, кәсіпорындар мен интернет арасында тіркелген сымсыз байланыс Ғаламдық сымсыз желілер Дүние жүзі бойынша Ұялы телефон жүйесі ұрпақ 2, 2,5, 3, GPRS Интернет нысандарына мобильді қол жеткізу болып табылады
Қазіргі таңда негізгі құрылғылар бағасының шапшаң арзандауына байланысты Wi-Fi– желілер аса тиімділік танытып отыр, атап айтқанда қазіргі кезде
әуежайлар, вокзалдар, көрме орталықтары, кафе, мейрамханалар және т.б. сияқты қоғамдық орындарда Интернетке сымсыз кіру қызметін атқаруда және келешегі жоғары шешім болып табылады. Сонымен қатар үй секторында, корпоративті секторда Wi-Fi базасындағы жергілікті желілерге деген қызығушылық, Wi-Fi байланыс құралдарымен ноутбуктер және ҚДК-мен жабдықталған мобильді құрылғылар санының жылдам өсуімен жоғарылауда. Wi–Fi немесе WLAN (Wireless LAN) желілері деп те аталатын сымсыз желілерді дәстүрлі сымды желілермен салыстырғандағы елеулі артықшылығы оны қолданудың қарапайымдылығында. Ең алдымен, сымсыз желі кабельдер көмегін қажет етпейді. Сонымен қатар сымсыз желілер өзінің қазіргі заманғы даму кезеңінде кемшіліктері де аз емес – бұл қазіргі өлшемдер бойынша байланыс жылдамдығының төмендегі. Бұл жылдамдық, сонымен қатар, қабылдағыш пен таратқыш арасында шектеу мен қашықтықтың нашар масштабталудың бар болуына және де егер сымсыз желілерді ғимараттарда қолданғандағы оның әсер етуінің шектеулі радиусына тәуелді. Сымсыз желілердің әсер ету радиусын үлкейту тәсілдерінің бірі ретінде сымсыз енудің бірнеше нүктелері негізінде таралған желіні құруды айтуға болады [4]. Осылайша, аталған кемшіліктеріне қарамастан, сымсыз желілердің артықшылықтары басым, оның қолданысы кең, әрі пайдаланушылар үшін ыңғайлы, сондықтан да тиімділік танытып отыр.
1. Расторгуев Н. Шуклин А. Строим Wi-Fi. Экспресс-Электроника. - №12. – 2004 2. Гургенидзе А. Современные технологии беспроводных сетей Мобильные телекоммуникации. – Вып. 62. - № 4. – 2006 3. Тұрым А.Ш. Есептеу жүйелері және желілері..Оқулық. – Алматы. ҚазҰТУ.- 2006 4. Дуйсенова А. А., Муханова Ж. А., Пирова Г. К. Қазіргі заманғы сымсыз байланыс тораптарының технологиясы мен құрылымы // Молодой ученый. — 2015. — №1.1. — С. 19-20.
«ҚОҒАМДЫ АҚПАРАТТАНДЫРУ» V ХАЛЫҚАРАЛЫҚ ҒЫЛЫМИ-ПРАКТИКАЛЫҚ КОНФЕРЕНЦИЯ
364
ӘОЖ 004:519.95
1 ., ЖАРАСОВ Ж.А. 2 АҚПАРАТТЫҚ ЖҮЙЕЛЕРДІҢ СЕНІМДІЛІГІН ҚАМТАМАСЫЗ ЕТУ ӘДІСТЕРІ ( 1 Еуразия ұлттық университеті, Астана, Қазақстан 2 Қазақ технология және бизнес университеті, Астана, Қазақстан) Ақпараттық жүйелердің сенімділігін қамтамасыз ету көптеген факторларға, атап айтқанда деректерді сақтау және байланыс арнасымен жіберу кезінде жүйенің деректерін қорғауды қамтамасыз етуге тікелей байланысты. Заманауи ақпараттық технологиялар мүмкіндіктері мен тиімді кодтау әдістерін қолдану арқылы ақпараттық жүйенің сақталатын және жіберілетін деректерінің көлемін, арнаға жіберу уақытын қысқартуға қол жеткізуге болады. Бұл өз кезегінде жіберілетін деректердің шынайылығына, ақпараттық жүйенің сенімділігіне әсерін тигізеді. Сондықтан да, ақпараттық жүйені жобалағанда ақпараттық жүйе сенімділігін қамтамасыз ету үшін байланыс теориясының, соның ішінде сигналдар теориясының, бөгеуілге орнықты кодтау теориясының, ақпарат теориясының талаптары ескеріледі.
тағайындалған шекті мәндерінің уақыт ішінде сақталу қасиетін айтады. Сенімділік ұғымына объекттің істен шығусыз жұмыс істеуі, ұзақ уақыт жұмыс істеуі, жөндеуге жарамдылығы және сақталушылығы сияқты қасиеттер кіреді [1]. Ақпараттық жүйе сенімді болуы үшін оның әрбір элементі істен шықпай жұмыс істеуі тиіс. Қазіргі таңдағы ақпараттық жүйелердің күрделілігін, әртекті болуын, әр түрлі платформалар мен технологияларға негізделуін, кең ауқымдылығы мен көпдеңгейлілігін, ақпарат алмасу үшін Интернет, Интранет желілерін қолдануын ескерсек, оның қауіпсіздігінің мәселесі де аса өзекті болып отыр. Ақпараттық жүйенің қауіпсіздігін қамтамасыз етудің, сенімділігін арттырудың бір жолы ретінде арнаға жіберілетін деректерге бөгеуілге орнықты кодтау қолданылады. Кодтау кезінде ақпаратты өңдеудің тиімділігі мен сенімділігін қамтамасыз ету мәселесі шешіледі, сондай-ақ шифрлеуді қолдану арқылы ақпарат мазмұны жасырылып, деректерді қорғау да жүзеге асады. Жүйенің сенімділігіне төнетін қатерлер (программалық қамтамасының қателері) ішкі және сыртқы болып екі топқа бөлінеді [2]. Ішкі қателерге жобалау қателері, алгоритмдеу қателері, программалау қателері, қорғау құралдарының төмен сапасы, құжаттамалардағы қателер жатады. Сыртқы қателерді қолданушылардың қателері, есептеу жүйесінің аппаратурасының істен шығуы, байланыс арнасындағы ақпараттың бұрмалануы, жүйе конфигурациясының өзгерістері тудырады. Ақпараттық жүйенің күрделі болуы оның программалық қамтамасының сенімділігінің төмен болуының бірден бір себепкері болып табылады. Сондықтан да, программалық қамтаманың сенімділігін арттыру үшін жобалау кезінде келесі әдістер қолданылады [3]:
әдістер;
функцияларын жасауға арналған әдістер;
салдарын түзетуге, қате болған жағдайда жүйенің жұмыс істеуін қамтамасыз етуге арналған қосымша функциялары.
«ҚОҒАМДЫ АҚПАРАТТАНДЫРУ» V ХАЛЫҚАРАЛЫҚ ҒЫЛЫМИ-ПРАКТИКАЛЫҚ КОНФЕРЕНЦИЯ
365
Ақпараттық жүйенің программалық қамтамасының сенімділігін арттыру үшін оны жобалау процесінің әрбір кезеңінде қателердің болуының алдын алудың келесі әдістері қолданылады [3]: жүйе күрделілігімен күресуге арналған әдістер (декомпозицияны, яғни иерархиялық құрылымды қолдану; жүйе элементтерін тәуелсіз ету); ақпаратты үлкен дәлдікпен аударуға (түрлендіруге) қол жеткізетін әдістер; ақпарат алмасуды жақсартуға арналған әдістер; жобалаудың әр кезеңінде қателерді тез анықтап, тез жоюға арналған әдістер. Қателерді анықтау әдістері программалық қамтамаға әртүрлі артықтықты (уақыттық, ақпараттық, программалық артықтықтар) енгізуге негізделеді. Уақыттық артықтық (немесе артық уақыт) істен шығудан кейін программалық қамтаманың жұмысын қалпына келтіруді және орындалуын бақылау үшін есептеу техникасының өнімділігінің бір бөлігін пайдаланады. Ақпараттық артықтықта сенімділікті қамтамасыз ету үшін және деректердің шынайылығын бақылау үшін ақпараттық жүйе деректерінің бөлігі қайталанады (дублдеу жүреді). Программалық артықтықтың құрамы өзара сенімсіздік (жүйе компоненттерінің басқа компоненттер мен бастапқы деректерде қате бар деген болжаммен жобалануы); қателерді тез табу және тіркеу; жүйенің бірдей функцияларын әртүрлі модулдерге орындату және өңдеу нәтижелерін салыстыру; басқа артықтық түрлерін қолданып деректерді бақылау және істен шығудан соң қалпына келтіру сияқты әрекеттерден тұрады. Қателерге орнықтылықты қамтамасыз ету әдістері қателердің әсерінен туындайтын шығындарды азайтуға бағытталады, оның құрамына: аппаратураның істен шығуларын өңдеу;операцияларды қайта орындату; конфигурацияны динамикалық өзгерту; жүйенің кейбір функциялары істен шыққан жағдайда қысқартылған қызмет көрсету; деректердің көшірмесін алу және қалпына келтіру;қателерді оқшаулау сияқты әдістер кіреді.
Олай болса, ақпараттық жүйенің сенімділігі қолданушыға берілетін ақпараттың шынайылығымен және ақпараттың дәл уақытында жеткізілуімен, сырттан қатынаудан қорғалуымен анықталады. Бөгеуілге орнықты кодтау ақпараттың шынайылығын (оның жіберілген түпнұсқасындай болып дұрыс қабылдануын) қамтамасыз етеді. Ақпараттың шынайылығына жіберілетін ақпарат жайлы мәлімет пен оқиғаның болу уақытын көрсету, әртүрлі ақпарат көздерінен түскен деректерді салыстыру, ақпараттың жалғандығын дәл уақытында анықтау, ақпараттың бұрмалануын болдырмау арқылы қол жеткізуге болады. Қажетті шынайылықпен белгіленген уақыт ішінде ақпаратты жіберуді қамтамасыз ету үшін құрылымдық және ақпараттық резервтер (сенімділік теориясының ұсынуы бойынша) және жіберілетін хабарға ақпараттық артықтықты енгізу (бөгеуілге орнықты кодтау теориясының ұсынуы бойынша) қолданылады. Құрылымдық резервті қолданғанда бір хабар бір мезгілде бірнеше байланыс арнасымен жіберіледі де, қабылданған хабарлар салыстырылып, көпшілік арналарда бірдей болған нұсқасы дұрыс деп саналады. Жүйенің құрылымында жіберушіге келіп түскен хабардың бұрмаланғанын немесе қателердің жоқ екенін хабарлайтын кері байланыс арнасы да қолданылуы мүмкін. Ақпараттық артықтықты қолданғанда арнамен жіберілетін хабар (деректердің блоктары) бірнеше рет қайталанып жіберілуі мүмкін, сондай-ақ қабылдаушы жақта қатені анықтайтын немесе түзете алатын арнайы түзетуші кодтар қолдануы мүмкін. Түзетуші кодтарды қолдану ақпаратты кодтау мен декодтауға арналған қосымша аппараттық, программалық құралдарды және кодтау-декодтауды орындауға қосымша уақытты қажет етеді. Сенімділік теориясының, бөгеуілге орнықты кодтау теориясының негізінде ақпарат жіберу шынайылығын арттыру үшін келесі әдістер қолданылады [4]: |