Леонард Эйлер циклы

Кіріспе 3
1 Леонард Эйлер 4
1.1 Байланысқан және байланыссыз графтар 5
2 Эйлер циклы 11
Қорытынды 18
Қолданылған әдебиеттер тізімі 19

Дискреттік Математика – математиканың дискретті құрылымдардың қасиеттерін зерттейтін саласы. Мұндай құрылымдарға шектеулі топтар, шектеулі графтар, сондай-ақ, ақпаратты түрлендіргіш кейбір математикалық модельдер, шектеулі автоматтар, Тьюринг машинасы, және т.б. жатады. Компьютерлерді жасау және пайдалану программалау тілдері, ақпаратты өңдеу және тарату жабдықтары, автоматтандырылған басқару және жобалау жүйелері мамандарының зерттеу жұмыстары үүшін дискретті математика әдістері негізгі құрал, ал дискретті математика тілі осы мәселелер бойынша пайдаланатын ғылыми және техникалық тіл болып табылады. - программалау процесінде жасанды интеллект есептерін шығаруда, программалардың дұрыстығын дәлелдеуде модельдеуді пайдалануға дағдыландыру. Компьютерлік ғылымның теориялық фундаменті болып саналатын дискретті математика арқылы сипаттағы құрылымдар қасиеттерін зерттейтін математиканың бір саласы болып саналады.
Дискретті математика негіздері егер үлкен есептеу жүйелері құрылса, онда олардың қандай да бір пайда болған үлкен есептерді шешу үүшін қажеттілігі болғаны. Кез-келген салада әр түрлі мәселелер, яғни соған байланысты жүздеген, мыңдаған сұрақтар пайда болуда. Ал олардың жауабын іздеудің жалпы қағидалары өте ертеректе құрастырылған. Бірінші, осы объектінің немесе процестің математикалық моделін құрудан бастайды. Математикалық модельдеу объектінің белгілі бір болмысын немесе болып жатқан процестерді теңдеулер тілінде және басқадай математикалық құралдар арқылы көрсету. Яғни, математикалық модель зерттеу облысына қатысты қандай да бір дифференциалдық, интегралдық алгебралық немесе басқа да бір өрнектер жиыны. Осы алынған математикалық модельді, яғни теңдеудінемесе әртүрлі теңдеулер жүйесін шеше отырып, біз қойылған сұрақтардың жауабын ала аламыз. Әрине, компьютерлер қаншалықты қуатты болғанымен олар өз беттерінше берілген есептерді шеше алмайды. Олар тек қана өте қарапайым амалдарды ғана орындай алады. Ал олардың бүкіл интеллектуалдық күші адам құрастырған бағдарламалармен анықталады. Бағдарламалар қандай да бір мақсатқа құрылған қарапайым амалдар тізбегін іске асырады. Шешімді іздеу, қарапайым амалдар тізбегін орындау процесіне келіп тіреледі. Бұл алгоритмді құрастыру деп аталады. Дискретті математика және математикалық логика пәні математика білімінің бөлінбес бір бөлігі болып саналады.

1. Потемкин И.С Функциональные узлы цировой автоматики. – М.: Радио и связь; 1986
2. Ушаков В.Н., Долженко О.В Электроника: от элементов до устройств -М.: Радио и связь; 1986
3. Белов В.В., Воробьев Е.М., Шаталов В.Е. Теория графов. – М.: Высшая школа, 1976. -392 с.
4. Бабич Н.П., Жуков И.А. «Компьютерная схемотехника. Методы построения и проектирования»: Учебное пособие. – К.: «МК-Пресс», 2004.- 576с., ил.
5. Симонович С.В. «Информатика». – Санкт-Петербург – 2000 г.
6. Острейковский В.А. «Информатика».- М.: Высш.шк., 2001г.
7. Могилев А.В. и др. «Информатика». – Москва.: ACADEMA, 1999 г.
8. Информатика/ Под ред. Н.В.Макаровой. — М.: Финансы и статистика, 1997
9. Аванесян Г.Р., Лёвшин В.П.Интегральные микросхемы ТТЛ, ТТЛШ: Справочник М.: Машиностроение, 1993

Пән: Математика, Геометрия
Жұмыс түрі: Курстық жұмыс
Тегін: Антиплагиат
Көлемі: 16 бет
Таңдаулыға:

МАЗМҰНЫ

Кіріспе
3
1
Леонард Эйлер
4
1.1
Байланысқан және байланыссыз графтар
5
2
Эйлер циклы
11

Қорытынды
18

Қолданылған әдебиеттер тізімі
19

КІРІСПЕ

Дискреттік Математика - математиканың дискретті құрылымдардың қасиеттерін зерттейтін саласы. Мұндай құрылымдарға шектеулі топтар, шектеулі графтар, сондай-ақ, ақпаратты түрлендіргіш кейбір математикалық модельдер, шектеулі автоматтар, Тьюринг машинасы, және т.б. жатады. Компьютерлерді жасау және пайдалану программалау тілдері, ақпаратты өңдеу және тарату жабдықтары, автоматтандырылған басқару және жобалау жүйелері мамандарының зерттеу жұмыстары үүшін дискретті математика әдістері негізгі құрал, ал дискретті математика тілі осы мәселелер бойынша пайдаланатын ғылыми және техникалық тіл болып табылады. - программалау процесінде жасанды интеллект есептерін шығаруда, программалардың дұрыстығын дәлелдеуде модельдеуді пайдалануға дағдыландыру. Компьютерлік ғылымның теориялық фундаменті болып саналатын дискретті математика арқылы сипаттағы құрылымдар қасиеттерін зерттейтін математиканың бір саласы болып саналады.
Дискретті математика негіздері егер үлкен есептеу жүйелері құрылса, онда олардың қандай да бір пайда болған үлкен есептерді шешу үүшін қажеттілігі болғаны. Кез-келген салада әр түрлі мәселелер, яғни соған байланысты жүздеген, мыңдаған сұрақтар пайда болуда. Ал олардың жауабын іздеудің жалпы қағидалары өте ертеректе құрастырылған. Бірінші, осы объектінің немесе процестің математикалық моделін құрудан бастайды. Математикалық модельдеу объектінің белгілі бір болмысын немесе болып жатқан процестерді теңдеулер тілінде және басқадай математикалық құралдар арқылы көрсету. Яғни, математикалық модель зерттеу облысына қатысты қандай да бір дифференциалдық, интегралдық алгебралық немесе басқа да бір өрнектер жиыны. Осы алынған математикалық модельді, яғни теңдеудінемесе әртүрлі теңдеулер жүйесін шеше отырып, біз қойылған сұрақтардың жауабын ала аламыз. Әрине, компьютерлер қаншалықты қуатты болғанымен олар өз беттерінше берілген есептерді шеше алмайды. Олар тек қана өте қарапайым амалдарды ғана орындай алады. Ал олардың бүкіл интеллектуалдық күші адам құрастырған бағдарламалармен анықталады. Бағдарламалар қандай да бір мақсатқа құрылған қарапайым амалдар тізбегін іске асырады. Шешімді іздеу, қарапайым амалдар тізбегін орындау процесіне келіп тіреледі. Бұл алгоритмді құрастыру деп аталады. Дискретті математика және математикалық логика пәні математика білімінің бөлінбес бір бөлігі болып саналады.

1 Леонард Эйлер

Леонард Эйлер швейцариялық математик, механик және физик. Базель университетін бітірген.1727 жылдан Санкт-Петербург академиясында қызмет істеді. Ол Санкт-Петербург және Бердин академияларынан басқа Париж академиясының, Лондон корольдік қоғамының, Санкт-Петербург академиясының т.б көптеген ірі ғылым қоғамдардың мүшесі болды.
Эйлердің негізгі еңбектері сол кездегі математика мен механиканың барлық саласына, серпімділік теориясына, математикалық физикаға, оптикаға, музыка теориясына, машиналар теориясына, баллистикаға, теңіз ғылымына, т.б. арналған. Оның ғылыми еңбектерінің жинағы ауқымды 60-80 том көлемінде деп болжанады. Эйлер "Аналитикалық түрде баяндалған механика не қозғалыс туралы ғылым" (2 томдық, 1736), "Анализге кіріспе" (2 томдық, 1748), "Дифференциалдық есептеу" (1755), "Универсал арифметика" (2 томдық, 1768 - 1769) және 6 тілде 30 шақты рет басылып шыққан "Интегралдық есептеу" (3 томдық, 1768 - 1770; 4 томдық, 1794), т.б. осы сияқты бірқатар классик.монографияларында өзінің және басқа ғалымдардың зерттеулерінің нәтижелерін жүйеге келтірді.
Ол "Механика" атты монографиясында жаңа математикалық анализдің көмегі арқылы нүкте динамикасын тұңғыш рет кең көлемде баяндады, ал "Қатты денелер қозғалысы теориясында" қатты дененің кинематикасы мендинамикасының теориясын жетілдірді және қатты дененің қозғалмайтын нүкте маңынан айналу теңдеуін (гироскоптар теориясының бастамасы болған) тапты. Аспан механикасы бойынша да үлкен жаңалықтар ашты.
1771-1757 жылдары жарық көрген мемуарлары тұтас орта механикасы жөнінен жүргізілген зерттеулерге қосылған елеулі үлесі болды. Эйлер вариациялық есептеу мен дифференциалдық теңдеулер теориясының негізін жасады, дифференциалдық және интегралдық есептеулерді жалпылап, одан әрі дамытты. Ол - 886 мақала мен мемуардың
авторы.
Математик, механик Л.Эйлер байланысқан бағытталмаған мультиграфта оның барлық қабырғаларынан тұратын цикл болатынын тұжырымдап берді. Мультиграфтың барлық қабырғаларынан тұратын цикл Эйлерлік д.а.
Теорема. Байланысқан бағытталмаған мультиграф Эйлерлік болады сол жағдайда, егер оның әр төбесінің дәрежесі - жұп сан болса.
Эйлерлік мультиграфта эйлер циклін табудың алгоритмі:
1. кез келген а төбені аламыз.
2. а төбесіне инцидентті кез келген u қабырғаны алып, оған 1 номер береміз (бұл қабырғаны жүрілген д.а.)
3. әрбір жүрілген қабырғаны сызып, 1 ден артық номер беріп отырамыз.
4. х төбесінде тұрып а төбесімен қосатын қабырғаны таңдамаймыз, егер басқа мүмкіндік болатын болса.
5. х төбесінде тұрып, сызылған қабырғаны таңдамау керек.
6. графтың барлық қабырғасы номерленгеннен кейін эйлер циклі пайда болады. Реттелген номер графтың айналу ретін көрсетеді.

1.1 Байланысқан және байланыссыз графтар

Графтағы ешбір қабырға арқылы 1-ден артық рет өтпейтін сызық шынжыр деп аталады. Егер қозғалысты А нүктесінен бастап, барлық төбелерден әр қабырға бойымен тек бір ғана рет жүре отырып, сол А төбесіне қайта оралу мүмкін болса, мұндай жолды цикл деп атайды. Егер циклдың барлық төбелері әртүрлі болса, мұндай цикл қарапайым цикл, ал қарсы жағдайда - қарапайым емес цикл деп аталады. Кей жағдайда цикл графтың барлық қабырғаларын дәл бір реттен қамтиды. Мұндай циклдарды Эйлер сызықтары деп атайды.
Егер графтың кез келген екі төбелері қандай да бір шынжырмен байланысып тұрса, ондай графты байланысты граф дейді, яғни байланысты граф дегеніміз бірде бір оқшауланған нүктесі болмайтын граф.
Егер графтың ең болмағанда екі төбесін қосатын жол болмаса, оны байланыссыз граф деп атайды, яғни оның қандай да бір төбесінен шығып, басқа төбелеріне қабырғаларының ешқайсысынан бір рет қана өте отырып бару мүмкін болмайды.
Байланысты графтың қасиеттері:
1. кез келген байланысты графтың дәрежелері тең болатын ең болмағанда екі төбесі бар болады.
2. барлық төбелерінің дәрежелері жұп болатын байланысты граф Эйлер сызығы болып табылады.
3. байланысты графта оның барлық қабырғаларын дәл бір реттен қамтитын l(A, B) шынжыры бар болуы үүшін А мен В төбелерінен басқа тақ дәрежелі төбелердің болмауы қажетті және жеткілікті.
Барлық қабырғаларының бағыты көрсетілген граф бағдарланған граф деп аталады. Қабырғаларының бағыты көрсетілмеген графты бағдарланбаған граф дейді. Кей қабырғаларының бағыты бар, ал кей қабырғаларының бағыты көрсетілмеген графты аралас граф дейді.
Ұштарындағы нүктелері беттесетін қабырғаны тұзақ деп атайды. Графты кескіндеу барысында тұзақ сол төбеге қайтып келетін және басқа төбелерден өтпейтін тұйық доға түрінде болады.
Эйлера функциясы , мұндағы - натурал сан, санынан үлкен емес әрі онымен өөзара жай натурал сандар санына тең. Эйлера бұл функцияны сандар теориясы еңбектерінде алғашқы болып пайдаланғандықтан соның құрметіне осылай талып кетті.
Анықтама
жай сандарға келесідей жіктелген натурал саны берілсін:

Онда

функциясы Эйлер функциясы деп аталады. Мұндағы болады деп саналады. Эйлера функциясын Эйлер көбейтіндісі ретінде де өрнектеуге болады:

мұндағы -- санының жай сандарға жіктелуінде қатысатын барлық жай сандарды қабылдайды.

Функцияның кейбір мәндері

+0
+1
+2
+3
+4
+5
+6
+7
+8
+9
0+

1
1
2
2
4
2
6
4
6
10+
4
10
4
12
6
8
8
16
6
18
20+
8
12
10
22
8
20
12
18
12
28
30+
8
30
16
20
16
24
12
36
18
24
40+
16
40
12
42
20
24
22
46
16
42
50+
20
32
24
52
18
40
24
36
28
58
60+
16
60
30
36
32
48
20
66
32
44
70+
24
70
24
72
36
40
36
60
24
78
80+
32
54
40
82
24
64
42
56
40
88
90+
24
72
44
60
46
72
32
96
42
60
Қасиеттері
, егер -- жай сан болса. Жекеше түрі: болғанда
;
, егер m мен өөзара жай болса. Яғни Эйлер функциясы мультипликативті;
, егер m мен өөзара жай болса. Бұл Эйлер теоремасы
болып табылады;

егер -- Ең Кіші Ортақ Еселік, aл - Ең Үлкен Ортақ Бөлгіш.

Асимптоталық байланыстар
мұндағы -- белгілі бір тұрақты;

Аналитикалық байланыстар
Эйлер функциясы Мёбиус функциясымен де байланысы бар:

Дирихле қатарын коэффициенттерімен Риман дзета-функциясы арқылы өрнектеуге болады:

Ламберт қатары қосындысын коэффициенттерімен:

мұндағы .
мұндағы .

Компьютерлік іске асырылуы
Си тілінде
Төмендегі функция көбейтіндісін есептейді. Бұл санын жай сандарға көбейткіштерге 2-ден бастап барлық сандарға бөлу арқылы іске асырылады; егер санға бөлінсе, бұл сан санын өшіріледі, ал нәтиже-көбейтінді сәйкесінше сол санға көбейтіліп өседі.

int phi(int n)
{
int ret = 1, p;
for(p = 2; p * p = n; p++)
{
if (n % p == 0)
{
n = p;
while(n % p == 0)
{
n = p;
ret *= p;
}
ret *= p - 1;
}
}
return n 1 ? ret * (n - 1) : ret;
}
VB.Net
Private Function phi(ByVal n As Integer) As Integer
Dim ret As Integer = 1, p As Integer = 2
For p = 2 To n p
If n Mod p = 0 Then
n = p
While n Mod p = 0
n = p
ret *= p
End While
ret *= p - 1
End If
Next
Return If(n 1, ret * (n - 1), ret)
End Function

Айталық m = p11p22 ... ptt , m1натурал саныны Канонды жіктелуі болсын. (m) = p11-1(p1-1)p22-1(p2-1)...ptt -1(pt-1) жне (1) = 1 болсын. Сонымен натурал аргументті функциясын анықтаймыз.
Анықтама 1 Жоғарыда көрсетілген әдіспен аныталған функциясы Эйлер функциясы деп аталады.
Анықтама 2 Эйлер функциясы n-нан кіші жне n-мен өөзара жай бүтін сандарды санына функцияны атайды. Функция (n) деп белгіленеді.
Мысала (10) = 4. Эйлер функциясыны келесі тамаша қасиеті бар: егер n = pq, мұндаы p және q - жай сандар, онда (n) = (p-1)(q-1)-ге те болады.
Теорема 1 (Эйлер) Кез-келген n модулі мен n-мен өөзара жай а саны үүшін келесі салыстыру a(n)-1 1(mod n).
Анықтама 3 Келесі ш шартты қанағаттандыратын функциясын мультипликативті деп атаймыз:
1) кез келген натурал сан үүшін анықталған;
2) (1) = 1;
3) егер (a,b) = 1 болса, онда (ab) = (a)(b).
Теорема 2 Эйлер функциясы - мултипликативті функция.
Дәлелдеуі. Айталық p11... ptt жне q11 ... qss сәйкесінше өөзара жай натурал m11 жне m21 өөзара жай сандарыны канонды жіктеулері болсын.
Онда p1, ..., pt сандарыны әрқайсысы q1, ..., qs сандарыны әрқайсысына өзгеше. Бұдан m1m2 канонды жіктеуі p11... ptt q11...qss. (m1m2) = (m1) (m2) тедеуі, Эйлер функциясыны анықтамасынан тікелей шығады. m1 = 1 немесе m2 = 1 үүшін берілген теңдеу дайын. Теорема дәлелденді.
Теорема 3 (m) саны 1, 2, ..., m санды тізбегіндегі m-мен өзара жай болатын сандарды санына те.
Дәлелдеуі. Дәлелдеме m1 саныны канонды жіктеуіндегі жай көбейткіш сандарды саны n бойынша математикалы индукция әдісі бойынша жүргізіледі. Теорема n = 0 (m = 1) жне n = 1 (m = p) үшін орындалады, мұндағы p - жай сан. Айта кетерлік жайт, i натурал саны mp - мен өзара жай болу үшін ол бір мезгілде m мен p сандарымен өзара жай болуы қажет және жеткілікті. 1, 2, ..., mp тізбегін талдау үшін ұзындыы m-ге те p тізбекшелеріне mk+1, mk+2, ..., mk+m-бөлеміз, мнда k = 0, 1, ..., p-1. Теорема 3-тен (mk + i,m) = (i, m) шығады. Осы теңдік пен осы индуктивті қайарымнан mk+1, mk+2, ..., mk+m тізбекшесінде m - мен өзара жай (m) сан бар. Осыдан 1, 2, ..., mp тізбегінде m - мен өзара жай (m)p сан бар. M p-а бөлінетін жағдайда, бұл сандар p-мен өзара жай, сонымен қатар mp санымен де өзара жай. Соны ескерту мен дайын тедік (mp) = (m)p қарастырылан жадайда теореманы айарымын дәлелдейді.
m-ні p-а бөлінбейтін жадайын арастыру алды. m-мен өзара жай (m)p сандарыны санынан осыларды p-а бөлінетіндеріні санын алып тастаса, іздеген (mp) санын табамыз. Ол сандар тек p, 2p, 3p, ..., mp сандарыны арасында ғана болуы мүмкін. Сондытан, m-мен өзара жай сандарды арасындаы p-а бөлінетіндері саны p, 2p, 3p, ..., mp сандарыны арасындаы m-мен өзара жай сандарды санына тең болады. Егер im жне (m,p) = 1 болғанда (ip,m) = (i,m) болатынын ескерсек, онда p, 2p, 3p, ..., mp сандарыны арасындағы m-мен өзара жай сандар саны. 1, 2, ..., m сандарыны арасындағы m-мен өзара жай сандар санына те, яғни индукция бойынша (m). қорыта келе, ізделінді (mp) = (m)p -- (m) = (m)(p-1). Теорема дәлелденді.
Эйлер функциясыны осы қасиетіні берілген дәлелдемесін Р.А.Сүйіндіков сынды.
Мысалдар: Берілген n натурал саны жай сан деп саналады, егер де ол тек өзіне ғана және 1-ге бөлінетін жағдайда a, n 2 натурал сандар өзара жай сандар деп саналады, егер оларды орта бөлгіштері болмаса.
1. n = 7
1 2 3 4 5 6 j(7) = 6.
2. n = p*q, p,q - жай сандар, j(n) = (p-1)*(q-1)
n = 33 = 11*3, j(33) = (11-1)(3-1) = 20.
3. n = kr
j(n) = (k-1)*kr-1, n = 8 = 23
j(8) = (2-1)*23-1 = 1*4 = 4.

2 Эйлер циклы

Графтар теориясына негіз болған есептердің бірі Кенигсберг көпірлері туралы есеп. 1-Суретте Леонард Эйлердің тұсындағы (17 ғасыр) XVII ғасырдағы Кенигсберг қаласының картасы салынған. Қала Прегель өзенінің екі жақ жағалауында және 2 аралда. орналасқан Аралдар өөзара және жағалаулармен 7 көпірмен жалғасқан. Кенигсберг тұрғындарының арасында сол кезде Кенигсберг көпірлері деп аталатын есеп кең тараған:
Есеп. Үйден шығып әр көпірмен бір рет қана жүріп үйге қайтып келуге болама ма деген сұрақ туады?

Сурет 1

Бұл есеп үүшін көпірлерден өтудің маңызы бар. Сондықтан көпірлердің орналасуын 2-суреттегі бағытталмаған мультиграфпен алмастыруға болады. Бұл графта Б, В төбелері өзеннің жағаларына, ал А, Г төбелері аралдар, ал мультиграфтың қабырғалары көпірлерге сәйкес келеді. Егер G графында оның барлық қабырғалары арқылы өтетін цикл табылса Кенигсберг туралы есеп шешілді деп есептеледі (Цикл деп бірде бір қабырға қайталанбайтын циклды маршрутты айтатынын еске саламыз). Демек графтар тілінде есептін қойылуы төмендегідей: Мультиграфта оның барлық қабырғалары болатындай цикл бар ма? Атақты ғалым-математик Л. Эйлер байланысты, бағытталмаған ... жалғасы

Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.