Дискреттик математика

Тапшырма(жеткиликсиз шилтеме) жок! Урааа!

Дискреттик математиканын темалары

Теориялык информатика

Татаалдуулук бул сорттоо тартиби сыяктуу алгоритмдердин убактысын изилдейт.

Эсептөөчү геометрия компьютердик алгоритмдерди геометриялык объекттерди көрсөтүүдө колдонот.

Теориялык информатика компьютерге тиешелүү дискреттик математиканын тармактарын камтыйт. Ал граф теориясына жана математикалык логикага көбүрөөк таянат. Теориялык информатика өзүнө алгоритмдерди жана маалымат структураларын изилдөөнү  камтыйт. Эсептөө жөндөмдүүлүгү принцибинде эсептелүүчү нерсени изилдеп, логика менен тыгыз байланышта болот, ал эми татаалдык убакытты жана эсептөөлөр тарабынан алынган башка ар кандай ресурстарды изилдейт. Автомат теориясы жана формалдуу тил теориясы эсептөө жөндөмдүүлүгү менен тыгыз байланышта. Эсептөөчү геометрия алгоритмдерди геометриялык маселелерге жана геометриялык объектилердин сүрөттөлүшүнө колдонот, ал эми компьютердик сүрөттөлүштүн анализи аларды сүрөттөрдүн чагылдырылышына колдонот. Теориялык информатика ар кандай үзгүлтүксүз эсептөө темаларын изилдөөнү да камтыйт.

Маалымат теориясы

Бул жерде бинардык түрдө берилген "Wikipedia" сөзүнүн ASCII коддору маалымат теориясында сөздү көрсөтүүнүн жолун, ошондой эле маалыматты иштетүү алгоритмдерин камсыз кылат.

Маалымат теориясы маалыматтын санын аныктайт. Эффективдүү жана ишенимдүү маалыматтарды берүү жана сактоо ыкмаларын иштеп чыгуу үчүн колдонулган коддоо теориясы менен  байланышта. Маалымат теориясына ошондой эле үзгүлтүксүз темалар да кирет: аналогдук сигналдар, аналогдук коддоо, аналогдук шифрлөө .

Логика

Логика негизги ой жүгүртүүнүн жана корутундунун, ошондой эле ырааттуулуктун, негиздүүлүктүн жана толуктуктун принциптерин изилдөө болуп саналат. Мисалы, логиканын көпчүлүк системаларында (интуициялык логикадан тышкары) Пирс мыйзамы ((( P → Q )→ P )→ P ) теорема. Классикалуу логика үчүн, аны чындык таблицасы менен оңой эле текшерип көрсө болот.

Логикалык формулалар дискреттик структуралар, далилдер сыяктуу эле, чектүү дарактарды1] же жалпысынан багытталган ациклдик график структураларын  түзөт. Логикалык формулалардын чындык маанилери, адатта, эки мааниге чектелген чектүү көптүктү түзөт: чыныгы жана жалган, бирок логика да үзгүлтүксүз мааниге ээ болушу мүмкүн. Чексиз далил дарактары же чексиз туунду дарактар сыяктуу түшүнүктөр да изилденген, [4] мис., чексиз логика .

Көптүктөр теориясы

Көптүк деп кандайдыр бир объекттердин жыйындысын түшүнөбүз. Мисалы, бүтүн сандардын жыйндысы, латын алфавитинин тамгалары, университеттеги студенттер, асмандагы жылдыздар, дарыялар, көлдөр, тоолор, автоунаалар ж.б. обьекттер көптүк түшүнүгүнө мисал боло алат. Мындан, көптүктү түзгөн обьекттердин жаратылышынын ар түрдүүлүгүн жана көптүктөр теориясынын колдонулушунун кеңири экендигин байкайбыз.

Дискреттик математикада эсептелүүчү көптүктөр (анын ичинде чектүү көптүктөр ) негизги көңүл бурат. Көптүктү түзгөн объекттер көптүктүн элементтери деп аталат. Демек, ар бир көптүк элементтерден турат. Элементтеринин саны чектүү болгон көптүктү чектүү көптүк деп, ал эми элементтеринин саны чексиз болгон көптүктү чексиз көптүк деп айтабыз.. Чынында эле, сүрөттөмө топтом теориясынын заманбап иштери салттуу үзгүлтүксүз математиканы кеңири колдонот.

Комбинаторика

Комбинаторика дискреттик структураларды бириктирүү же жайгаштыруу жолдорун изилдейт. Эсептөөчү комбинаторика белгилүү бир комбинатордук объекттердин санын эсептөөгө топтолот - мисалы, он эки жол менен алмаштырууларды, комбинацияларды жана бөлүктөрдү эсептөө үчүн бирдиктүү негизди түзөт. Аналитикалык комбинаторика комплекстүү анализдин жана ыктымалдуулук теориясынын куралдарын колдонуп, комбинатордук структураларды санап чыгат. Натыйжаларды сүрөттөө үчүн ачык комбинатордук формулаларды жана генерациялоо функцияларын колдонуп, санак комбинаторикасынан айырмаланат, аналитикалык комбинаторика болсо асимптотикалык формулаларды алууну көздөйт. Топологиялык комбинаторика топологиядан жана алгебралык топологиядан / комбинаторикада комбинатордук топологиядан техникаларды колдонот. Бөлүү теориясы бүтүн бөлүмдөргө байланыштуу ар кандай санап чыгуу жана асимптотикалык маселелерди изилдейт жана q-сериялары, атайын функциялар жана ортогоналдык көп мүчөлөр менен тыгыз байланышкан. Башында сандар теориясынын жана анализинин бир бөлүгү болгон бөлүү теориясы азыр комбинаториканын бир бөлүгү болуп эсептелет. Тартип теориясы жарым-жартылай иреттелген чектүү жана чексиз  көптүктөрдү изилдөөсү болуп саналат.

График теориясы

График теориясы топ теориясы менен тыгыз байланышта. Бул кесилген тетраэдр графиги кезектешип турган A ₄ тобуна тиешелүү.

График теориясы, графиктерди жана тармактарды изилдөө, адатта комбинаториканын бир бөлүгү катары категорияга кирет. Бирок, ал кыйла кеңейип, өз алдынча изилдөө тармагы катары өзгөчөлөнүп, өзүнүн уникалдуу проблемаларынын комплексин иштеп чыкты. Графиктер дискреттик математикада изилдөөнүн негизги объектиси катары кызмат кылат, алар табигый жана адам жасаган структуралар үчүн кеңири жайылган моделдер болуп саналат. Алар физикалык, биологиялык жана социалдык системалардагы мамилелердин жана динамикалык процесстердин ар кандай түрлөрүн сунуштайт. Информатикада графиктер байланыш тармактарын, маалыматтарды уюштурууну, эсептөө приборлорун жана эсептөө агымын жана башка тиркемелерди көрсөтүү үчүн кызмат кылат. Математикада алар геометрияда жана топологиянын белгилүү тармактарында, мисалы түйүн теориясында пайдалуу болот. Алгебралык график теориясы топ теориясы менен тыгыз байланышты көрсөтөт, ал эми топологиялык граф теориясы топология менен тыгыз байланышты көрсөтөт. Үзгүлтүксүз графиктер бар болсо да, граф теориясындагы изилдөөлөрдүн көпчүлүгү дискреттик математиканын чөйрөсүндө жайгашкан.

Кара пикселдер негизги сандарды көрсөткөн Улам сандардын спиралы . Бул диаграммада жөнөкөй сандардын бөлүштүрүлүшүнүн үлгүлөрү көрсөтүлөт.

Сандар теориясы же жогорку арифметика — алгач бүтүн сандардын касиеттерин изилдеген математиканын бөлүмү. Заманбап сандар теориясында сандардын башка түрлөрү каралат — мисалы, алгебралык жана трансценденттик, ошондой эле бүтүн сандардын арифметикасы жана аларды жалпылоо менен байланышкан ар кандай келип чыккан функциялар.

Алгебралык структуралар

Алгебралык структуралар дискреттик мисалдар катары жана үзгүлтүксүз мисалдар катары кездешет. Дискреттик алгебраларга ушулар кирет: логикалык дарбазаларда , программалоодо колдонулган буль алгебрасы ; маалымат базаларында колдонулган реляциялык алгебра ; формалдуу тилдердин теориясында дискреттик жарым группалар жана моноиддер пайда болот.

Үзгүлтүксүз математиканын дискреттик аналогдору

Үзгүлтүксүз математикада дискреттүү версиялары да бар көптөгөн концепциялар жана теориялар бар, мисалы, дискреттүү оптимизация, дискреттик логарифм дискреттик эсептөө, дискреттүү Фурье түрлендіру, дискреттүү Морзе теориясы дискреттик геометрия, дискреттик логарифм, дискреттүү дифференциалдык геометрия, дискреттик вектор<span typeof="mw:Entity" id="mwARo"> </span>чаралар дискреттүү тышкы эсептөө, дискреттүүлүк, дискреттик оптимизация.

Чектүү айырмачылыктарды эсептөө, дискреттик анализ жана дискреттик эсептөө

Дискреттик эсептөө жана чектүү айырмачылыктар чөйрөсүндө бүтүн сандардын диапазонунда аныкталган функция адатта ырааттуулук деп аталат. Ырааттуулуктар чектүү маалымат топтомдорунан же дискреттик динамикадагы чексиз системалардан келип чыгышы мүмкүн. Бул функциялар чектүү тизме аркылуу (алардын домени чектелүү болгондо) же алардын жалпы терминин туюндурган формула менен ачык түрдө белгилениши мүмкүн. Же болбосо, алар кайталануу мамилелери же айырма теңдемелери аркылуу кыйыр түрдө сүрөттөлүшү мүмкүн. Айырма теңдемелери дифференциалдык теңдемелердин түзүлүшүн чагылдырат, бирок ырааттуу мүчөлөрдүн ортосундагы диспропорцияны эсептөө менен иштейт. Алар дифференциалдык теңдемелерге окшош максаттарга же аларга жакындоо катары же өз алдынча изилдөөнүн предмети катары кызмат кылат.

Дифференциалдык теңдемелерде колдонулган көптөгөн түшүнүктөрдүн жана ыкмалардын айырмачылык теңдеме чөйрөсүндө окшош окшоштуктары бар. Мисалы, гармоникалык анализдеги интегралдык трансформациялар үзгүлтүксүз функцияларды же аналогдук сигналдарды текшерүүнү жеңилдеткендей, дискреттик трансформациялар да дискреттик функциялар же санариптик сигналдар үчүн ушундай ролду аткарат. Мындан тышкары, дискреттик метрикалык мейкиндиктерден тышкары, дискреттүү топологиялык мейкиндиктер, чектүү метрикалык мейкиндиктер жана чектүү топологиялык мейкиндиктер сыяктуу кеңири категориялар бар.

Убакыт масштабындагы эсептөө айырма теңдемелеринин жана дифференциалдык теңдемелердин теорияларын бириктирген бирдиктүү негизди сунуш кылат. Ал дискреттик жана үзгүлтүксүз маалымат агымдарын бир эле учурда моделдештирүү зарыл болгон дисциплиналардагы колдонмолорду табат. Мындай сценарийлерди чечүүнүн дагы бир ыкмасы гибриддик динамикалык системалардын концепциясы аркылуу.

Дискреттик геометрия

Дискреттик геометрия жана комбинатордук геометрия геометриялык объектилердин дискреттүү жыйнактарынын комбинатордук касиеттери жөнүндө. Дискреттик геометрияда көптөн бери айтылып келе жаткан тема учактын плиткасы.

Алгебралык геометрияда ийри сызык түшүнүгүн дискреттик геометрияларга чейин кеңейтүүгө болот, ал чектүү талаалардагы полиномдук шакекчелердин спектрлерин ал талаалардын үстүндөгү аффиндик мейкиндиктердин моделдери катары кароо аркылуу. Кийинчерээк, бул мейкиндиктердин ичиндеги ийри сызыктар башка шакекчелердин суб сорттору же спектрлери менен аныкталат. Ийри сызыктар бар мейкиндиктеги чектүү чекиттерге карабастан, алар жөн гана чекиттердин жыйындысы эмес. Мисалы $V(x-c)\subset \operatorname {Spec} K[x]=\mathbb {A} ^{1}$ үчүн $K$ катары да изилдөөгө болот $\operatorname {Spec} K[x]/(x-c)\cong \operatorname {Spec} K$, чекит же спектр катары $\operatorname {Spec} K[x]_{(x-c)}$ жергиликтүү шакекченин (xc), анын тегерегиндеги кошуна менен бирге чекит. Алгебралык сорттор Зариски тангенс мейкиндиги деп аталган так мейкиндиктин так аныкталган түшүнүгүнө ээ. Бул өзгөчөлүк эсептөөнүн көптөгөн аспектилери чектүү орнотууларда да актуалдуу болууга мүмкүндүк берет.

Дискреттүү моделдөө

Колдонмо математикада дискреттик моделдөө үзгүлтүксүз моделдөөнүн теңдеши катары кызмат кылат. Бул маалыматтарга дискреттик формулаларды орнотууну камтыйт. Бул моделдөө ыкмасында кайталануу мамилелери көп колдонулат. Дискреттөө үзгүлтүксүз моделдерди жана теңдемелерди дискреттик формаларга айландырууну камтыйт, көбүнчө болжолдоо аркылуу эсептөөлөрдү жеңилдетүү. Сандык талдоо бул процесстин маанилүү мисалы болуп саналат.

График теориясы боюнча көптөгөн изилдөөлөр ушул сыяктуу бардык карталарды төрт гана түс менен боёсо болорун далилдөө аракети түрткү болгон, ошондуктан бир түстөгү эч бир аймак бир чети бөлүштүрбөйт. Муну Кеннет Аппел жана Вольфганг Хакен 1976-жылы далилдешкен .

Дискреттик математиканын эволюциясы чөйрөнүн ар кайсы тармактарында көңүл бурган көптөгөн татаал көйгөйлөр менен коштолгон. График теориясынын алкагында, төрт түс теоремасынын негиздүүлүгүн аныктоо аракети менен кеңири изилдөө аракеттери түрткү болду. Алгач 1852-жылы сунуш кылынган, ал 1976-жылга чейин далилденбеген бойдон калууда, акырында Кеннет Аппел жана Вольфганг Хакен компьютерлердин олуттуу жардамы менен анын чындыгын көрсөтүшкөн.

Логика чөйрөсүндө Дэвид Гильберттин 1900-жылы белгиленген ачык суроолор тизмесиндеги экинчи маселеси арифметика аксиомаларынын ырааттуулугун орнотууга аракет кылган. Бирок, 1931-жылы түзүлгөн Годелдин экинчи толук эместик теоремасы, жок эле дегенде, арифметика чөйрөсүндө бул максатка жетүү мүмкүн эместигин көрсөттү. Ал эми Гильберттин онунчу маселеси бүтүн сандуу коэффициенттери бар спецификалык көп мүчөлүү Диофантин теңдемесинин бүтүн сандык чечимге ээ экендигин аныктоого багытталган. Юрий Матиасевичтин 1970-жылдагы жетишкендиги мындай чечкиндуу-луктун болушу мумкун эмес экендигин аныктады.

Экинчи дүйнөлүк согуш маалында, немис билдирүүлөрүн чечмелөө императиви криптографияда жана теориялык информатикада прогресске түрткү болгон. Алан Тюрингдин "Эсептелүүчү сандар жөнүндө" аттуу таасирдүү эмгеги Англиядагы Блетчли паркында биринчи программалануучу санариптик электрондук компьютерди иштеп чыгууга жетекчилик кылган. Криптографиянын мааниси Кансыз согуш дооруна чейин сакталып, кийинки ондогон жылдардагы ачык ачкыч криптографиясы сыяктуу негизги жетишкендиктерге алып келди. Телекоммуникация тармагы ошондой эле дискреттик математикадагы прогресстин катализатору болуп калды, айрыкча графика теориясы жана маалымат теориясы сыяктуу тармактарда. Логикалык билдирүүлөрдү формалдуу текшерүү коопсуздук-критикалык программалык камсыздоо тутумдарын иштеп чыгуу үчүн чечүүчү мааниге ээ болуп, автоматташтырылган теореманы далилдөөдөгү прогресске түрткү болду.

Эсептөөчү геометрия заманбап видео оюндарга жана компьютердик дизайн куралдарына интеграцияланган компьютердик графикада маанилүү роль ойнойт.

Дискреттик математиканын ар кандай чөйрөлөрү, айрыкча теориялык информатика, график теориясы жана комбинаторика жашоо дарагын түшүнүүгө байланышкан татаал биоинформатика көйгөйлөрүн чечүүдө негизги ролду ойнойт.

Азыркы учурда теориялык информатикадагы эң белгилүү чечилбеген маселелердин бири P жана NP татаалдык класстарынын ортосундагы өз ара байланыштын тегерегинде айланган P = NP проблемасына тиешелүү. Клей Математика Институту алты кошумча математикалык маселе боюнча сыйлыктар менен бирге алгачкы жарактуу далил үчүн 1 миллион долларлык сыйлыкты койду.

Ошондой эле караңыз

• Дискреттик математиканын конспектиси

Шилтемелер

1. Richard Johnsonbaugh, Discrete Mathematics, Prentice Hall, 2008.
2. Franklin, James (2017). "Discrete and continuous: a fundamental dichotomy in mathematics". Journal of Humanistic Mathematics 7 (2): 355–378. doi:10.5642/jhummath.201702.18. https://scholarship.claremont.edu/jhm/vol7/iss2/18/. Retrieved 30 June 2021. 
3. Discrete Structures: What is Discrete Math?.