Gambar 1
Seret untuk memutar · shift-seret untuk menggeser · klik untuk membongkar
Gulir untuk membalik halaman
Computer Science Principles · AP Computer Science Principles
bit, kompresi, dan informasi
Semua yang disimpan komputer, bilangan, nama, foto, lagu, pada dasarnya adalah pola bit.
Sebuah bit (singkatan dari binary digit) bernilai 0 atau 1. Perangkat komputasi merepresentasikan data secara digital: komponen tingkat terendah dari setiap nilai adalah bit.
Gambar ini menghitung dalam biner. Setiap petak adalah satu bit, sisi kertas untuk 0 dan sisi merah untuk 1, di bawah nilai tempatnya, 128, 64, 32, 16, 8, 4, 2, 1. Setiap langkah menambah 1: bit paling kanan berbalik, dan setiap kali 1 berbalik menjadi 0, bawaan merambat satu tempat ke kiri, seperti saat 00000111 (7) menjadi 00001000 (8).
Program menyimpan nilai data dalam variabel, dalam daftar berisi item, atau sebagai konstanta tersendiri, lalu meneruskannya sebagai masukan ke prosedur dan menerimanya kembali sebagai keluaran. Apa pun bentuknya, nilai-nilai itu disimpan sebagai bit, dan program menerjemahkannya ke bentuk yang bisa dibaca orang.
Bab ini adalah Gagasan Besar 2 AP Computer Science Principles, Data, 17–22% dari ujian pilihan ganda: bilangan biner (2.1), kompresi data (2.2), mengekstrak informasi dari data (2.3), dan memakai program dengan data (2.4).
bit dikelompokkan menjadi abstraksi
Sebuah byte adalah 8 bit. Sendirian, sebuah byte tidak berarti apa-apa: maknanya bergantung pada apa yang dianggap oleh program yang membacanya.
Abstraksi adalah proses mengurangi kerumitan dengan berfokus pada gagasan utama. Dengan menyembunyikan rincian yang tidak relevan dengan pertanyaan yang dihadapi dan menyatukan rincian yang berkaitan dan berguna, abstraksi memungkinkan kamu memikirkan gagasannya, bukan bit-bitnya.
Bit dikelompokkan untuk merepresentasikan abstraksi, termasuk (tetapi tidak terbatas pada) bilangan, karakter, dan warna. Gambar ini membaca satu byte, 01000001, dengan tiga cara:
| dibaca sebagai | artinya |
|---|---|
| bilangan biner | 65 |
| karakter (kode ASCII dan Unicode 65) | huruf A |
| kecerahan piksel, 0 (hitam) sampai 255 (putih) | abu-abu tua |
Jadi urutan bit yang sama dapat merepresentasikan jenis data yang berbeda dalam konteks yang berbeda. Gambar berwarna biasanya menyimpan tiga bilangan seperti itu untuk setiap piksel, masing-masing untuk merah, hijau, dan biru: 3 byte, 24 bit.
nilai tempat, bernomor dari 0 di sebelah kanan
Basis bilangan, termasuk biner dan desimal, dipakai untuk merepresentasikan data. Desimal (basis 10) hanya memakai angka 0–9; biner (basis 2) hanya memakai 0 dan 1.
Seperti dalam desimal, posisi sebuah angka menentukan nilainya: nilai numeriknya adalah angka itu dikali nilai tempat posisinya. Nilai tempat adalah basis dipangkatkan posisi, dan posisi diberi nomor mulai dari 0 di paling kanan, bertambah 1 ke arah kiri. Dalam desimal, 305 = 3 × 102 + 0 × 101 + 5 × 100.
Dalam biner, setiap tempat bernilai dua kali tempat di sebelah kanannya. Untuk 10110101:
| posisi | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
|---|---|---|---|---|---|---|---|---|
| nilai tempat | 27 = 128 | 26 = 64 | 25 = 32 | 24 = 16 | 23 = 8 | 22 = 4 | 21 = 2 | 20 = 1 |
| bit | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 |
Jumlahkan nilai tempat yang bitnya 1: 128 + 32 + 16 + 4 + 1 = 181. Bit 0 tidak menambahkan apa-apa. Gambar dibaca dari kiri ke kanan; setiap 1 menjatuhkan nilai tempatnya ke dalam jumlah.
ambil nilai tempat terbesar yang muat
Untuk menulis bilangan bulat positif dalam biner, bekerjalah dari nilai tempat terbesar ke bawah: bila nilai tempat itu muat dalam sisa, tulis 1 dan kurangkan; bila tidak muat, tulis 0.
Untuk 100 dengan delapan bit:
| nilai tempat | sisa | muat? | bit | sisa setelahnya |
|---|---|---|---|---|
| 128 | 100 | no | 0 | 100 |
| 64 | 100 | yes | 1 | 36 |
| 32 | 36 | yes | 1 | 4 |
| 16 | 4 | no | 0 | 4 |
| 8 | 4 | no | 0 | 4 |
| 4 | 4 | yes | 1 | 0 |
| 2 | 0 | no | 0 | 0 |
| 1 | 0 | no | 0 | 0 |
Jadi 100 = 01100100: 64 + 32 + 4 = 100. Nol di depan tidak mengubah apa-apa, sehingga 01100100 dan 1100100 adalah bilangan yang sama.
Cara kedua: bagi dengan 2 berulang kali, lalu baca sisa baginya dari yang terakhir ke yang pertama. 100 ÷ 2 = 50 sisa 0; 50 ÷ 2 = 25 sisa 0; 25 ÷ 2 = 12 sisa 1; 12 ÷ 2 = 6 sisa 0; 6 ÷ 2 = 3 sisa 0; 3 ÷ 2 = 1 sisa 1; 1 ÷ 2 = 0 sisa 1. Dibaca dari bawah ke atas: 1100100.
Pada gambar, batang biru adalah sisa dari 100; setiap 1 mematahkan nilai tempatnya dari batang dan membuat petaknya menjadi merah.
dan membandingkan bilangan biner
Satu bit memiliki 2 pola. Setiap bit tambahan menggandakan jumlahnya: setiap pola lama sekali dengan 0 di depan, dan sekali lagi dengan 1. Jadi n bit memiliki 2n pola.
Gambar ini menyusunnya: 1 bit, 2; 2 bits, 4; 3 bits, 8; 4 bits, 16. Sebuah byte memiliki 28 = 256 pola, yaitu bilangan bulat 0 sampai 255. Bilangan n bit terbesar adalah semuanya 1: 2n − 1.
Berapa bit yang dibutuhkan agar masing-masing dari 26 huruf mendapat polanya sendiri? 24 = 16 terlalu sedikit; 25 = 32 cukup: 5 bit.
Membandingkan dan mengurutkan. Buat kedua bilangan memiliki jumlah bit yang sama (tambahkan nol di depan) dan telusuri dari kiri. Posisi pertama yang berbeda menentukan: bilangan yang memiliki 1 di situ lebih besar, karena satu nilai tempat itu lebih besar daripada seluruh tempat di sebelah kanannya digabungkan (2p > 2p − 1).
01101100 dan 01011111 pertama kali berbeda di posisi 5, tempat 32, tempat bilangan pertama memiliki 1: 108 > 95, apa pun bit sesudahnya.
overflow dan galat pembulatan
Di banyak bahasa pemrograman, bilangan bulat direpresentasikan dengan jumlah bit yang tetap. Hal itu membatasi rentang nilai bilangan bulat dan perhitungan atasnya, dan dapat menyebabkan overflow atau kesalahan lain.
Penghitung pada gambar (hipotetis) memiliki 4 bit: ia menampung 0 sampai 15. Menambah 1 pada 15 (1111) membutuhkan bit kelima; bawaannya tidak punya tempat, dan penghitung menunjukkan 0. Itulah overflow.
Bahasa lain menyediakan abstraksi yang ukuran bilangan bulatnya hanya dibatasi oleh ukuran memori komputer. Bahasa pada lembar referensi ujian termasuk salah satunya: bilangan bulatnya tidak overflow.
Bilangan riil (dengan bagian pecahan) juga disimpan dalam jumlah bit yang tetap, yang membatasi rentangnya dan perhitungan atasnya serta dapat menyebabkan galat pembulatan dan kesalahan lain: sebagian bilangan riil hanya disimpan sebagai pendekatan. Dengan 3 bit pecahan (pada gambar, hipotetis) hanya kelipatan 1/8 = 0.125 yang ada; 0.1 disimpan sebagai 0.125, selisihnya 0.025.
Bahasa yang sebenarnya memakai jauh lebih banyak bit, sehingga galatnya jauh lebih kecil tetapi tidak hilang: di banyak bahasa, 0.1 + 0.2 bernilai 0.30000000000000004. Batas rentang tertentu untuk bilangan riil berada di luar cakupan kursus dan ujian.
pendekatan digital
Data analog memiliki nilai yang berubah secara mulus, bukan dalam selang diskret, seiring waktu: nada dan volume musik, warna-warna lukisan, posisi pelari cepat selama perlombaan.
Komputer menyimpan bit, sehingga hanya dapat mendekati data analog. Memakai data digital untuk mendekati data analog dunia nyata adalah contoh abstraksi.
Data analog dapat didekati dengan sangat baik secara digital melalui pencuplikan: mengukur nilai sinyal analog pada selang teratur, yang disebut cuplikan. Setiap cuplikan diukur untuk menentukan bit persis yang dibutuhkan untuk menyimpannya.
Gambar ini mencuplik sinyal mulus yang sama dua kali. Pertama 8 cuplikan, masing-masing dibulatkan ke salah satu dari 4 tingkat (2 bit): 8 × 2 = 16 bit, anak tangga yang kasar. Lalu 16 cuplikan pada 8 tingkat (3 bit): 16 × 3 = 48 bit, dan anak tangganya mengikuti kurva lebih dekat (jarak rata-ratanya dari sinyal turun 43%).
Lebih banyak cuplikan dan lebih banyak bit per cuplikan memberi pendekatan yang lebih dekat, dan menambah jumlah bit untuk disimpan atau dikirim. Tidak ada jumlah cuplikan terhingga yang membuatnya persis.
lebih kecil, dan kembali persis
Kompresi data dapat memperkecil ukuran (jumlah bit) data yang dikirim atau disimpan. Algoritma lossless biasanya dapat memperkecilnya sambil menjamin rekonstruksi data asli secara utuh.
Baris pada gambar memiliki 20 piksel, masing-masing satu byte: 20 byte (hipotetis). Run-length encoding menyimpan setiap deret satu warna sebagai hitungan dan warna: 7W 4R 6W 3B, 4 deret × 2 byte = 8 byte.
Dekode menuliskan 7 white, 4 red, 6 white, 3 blue: persis baris aslinya, piksel demi piksel. Tidak ada yang hilang, jadi bit yang lebih sedikit belum tentu berarti informasi yang lebih sedikit.
Besarnya pengurangan ukuran bergantung pada banyaknya redundansi dalam data asli dan algoritma kompresi yang dipakai. Deret panjang terkompresi dengan baik. Baris yang berganti warna setiap piksel (WRWRWR…) memiliki 20 deret sepanjang 1: setelah disandikan, ia memakai 40 byte, lebih banyak daripada 20 byte semula.
lebih kecil lagi, tetapi hanya pendekatan
Algoritma lossy dapat mengurangi jumlah bit yang disimpan atau dikirim secara signifikan, tetapi hanya memungkinkan rekonstruksi pendekatan dari data asli.
16 piksel pada gambar (kecerahan hipotetis, satu byte masing-masing) hanya menyimpan rata-rata tiap pasangan: 8 byte, setengah ukuran semula. Dekode memberi setiap piksel rata-rata pasangannya: 14 dari 16 kembali berbeda, hingga selisih 10. Bayangan abu-abu adalah data aslinya, dan tidak ada apa pun dalam 8 byte itu yang dapat mengembalikannya: pasangan 200, 180 dan 190, 190 sama-sama berrata-rata 190.
Algoritma lossy biasanya dapat mengurangi jumlah bit lebih banyak daripada yang lossless. Mana yang dipilih bergantung pada situasinya:
| yang paling penting | biasanya dipilih |
|---|---|
| kualitas, atau kemampuan merekonstruksi data asli secara persis (berkas program, dokumen teks) | lossless |
| memperkecil ukuran data atau waktu pengiriman (video streaming lewat koneksi lambat) | lossy |
pola, dan yang tidak dibuktikannya
Informasi adalah kumpulan fakta dan pola yang diekstrak dari data. Data memberi peluang untuk mengenali tren, membuat hubungan, dan menyelesaikan masalah.
Gambar ini memplot 24 hari hipotetis di sebuah kota pantai: es krim yang terjual terhadap kasus kulit terbakar. Saat yang satu naik, yang lain ikut naik: korelasi yang kuat (koefisien korelasi r = 0.86; 1 berarti garis lurus sempurna).
Es krim tidak menyebabkan kulit terbakar. Warnai hari-hari menurut suhunya dan alasannya terlihat: 7 hari panas (merah, 27 °C atau lebih) membawa lebih banyak es krim dan lebih banyak sinar matahari. Korelasi yang ditemukan dalam data belum tentu menunjukkan adanya hubungan sebab-akibat; dibutuhkan penelitian tambahan untuk memahami sifat pasti hubungannya.
Di sini catatan penjualan saja tidak bisa menunjukkannya. Sering kali satu sumber tidak memuat data yang dibutuhkan untuk menarik kesimpulan, dan data dari beberapa sumber (penjualan, kunjungan klinik, catatan cuaca) harus digabungkan.
data tentang data
Metadata adalah data tentang data. Fotonya adalah datanya; metadatanya dapat mencakup tanggal pembuatan, ukuran berkas, dimensi, dan tag-nya.
Perubahan dan penghapusan pada metadata tidak mengubah data utama. Pada gambar, tag “sunset” dihapus; tidak satu pun dari 64 piksel berubah.
Metadata dipakai untuk menemukan, mengatur, dan mengelola informasi: pustaka foto dapat mendaftar setiap foto yang diambil pada 14 Juni, atau setiap foto bertag “beach”, tanpa melihat satu piksel pun. Metadata meningkatkan efektivitas pemakaian data dengan memberi informasi tambahan, dan memungkinkan data distrukturkan dan diatur.
Dalam ujian, sebuah skenario memberikan data dan metadata yang dikumpulkan lalu bertanya apa yang dapat ditemukan. Tanyakan apa yang dicatat tiap bidang. Pustaka yang hanya memiliki tanggal dan tag dapat menjawab “berapa foto yang diambil pada bulan Juni?” tetapi tidak “di mana foto ini diambil?”: tidak ada bidang yang mencatat tempat.
seragam, tanpa mengubah maknanya
Himpunan data menimbulkan tantangan berapa pun ukurannya: perlunya membersihkan data, data yang tidak lengkap, data yang tidak valid, dan perlunya menggabungkan sumber data. Kemampuan memproses data bergantung pada kemampuan pengguna dan alat mereka.
Bergantung pada cara data dikumpulkan, data mungkin tidak seragam. Saat pengguna mengetik di kolom isian bebas, cara mereka menyingkat, mengeja, atau menulis huruf kapital berbeda-beda dari pengguna ke pengguna. Formulir pendaftaran pada gambar (hipotetis) memiliki 7 ejaan berbeda untuk 2 kota.
Pembersihan membuat data seragam tanpa mengubah maknanya, dengan mengganti semua singkatan, ejaan, dan huruf kapital yang setara dengan kata yang sama: 5 entri ditulis ulang, dan 7 ejaan menjadi 2. Sekarang program yang menghitung pendaftar per kota menghitung dengan benar.
Pembersihan tidak dapat mengarang apa yang hilang. Satu baris tidak memiliki usia (tidak lengkap) dan satu baris berisi −4 (tidak valid); keduanya ditandai, untuk diperiksa atau dikeluarkan dari analisis, bukan ditebak.
lebih banyak data bukan berarti data lebih baik
Masalah bias sering ditimbulkan oleh jenis atau sumber data yang dikumpulkan. Bias tidak hilang hanya dengan mengumpulkan lebih banyak data.
Jajak pendapat pada gambar (hipotetis) hanya menjangkau sisi kiri populasi, misalnya pembaca satu situs web. Pada seluruh populasi, 41% berpendapat merah. Setelah 30 jawaban, jajak pendapat menyatakan 80%; setelah 60, 78%. Jawaban dua kali lipat, gambaran salah yang sama, karena setiap jawaban berasal dari sumber tak representatif yang sama.
Ukuran tetap penting: ukuran himpunan data memengaruhi jumlah informasi yang dapat diekstrak darinya. Namun himpunan data besar sulit diproses dengan satu komputer dan mungkin membutuhkan sistem paralel, banyak prosesor yang mengerjakan bagian-bagian data sekaligus.
Skalabilitas sistem merupakan pertimbangan penting saat bekerja dengan himpunan data, karena kapasitas komputasi suatu sistem memengaruhi cara himpunan data diproses dan disimpan.
program yang memproses daftar
Program dapat dipakai untuk memproses data guna memperoleh informasi. Alat pencarian berguna untuk menemukan informasi secara efisien, dan sistem penyaringan data adalah alat penting untuk menemukan informasi dan mengenali pola dalam data.
Penyaringan hanya mempertahankan elemen yang memenuhi suatu kondisi, seperti hanya menyimpan bilangan positif dari sebuah daftar, atau hanya siswa yang mendaftar band:
data ← [4, -2, 7, 0, -5, 3] positives ← [] FOR EACH n IN data { IF(n > 0) { APPEND(positives, n) } } Gambar ini menjalankannya dengan baris yang sedang berjalan berwarna merah. Setiap n diuji; hanya yang memenuhi n > 0 yang ditambahkan. positives berakhir sebagai [4, 7, 3]; 0 tidak disimpan, karena 0 > 0 bernilai false.
Mengubah bentuk mengubah setiap elemen, seperti menggandakan setiap elemen dalam daftar, atau menambahkan email orang tua ke setiap catatan siswa. Dengan doubled ← [] lebih dulu:
FOR EACH n IN data { APPEND(doubled, 2 * n) } doubled berakhir sebagai [8, −4, 14, 0, −10, 6]. Wawasan bisa datang dari menerjemahkan dan mengubah bentuk data, dan pola dapat muncul saat data diubah bentuknya memakai program. Programmer juga memakai program untuk menyaring dan membersihkan data.
satu bilangan dari banyak, dan sebuah diagram
Menggabungkan atau membandingkan data mereduksi banyak nilai menjadi satu jawaban: menjumlahkan daftar bilangan, atau mencari siswa dengan IPK tertinggi. Visualisasi menampilkan himpunan data sebagai diagram, grafik, atau representasi visual lainnya.
Sebuah klub mencatat pendaftaran selama 6 minggu (hipotetis): signups ← [12, 18, 9, 22, 15, 20].
total ← 0 most ← signups[1] FOR EACH n IN signups { total ← total + n IF(n > most) { most ← n } } DISPLAY(total) DISPLAY(most) Program ini menampilkan 96 22: 6 minggu, 96 pendaftar secara keseluruhan, 22 pada minggu terbaik. most dimulai dari signups[1], nilai pertama, bukan 0, sehingga tetap bekerja walau semua nilai negatif. Saat berjalan, gambar menggambar setiap minggu sebagai batang: diagram terbentuk seiring data dibaca.
Tabel, diagram, teks, dan alat visual lain dapat dipakai untuk mengomunikasikan wawasan dan pengetahuan yang diperoleh dari data. Program seperti spreadsheet membantu mengatur dan menemukan tren dalam informasi secara efisien.
Program dipakai secara iteratif dan interaktif: lihat diagramnya, ajukan pertanyaan baru, saring atau ubah bentuk lagi. Menggabungkan sumber data, pengelompokan data (mengelompokkan item yang mirip) dan klasifikasi data (memilah item ke dalam kategori) adalah bagian dari memakai program untuk memperoleh wawasan dan pengetahuan dari data.