BAB 1. Berpikir Komputasional (Computational Thinking)

Pengertian

Berpikir komputasional adalah cara menyelesaikan masalah secara sistematis sehingga dapat dikerjakan manusia maupun komputer.

Empat Komponen Utama

1. Dekomposisi

Memecah masalah besar menjadi bagian kecil.

Contoh:
Membuat LMS terdiri dari:

• Login
• Data Siswa
• Data Guru
• Nilai
• Absensi

2. Pengenalan Pola

Mencari kesamaan pola.

Contoh:
2, 4, 6, 8, …

Polanya: tambah 2.

3. Abstraksi

Mengambil informasi penting dan mengabaikan yang tidak penting.

4. Algoritma

Langkah-langkah untuk menyelesaikan masalah.

---

BAB 2. Algoritma

Definisi

Algoritma adalah urutan langkah logis untuk menyelesaikan suatu masalah.

Syarat Algoritma

1. Memiliki input
2. Memiliki output
3. Jelas
4. Efektif
5. Berakhir (finite)

Contoh

Menentukan bilangan genap:

1. Masukkan angka N
2. Jika N mod 2 = 0
3. Tampilkan “Genap”
4. Jika tidak
5. Tampilkan “Ganjil”

---

BAB 3. Kompleksitas Algoritma

OSN sangat menekankan efisiensi.

Notasi Big O

Kompleksitas	Keterangan
O(1)	Sangat cepat
O(log n)	Cepat
O(n)	Linear
O(n log n)	Sorting
O(n²)	Lambat
O(2ⁿ)	Sangat lambat

Contoh

for i = 1 sampai n

Kompleksitas:

O(n)

---

BAB 4. Struktur Data

Array

Menyimpan data berurutan.

Contoh:

10 20 30 40 50

Index:

0 1 2 3 4

---

Stack (LIFO)

Last In First Out

Contoh:

Tumpukan buku.

Masuk:
1
2
3

Keluar:
3
2
1

---

Queue (FIFO)

First In First Out

Contoh:

Antrian siswa.

Masuk:
A B C

Keluar:
A B C

---

Linked List

Data saling terhubung menggunakan pointer.

---

Tree

Struktur data berbentuk pohon.

Contoh:

      A
     / \
    B   C

---

Graph

Kumpulan simpul dan sisi.

Contoh:

Peta jalan antar kota.

---

BAB 5. Sorting (Pengurutan)

Bubble Sort

Contoh:

5 3 8 1

Hasil:

1 3 5 8

Kompleksitas:

O(n²)

---

Merge Sort

Metode divide and conquer.

Kompleksitas:

O(n log n)

---

Quick Sort

Sangat populer di OSN.

Rata-rata:

O(n log n)

---

BAB 6. Searching

Linear Search

Mencari satu per satu.

Kompleksitas:

O(n)

---

Binary Search

Syarat:

Data harus terurut.

Kompleksitas:

O(log n)

Contoh:

Cari 15 dalam:

5 10 15 20 25

Langsung ditemukan melalui pembagian tengah.

---

BAB 7. Rekursi

Fungsi yang memanggil dirinya sendiri.

Contoh Faktorial:

5! = 5×4×3×2×1

---

BAB 8. Greedy Algorithm

Memilih solusi terbaik saat itu juga.

Contoh:

Pecahan uang:

Rp 100.000
Rp 50.000
Rp 20.000
Rp 10.000

Untuk Rp 180.000:

100.000 + 50.000 + 20.000 + 10.000

---

BAB 9. Dynamic Programming

Digunakan jika ada perhitungan berulang.

Contoh:

Fibonacci.

Tanpa DP:

Lambat.

Dengan DP:

Cepat.

---

BAB 10. Graph dan BFS DFS

BFS (Breadth First Search)

Pencarian melebar.

Menggunakan Queue.

---

DFS (Depth First Search)

Pencarian mendalam.

Menggunakan Stack.

---

CONTOH SOAL OSN INFORMATIKA

Soal 1

Berapakah hasil dari:

13 mod 5

Jawaban

3

Alasan

13 ÷ 5 = 2 sisa 3.

---

Soal 2

Berapa kompleksitas algoritma berikut?

for(int i=0;i<n;i++)
{
   cout<<i;
}

Jawaban

O(n)

Alasan

Perulangan dilakukan sebanyak n kali.

---

Soal 3

Data:

7 2 5 1

Urutkan secara ascending.

Jawaban

1 2 5 7

Alasan

Ascending berarti dari kecil ke besar.

---

Soal 4

Struktur data apa yang menggunakan prinsip FIFO?

A. Stack

B. Queue

C. Tree

D. Graph

Jawaban

B. Queue

Alasan

FIFO = First In First Out.

---

Soal 5

Struktur data apa yang menggunakan prinsip LIFO?

A. Queue

B. Tree

C. Stack

D. Graph

Jawaban

C. Stack

Alasan

LIFO = Last In First Out.

---

Soal 6

Jika:

F(5)=?

Dengan:

F(n)=F(n-1)+F(n-2)

F(0)=0
F(1)=1

Jawaban

5

Alasan

F(2)=1
F(3)=2
F(4)=3
F(5)=5

---

Soal 7

Apa keuntungan Binary Search dibanding Linear Search?

Jawaban

Lebih cepat.

Alasan

Binary Search memiliki kompleksitas O(log n), sedangkan Linear Search O(n).

---

Soal 8

BFS menggunakan struktur data?

A. Stack

B. Queue

C. Array

D. Tree

Jawaban

B. Queue

Alasan

BFS bekerja dengan prinsip antrian.

---

Soal 9

DFS menggunakan struktur data?

A. Stack

B. Queue

C. Tree

D. Array

Jawaban

A. Stack

Alasan

DFS menelusuri simpul secara mendalam menggunakan Stack.

---

Soal 10

Algoritma yang mencoba seluruh kemungkinan solusi disebut?

A. Greedy

B. Dynamic Programming

C. Brute Force

D. DFS

Jawaban

C. Brute Force

Alasan

Brute Force memeriksa semua kemungkinan yang ada.

---

Materi yang Paling Sering Keluar di OSN

1. Algoritma Dasar
2. Sorting dan Searching
3. Rekursi
4. Struktur Data
5. Greedy
6. Dynamic Programming
7. Graph
8. BFS dan DFS
9. Shortest Path
10. String Processing
11. Kombinatorika
12. Teori Bilangan