Perkenalan Ilmu Komputer
Hola, disini aku akan spill materi perkenalan ilmu komputer yang biasa diajarkan di perguruan tinggi untuk mahasiswa semester 1 di jurusan ilmu komputer atau informatika. Materinya aku ambil dari kampusku dan aku interpretasi ulang biar gak melanggar copyright. Semoga membantu 🙏
Daftar bab
- Part 1
- Part 2 (coming not so soon™)
Apa itu ilmu komputer atau informatika?
Tergantung kamu tanya siapa, informatika bisa didefinisikan dengan berbeda.
“Computer science has such intimate relations with so many other subjects that it is hard to see it as a thing in itself.”
“Computer science = engineering”
“Computing is a 4th great domain of science alongside the physical, life, and social sciences.”
Banyak yang bingung apakah ilmu komputer itu sains atau teknik. Di dunia modern, ilmu komputer umumnya mencakup penemuan (bagian dari sains) dan implementasi (bagian dari teknik) dalam bidang pemrosesan informasi. Jadi ilmu komputer adalah sains dan teknik disaat yang sama.
Algoritma
Algoritma dan struktur data dapat ditemukan di mana-mana dalam ilmu komputer. Daripada aku jelasin, mending kita langsung liat contoh pemikiran algoritmik. For fun aja!
The Two Egg Problem (Masalah Dua Telur)
Mari kita asumsi ada gedung dengan tinggi 100 lantai. Lalu kita punya dua telur. Telur ini tidak bisa menjadi “lemah” atau retak. Dia hanya bisa pecah atau tidak pecah. Kedua telur tersebut identis. Sekarang kita ingin tau lantai tertinggi dimana telur tersebut tidak pecah jika dijatuhkan.
Aku akan kasih contoh solusi yang mungkin langsung terpikir (disebut solusi naïve) dan solusi lain yang lebih bagus.
Kita mulai dari lantai 1. Lalu kita jatuhkan satu telur.
Jika pecah, maka kita tau bahwa lantai tertinggi telur tidak pecah adalah (lantai sekarang - 1)
Jika tidak pecah, maka kita naik 1 lantai.
Solusi diatas hanya butuh 1 telur. Tetapi di kasus terburuk, kita butuh untuk mengetes 100 lantai (semua lantai). Apakah tidak ada solusi yang lebih baik, mengingat kita punya 2 telur?
Kita mulai dari tengah gedung (lantai 50). Lalu kita jatuhkan 1 telur.
Jika pecah, maka kita lanjutkan dengan solusi sebelumnya (solusi 1) dari lantai 1. Dengan ini sekarang kita hanya perlu mencoba maximal 50 lantai, karena kita tahu jawabannya lebih kecil daripada lantai 50.
Jika tidak pecah, maka kita lanjutkan dengan solusi sebelumnya (solusi 1) dari lantai 51.
Di solusi kedua, kita tidak mencoba tiap lantai satu persatu. Kita langsung membagi jumlah lantai yang harus dicoba menjadi 2. Sehingga di kasus terburuk, kita butuh 50 (jika telur pertama pecah) kali mencoba atau 51 kali (jika telur pertama tidak pecah).
Solusi yang optimal adalah solusi dimana kita bisa tahu jawabannya dengan angka percobaan minimal. Kedua solusi diatas bukan solusi yang optimal. Nah sekarang coba kamu pikir dulu, bagaimanakah solusi dimana total mencoba kita terkecil (solusi optimal)?
Kalo kamu udah ada jawaban (gaharus bener! yang penting ada solusi kamu sendiri), coba cek jawaban dan penjelasannya disini. By the way, kalo gak paham kenapa jawabannya kayak gitu gapapa kok! Tujuannya disini hanya melihat contoh cara berpikir algoritmik yang akan sering dipakai di ilmu komputer.
Program vs Algoritma
Apa bedanya program dengan algoritma?
- Algoritma menjelaskan, dalam unsur-unsur dasarnya, apa yang harus dijalankan oleh komputer. Algoritma berfokus pada keakuratan, kelengkapan, dan kompleksitas.
- Sebuah program menjalankan algoritma di komputer. Sebuah program juga harus memperhitungkan semua detail komputer.
Algoritma biasa ditampilkan dengan pseudocode. Pseudocode itu semacam bahasa pemrograman, tapi tujuannya adalah untuk dibaca manusia. Jadi tidak banyak peraturan dalam cara penulisannya. Bahkan orang yang berbeda, mungkin menulis pseudocode dengan cara yang berbeda juga. Contoh sebuah algoritma dalam pseudocode:
m ← 0;
p ← 1;
while (p < n)
Tampilkan: "2^m adalah p";
m ← m + 1;
p ← p * 2; Sebuah program itu dibuat dari sebuah bahasa pemrograman yang di-compile (kalo gak tau gapapa, kita akan bahas compilation di part selanjutnya).
Nah, bahasa pemrograman itu mempunyai peraturan yang ketat dalam cara penulisannya (disebut syntax). Ini adalah contoh kode pemograman dari algoritma diatas dengan bahasa C:
void printPangkatDua(int n) {
int m = 0;
int p = 1;
while (p < n) {
printf("2^%d adalah %d\n", m, p);
m = m + 1;
p = p * 2;
}
} Bisa dilihat perbedaan dan kemiripan dari keduanya.
Pseudocode sangat simpel, hanya butuh keyword (kata kunci) while.
Sementara, bahasa C butuh beberapa keywords extra, seperti void, int dan printf.
Kita akan belajar lebih lanjut tentang keywords tersebut di part selanjutnya.
Insertion Sort (Penyortiran Insersi)
Daritadi kita belajar lumayan abstrak, sekarang kita coba belajar sesuatu yang lebih konkrit, yaitu sorting (penyortiran). So, apa itu sorting?
Sorting
Sorting adalah algoritma yang mengurutkan elements dari sebuah array. Sorting bisa dilakukan secara ascending (meningkat, dari kecil ke besar) atau secara descending (menurun, dari besar ke kecil). Sorting adalah algoritma yang selalu dipelajari pertama disaat orang belajar ilmu komputer, karena ini adalah dasar dari banyak hal. Jadi sangat penting kamu bisa ngerti ini!
Kita mulai dengan membahas definisi formal sorting. Karena ini pakai materi kampus, jadi sorting ini didefinisikan memakai matematika formal, tapi aku juga akan jelasin artinya.
Output: permutasi (a'1, ... , a'n) dari input (a1, ... , an)
dimana (a'1 ≤ a'2 ≤… ≤ a'n)
Definisi formalnya mungkin bingungin tapi sebenernya artinya gampang. Sorting secara ascending akan membuat seluruh elementnya mengurut, dari yang paling kecil ke paling besar.
Insertion sort algorithm
Algoritma ini akan mempunyai input sebuah deret bilang dengan panjang n. Contoh {3, 2, 5, 1} mempunyai n = 4. Lalu outputnya adalah deretan bilangan yang sama, tetapi dimulai dari element terkecil ke yang besar, contoh {1, 2, 3, 5}.
Algoritma ini bekerja seperti ini:
- Mulailah dari elemen kedua, karena elemen pertama diasumsikan sudah terurut.
- Bandingkan elemen kedua dengan elemen pertama; jika elemen kedua lebih kecil, tukar posisi keduanya.
- Lanjutkan ke elemen ketiga, bandingkan dengan dua elemen sebelumnya, lalu letakkan di posisi yang benar.
- Ulangi proses ini hingga seluruh array terurut.
source: https://www.geeksforgeeks.org/dsa/insertion-sort-algorithm/ Oke sekarang kita akan lihat step-by-step gimana algoritma ini berkerja dengan input [3, 2, 5, 1].
Array: [3, 2, 5, 1]
Step 1: Mulai dengan element kedua, yaitu angka 2. Kita bandingkan 2 dengan 3 (element pertama). Karena 3 lebih besar dari 2, maka kita ubah posisi mereka. Selesai step 1 karena sudak mentok ke kiri.
Array: [2, 3, 5, 1]
Step 2: Element ketiga adalah 5. 5 lebih besar dari 3, jadi tidak terjadi apa apa dan selesai step 2.
Array: [2, 3, 5, 1]
Step 3: Element keempat adalah 1. 1 lebih kecil daripada 5, jadi kita tukar.
Array: [2, 3, 1, 5]
Step 3.1: sekarang kita bandingkan 1 dan 3. 1 lebih kecil, jadi kita tukar.
Array: [2, 1, 3, 5]
Step 3.2: sekarang kita bandingkan 1 dan 2. 1 lebih kecil, jadi kita tukar. Selesai step 3 karena sudak mentok ke kiri.
Hasil akhir array: [1, 2, 3, 5] Nah sekarang coba kalian bikin kode yang bisa mengimplementasikan insertion sort. Jangan pake AI! Soalnya kalo pake AI bakal langsung selesai dan kalian gaada belajar apa-apa. Btw kalo mungkin masih bingung, dulu aku dikasih video ini sama dosennya.
Komentar
Tinggalkan komentar