Mengulas Lebih Dalam Tentang Matematika Diskrit – Matematika diskrit merupakan sebuah studi tentang bagan matematika yang dasarnya ialah diskrit daripada kontinu . Berbeda dengan bilangan asli yang memiliki sifat memvariasikan “lancar”, objek yang dipelajari dalam matematika diskrit – seperti bilangan bulat , grafik , dan pernyataan dalam logika – tidak bervariasi dengan mulus dengan cara ini, tetapi memiliki perbedaan , nilai terpisah. Oleh karena itu, matematika diskrit mengecualikan topik dalam “matematika berkelanjutan” seperti kalkulus atau geometri Euclidean.

Mengulas Lebih Dalam Tentang Matematika Diskrit

transitionmathproject – Objek diskrit sering dapat dihitung dengan bilangan bulat. Secara lebih formal, matematika diskrit telah dicirikan sebagai cabang matematika yang berhubungan dengan himpunan yang dapat dihitung (himpunan berhingga atau himpunan dengan kardinalitas yang sama dengan bilangan asli). Namun, tidak ada definisi pasti dari istilah “matematika diskrit”. Memang, matematika diskrit dijelaskan kurang oleh apa yang disertakan daripada apa yang dikecualikan: kuantitas terus menerus bervariasi dan gagasan terkait.

Baca Juga : Ilmu linier proyektif Di Matematika

Himpunan objek yang dipelajari dalam matematika diskrit bisa terbatas atau tak terbatas. Istilah matematika hingga kadang-kadang diterapkan pada bagian bidang matematika diskrit yang berhubungan dengan himpunan hingga, khususnya bidang yang relevan dengan bisnis. Penelitian matematika diskrit meningkat pada paruh kedua abad ke-20, sebagian karena perkembangan komputer digital langkah-langkah diskrit dan menyimpan data dalam bit diskrit. Konsep dan simbol dalam matematika diskrit adalah belajar dan mendeskripsikan Objek dan masalah dalam cabang ilmu komputer, seperti algoritma komputer, bahasa pemrograman , kriptografi , pembuktian teorema otomatis , dan pengembangan perangkat lunak . Sebaliknya, implementasi komputer signifikan dalam menerapkan ide-ide dari matematika diskrit ke masalah dunia nyata, seperti dalam riset operasi.

Meskipun objek utama studi dalam matematika diskrit adalah objek diskrit, metode analitik dari matematika kontinu sering digunakan juga. Dalam kurikulum universitas, “Matematika Diskrit” muncul pada 1980-an, awalnya sebagai kursus pendukung ilmu komputer; isinya agak serampangan pada saat itu. Kurikulum kemudian dikembangkan bersama dengan upaya ACM dan MAA menjadi mata pelajaran yang pada dasarnya dimaksudkan untuk Menumbuhkan kedewasaan siswa dalam matematika tahun pertama; Oleh karena itu, saat ini merupakan prasyarat untuk jurusan matematika di beberapa universitas juga. Beberapa buku teks matematika diskrit tingkat sekolah menengah telah muncul juga. Pada tingkat ini, matematika diskrit kadang-kadang dilihat sebagai kursus persiapan, tidak seperti prakalkulus dalam hal ini.

The Fulkerson Prize diberikan untuk kertas yang beredar dalam matematika diskrit.

Tantangan besar, dulu dan sekarang

Sejarah matematika diskrit telah melibatkan sejumlah masalah yang menantang yang telah memusatkan perhatian dalam bidang lapangan. Dalam teori graf, banyak penelitian dimotivasi oleh upaya untuk membuktikan teorema empat warna , pertama kali dinyatakan pada tahun 1852, tetapi tidak terbukti sampai tahun 1976 (oleh Kenneth Appel dan Wolfgang Haken, menggunakan bantuan komputer yang substansial).

Dalam logika , yang Masalah kedua pada David Hilbert daftar ‘s open masalah yang disajikan pada tahun 1900 adalah untuk membuktikan bahwa aksioma dari aritmatika yang konsisten . Teorema ketidaklengkapan kedua Gödel , dibuktikan pada tahun 1931, menunjukkan bahwa ini tidak mungkin – setidaknya tidak dalam aritmatika itu sendiri. Masalah kesepuluh Hilbert adalah menentukan apakah persamaan Diophantine polinomial yang diberikan dengan koefisien bilangan bulat memiliki solusi bilangan bulat. Pada tahun 1970, Yuri Matiyasevich membuktikan bahwa ini tidak dapat dilakukan .

Kebutuhan untuk memecahkan kode Jerman dalam Perang Dunia II menyebabkan kemajuan dalam kriptografi dan ilmu komputer teoretis , dengan komputer elektronik digital pertama yang dapat diprogram dikembangkan di Bletchley Park Inggris dengan bimbingan Alan Turing dan karya maninya, On Computable Numbers. Pada saat yang sama, kebutuhan militer memotivasi kemajuan dalam riset operasi . The Perang Dingin berarti bahwa kriptografi tetap penting, dengan kemajuan mendasar seperti kriptografi kunci publikdikembangkan pada dekade-dekade berikutnya. Riset operasi tetap penting sebagai alat dalam bisnis dan manajemen proyek, dengan metode jalur kritis dikembangkan pada 1950-an. Industri telekomunikasi juga telah mendorong kemajuan dalam matematika diskrit, khususnya dalam teori graf dan teori informasi . Verifikasi formal pernyataan dalam logika telah diperlukan untuk pengembangan perangkat lunak dari sistem keselamatan-kritis , dan kemajuan dalam membuktikan teorema otomatis telah didorong oleh kebutuhan ini.

Geometri komputasi telah menjadi bagian penting dari grafik komputer yang dimasukkan ke dalam video game modern dan alat desain berbantuan komputer . Beberapa bidang matematika diskrit, khususnya ilmu komputer teoretis, teori graf, dan kombinatorik , penting dalam mengatasi masalah bioinformatika yang menantang terkait dengan pemahaman pohon kehidupan . Saat ini, salah satu masalah terbuka paling terkenal dalam ilmu komputer teoretis adalah masalah P = NP , yang melibatkan hubungan antara kelas kompleksitas P dan NP . The Institut Matematika Clay telah menawarkan $ 1 juta USD hadiah untuk bukti yang benar pertama, bersama dengan hadiah untuk enam masalah matematika lainnya .

Topik dalam matematika diskrit

Ilmu komputer teoretis

Ilmu komputer teoretis mencakup bidang matematika diskrit yang relevan dengan komputasi. Ini sangat mengacu pada teori grafik dan logika matematika . Termasuk dalam ilmu komputer teoretis adalah studi tentang algoritma dan struktur data. Computability mempelajari apa yang dapat dihitung pada prinsipnya, dan memiliki hubungan dekat dengan logika, sedangkan kompleksitas mempelajari waktu, ruang, dan sumber daya lain yang diambil oleh komputasi. Teori automata dan teori bahasa formal berkaitan erat dengan komputabilitas. Jaringan petri dan aljabar proses digunakan untuk memodelkan sistem komputer, dan metode dari matematika diskrit digunakan dalam menganalisis VLSIsirkuit elektronik. Geometri komputasional menerapkan algoritme untuk masalah geometris, sedangkan analisis citra komputer menerapkannya pada representasi gambar. Ilmu komputer teoretis juga mencakup studi tentang berbagai topik komputasi berkelanjutan.

Teori informasi

Teori informasi melibatkan kuantifikasi informasi . Terkait erat adalah teori pengkodean yang digunakan untuk merancang metode transmisi dan penyimpanan data yang efisien dan andal. Teori informasi juga mencakup topik-topik yang terus menerus seperti: sinyal analog , analog coding , enkripsi analog .

Logika

Logika adalah studi tentang prinsip-prinsip penalaran dan kesimpulan yang valid , serta konsistensi , kesehatan , dan kelengkapan . Misalnya, di sebagian besar sistem logika (tetapi tidak dalam logika intuisi ) Hukum Peirce ((( P → Q )→ P )→ P ) adalah teorema. Untuk logika klasik, dapat dengan mudah diverifikasi dengan tabel kebenaran . Studi tentang bukti matematis sangat penting dalam logika, dan memiliki aplikasi untuk pembuktian teorema otomatis dan verifikasi formal perangkat lunak.

Rumus logika adalah struktur diskrit, seperti halnya bukti , yang membentuk pohon hingga atau, lebih umum, struktur grafik asiklik terarah (Gabungkan satu atau lebih dengan setiap langkah penalaran cabang premis untuk memberikan satu kesimpulan). Nilai kebenaran dari rumus logika biasanya membentuk himpunan berhingga, umumnya terbatas pada dua nilai: benar dan salah , tetapi logika juga dapat bernilai kontinu, misalnya logika fuzzy . Konsep seperti pohon bukti tak terbatas atau pohon turunan tak terbatas juga telah dipelajari, misalnyalogika tak terbatas .

Teori himpunan

Teori himpunan adalah cabang matematika yang mempelajari himpunan , yang merupakan kumpulan objek, seperti {biru, putih, merah} atau himpunan (tak hingga) dari semua bilangan prima . Himpunan yang terurut sebagian dan himpunan dengan relasi lain memiliki penerapan di beberapa area. Dalam matematika diskrit, himpunan yang dapat dihitung (termasuk himpunan hingga ) adalah fokus utama. Awal teori himpunan sebagai cabang matematika biasanya ditandai dengan karya Georg Cantor yang membedakan berbagai jenis himpunan tak hingga , dimotivasi oleh studi deret trigonometri, dan perkembangan lebih lanjut dari teori himpunan tak hingga berada di luar ruang lingkup diskrit. matematika. Memang, karya kontemporer dalam teori himpunan deskriptif membuat ekstensif menggunakan matematika kontinu tradisional.

Kombinatorik

Kombinatorika mempelajari cara di mana struktur diskrit dapat digabungkan atau diatur. Kombinatorik enumeratif berkonsentrasi pada penghitungan jumlah objek kombinatorial tertentu – misalnya cara dua belas kali lipat menyediakan kerangka kerja terpadu untuk menghitung permutasi , kombinasi , dan partisi . Kombinatorika analitik menyangkut enumerasi (yaitu, menentukan jumlah) struktur kombinatorial menggunakan alat dari analisis kompleks dan teori probabilitas . Berbeda dengan kombinatorik enumeratif yang menggunakan rumus kombinatorial eksplisit dan fungsi pembangkituntuk menggambarkan hasil, kombinatorik analitik bertujuan untuk memperoleh rumus asimtotik .

Teori desain adalah studi tentang desain kombinatorial , yang merupakan kumpulan himpunan bagian dengan sifat perpotongan tertentu . Teori partisi mempelajari berbagai masalah enumerasi dan asimtotik yang terkait dengan partisi bilangan bulat , dan terkait erat dengan deret q , fungsi khusus dan polinomial ortogonal . Awalnya bagian dari teori bilangan dan analisis , teori partisi sekarang dianggap sebagai bagian dari kombinatorik atau bidang independen. Teori keteraturan adalah studi tentanghimpunan terurut sebagian , baik berhingga maupun tak berhingga.

Teori Graf

Teori graf, studi tentang graf dan jaringan , sering dianggap sebagai bagian dari kombinatorik, tetapi telah berkembang cukup besar dan cukup berbeda, dengan jenis masalahnya sendiri, untuk dianggap sebagai subjek dalam dirinya sendiri. Grafik adalah salah satu objek utama studi dalam matematika diskrit. Mereka adalah salah satu model yang paling umum dari struktur alami dan buatan manusia. Mereka dapat memodelkan banyak jenis hubungan dan dinamika proses dalam sistem fisik, biologis dan sosial. Dalam ilmu komputer, mereka dapat mewakili jaringan komunikasi, organisasi data, perangkat komputasi, aliran komputasi, dll. Dalam matematika, mereka berguna dalam geometri dan bagian topologi tertentu , misalnya teori simpul .Teori graf aljabar memiliki kaitan erat dengan teori grup. Ada juga grafik kontinu ; namun, untuk sebagian besar, penelitian dalam teori graf termasuk dalam domain matematika diskrit.

Probabilitas

Teori probabilitas diskrit berkaitan dengan peristiwa yang terjadi dalam ruang sampel yang dapat dihitung . Misalnya, pengamatan hitung seperti jumlah burung dalam kawanan hanya terdiri dari nilai bilangan asli {0, 1, 2, …}. Di sisi lain, pengamatan terus menerus seperti bobot burung terdiri dari nilai bilangan real dan biasanya akan dikombinasikan dengan distribusi probabilitas kontinu seperti normal . Distribusi probabilitas diskrit dapat digunakan untuk mendekati distribusi kontinu dan sebaliknya. Untuk situasi yang sangat terbatas seperti melempar dadu atau eksperimen dengan tumpukan kartu , menghitung probabilitas kejadian pada dasarnya adalah kombinatorik enumeratif .

Teori bilangan

Teori bilangan berkaitan dengan sifat-sifat bilangan secara umum, khususnya bilangan bulat . Ini memiliki aplikasi untuk kriptografi dan kriptanalisis , khususnya yang berkaitan dengan aritmatika modular , persamaan diophantine , kongruensi linier dan kuadrat, bilangan prima dan pengujian primalitas . Aspek diskrit lain dari teori bilangan termasuk geometri bilangan . Dalam teori bilangan analitik , teknik dari matematika kontinu juga digunakan. Topik yang melampaui objek diskrit meliputi bilangan transendental , pendekatan diophantine , analisis p-adik danbidang fungsi .

Struktur aljabar

Struktur aljabar terjadi sebagai contoh diskrit dan contoh kontinu. Aljabar diskrit meliputi: aljabar boolean yang digunakan dalam gerbang logika dan pemrograman; aljabar relasional yang digunakan dalam database ; versi diskrit dan terbatas dari grup , ring dan field penting dalam teori pengkodean aljabar ; semigrup diskrit dan monoid muncul dalam teori bahasa formal .

Kalkulus perbedaan hingga, kalkulus diskrit atau analisis diskrit

Sebuah fungsi yang didefinisikan pada interval bilangan bulat biasanya disebut barisan . Urutan bisa menjadi urutan terbatas dari sumber data atau urutan tak terbatas dari sistem dinamis diskrit . Fungsi diskrit seperti itu dapat didefinisikan secara eksplisit oleh sebuah daftar (jika domainnya berhingga), atau dengan rumus untuk suku umumnya, atau dapat diberikan secara implisit oleh relasi perulangan atau persamaan perbedaan .

Persamaan perbedaan mirip dengan persamaan diferensial , tetapi menggantikan diferensiasidengan mengambil selisih antara suku-suku yang berdekatan; mereka dapat digunakan untuk memperkirakan persamaan diferensial atau (lebih sering) dipelajari dengan sendirinya. Banyak pertanyaan dan metode tentang persamaan diferensial memiliki padanan untuk persamaan perbedaan. Misalnya, di mana ada transformasi integral dalam analisis harmonik untuk mempelajari fungsi kontinu atau sinyal analog, ada transformasi diskrit untuk fungsi diskrit atau sinyal digital. Selain metrik diskrit, ada ruang metrik diskrit atau terhingga yang lebih umum dan ruang topologi terhingga .

Geometri

Geometri diskrit dan geometri kombinatorial adalah tentang sifat-sifat kombinatorial dari kumpulan objek geometris diskrit . Topik lama dalam geometri diskrit adalah ubin pesawat . Geometri komputasional menerapkan algoritma untuk masalah geometris.

Topologi

Meskipun topologi adalah bidang matematika yang memformalkan dan menggeneralisasi gagasan intuitif tentang “deformasi terus-menerus” objek, itu memunculkan banyak topik diskrit; ini dapat dikaitkan sebagian dengan fokus pada invarian topologi , yang biasanya mengambil nilai diskrit. Lihat kombinasi topologi , teori graph topologi , kombinatorika topologi , topologi komputasi , ruang topologi diskrit , ruang topologi yang terbatas , topologi (kimia) .

Riset operasi

Riset operasi menyediakan teknik untuk memecahkan masalah praktis di bidang teknik, bisnis, dan bidang lainnya — masalah seperti mengalokasikan sumber daya untuk memaksimalkan keuntungan, dan menjadwalkan aktivitas proyek untuk meminimalkan risiko. Teknik riset operasi meliputi pemrograman linier dan bidang optimasi lainnya , teori antrian , teori penjadwalan , dan teori jaringan . Riset operasi juga mencakup topik-topik berkelanjutan seperti proses Markov waktu-kontinyu , martingales -waktu-kontinyu , optimasi proses , dan teori kontrol kontinu dan hibrid .

Analog diskrit dari matematika kontinu

Baca Juga : Teori Homologi Dalam Matematika

Ada banyak konsep dalam matematika kontinu yang memiliki versi diskrit, seperti kalkulus diskrit , distribusi probabilitas diskrit , transformasi Fourier diskrit , geometri diskrit , logaritma diskrit , diskrit geometri diferensial , kalkulus eksterior diskrit , teori Morse diskrit , persamaan perbedaan , sistem dinamis diskrit , dan ukuran vektor diskrit . Dalam matematika terapan , pemodelan diskrit adalah analog diskrit dari pemodelan kontinu . Dalam pemodelan diskrit, rumus diskrit cocok dengan data . Metode umum dalam bentuk pemodelan ini adalah dengan menggunakan relasi rekurensi .

Dalam geometri aljabar , konsep kurva dapat diperluas untuk geometri diskrit dengan mengambil spektrum dari banyak berdering lebih bidang terbatas untuk menjadi model dari ruang affine atas lapangan itu, dan membiarkan subvarieties atau spektrum dari cincin lain memberikan kurva yang terletak pada ruang itu. Meskipun ruang di mana kurva muncul memiliki jumlah titik yang terbatas, kurva tidak begitu banyak set titik sebagai analog dari kurva dalam pengaturan terus menerus. Misalnya, setiap titik dari bentuk V(xc)\subset \operatorname {Spec} K[x]=\mathbb {A}1 untuk K suatu bidang dapat dipelajari baik sebagai \operatorname {Spec} K[x]/(xc)\cong \operatorname {Spec} K, titik, atau sebagai spektrum \nama operator {Spec} K[x]_{(xc)}dari cincin lokal di (xc) , bersama titik dengan lingkungan sekitarnya. Varietas aljabar juga memiliki gagasan yang terdefinisi dengan baik tentang ruang singgung yang disebut ruang singgung Zariski , membuat banyak fitur kalkulus dapat diterapkan bahkan dalam pengaturan yang terbatas.