Rajah 1
Seret untuk memutar · shift-seret untuk menganjak · klik untuk membongkar
Tatal untuk bertukar halaman
Computer Science Principles · AP Computer Science Principles
bit, pemampatan dan maklumat
Segala yang disimpan oleh komputer, nombor, nama, foto, lagu, pada dasarnya ialah satu corak bit.
Sebuah bit (singkatan bagi digit perduaan) ialah 0 atau 1. Peranti pengkomputeran mewakili data secara digital: komponen paling asas bagi sebarang nilai ialah bit.
Rajah ini mengira dalam perduaan. Setiap jubin ialah satu bit, bahagian kertas bagi 0 dan bahagian merah bagi 1, di bawah nilai tempatnya, 128, 64, 32, 16, 8, 4, 2, 1. Setiap langkah menambah 1: bit paling kanan terbalik, dan di mana-mana 1 bertukar menjadi 0, nombor bawa mengalir satu tempat ke kiri, seperti apabila 00000111 (7) menjadi 00001000 (8).
Aturcara menyimpan nilai data dalam pemboleh ubah, dalam senarai item, atau sebagai pemalar yang berdiri sendiri, dan menghantarnya sebagai input kepada prosedur serta mendapatnya kembali sebagai output. Apa-apa pun bentuknya, nilai itu disimpan sebagai bit, dan aturcara menterjemahkannya ke bentuk yang boleh dibaca oleh manusia.
Bab ini ialah Idea Besar 2 AP Computer Science Principles, Data, 17–22% daripada peperiksaan aneka pilihan: nombor perduaan (2.1), pemampatan data (2.2), pengekstrakan maklumat daripada data (2.3) dan penggunaan aturcara dengan data (2.4).
bit dikumpulkan menjadi pengabstrakan
Sebuah bait ialah 8 bit. Dengan sendirinya, satu bait tidak bermakna apa-apa: maknanya bergantung pada apa yang dianggap oleh aturcara yang membacanya.
Pengabstrakan ialah proses mengurangkan kerumitan dengan menumpukan pada idea utama. Dengan menyembunyikan butiran yang tidak relevan kepada soalan yang dihadapi dan menghimpunkan butiran berkaitan yang berguna, pengabstrakan membolehkan anda memikirkan idea itu dan bukan bit-bitnya.
Bit dikumpulkan untuk mewakili pengabstrakan, termasuk (tetapi tidak terhad kepada) nombor, aksara dan warna. Rajah ini membaca satu bait, 01000001, dalam tiga cara:
| dibaca sebagai | maknanya |
|---|---|
| nombor perduaan | 65 |
| aksara (kod ASCII dan Unicode 65) | huruf A |
| kecerahan piksel, 0 (hitam) hingga 255 (putih) | kelabu gelap |
Jadi jujukan bit yang sama boleh mewakili jenis data yang berbeza dalam konteks yang berbeza. Imej berwarna lazimnya menyimpan tiga nombor sedemikian bagi setiap piksel, satu bagi merah, hijau dan biru: 3 bait, 24 bit.
nilai tempat, dinomborkan dari 0 di sebelah kanan
Asas nombor, termasuk perduaan dan perpuluhan, digunakan untuk mewakili data. Perpuluhan (asas 10) hanya menggunakan digit 0–9; perduaan (asas 2) hanya menggunakan 0 dan 1.
Seperti dalam perpuluhan, kedudukan sesuatu digit menentukan nilainya: nilai angkanya ialah digit itu didarab dengan nilai tempat kedudukannya. Nilai tempat ialah asas dinaikkan kepada kuasa kedudukan, dan kedudukan dinomborkan dari 0 di sebelah paling kanan, bertambah 1 ke kiri. Dalam perpuluhan, 305 = 3 × 102 + 0 × 101 + 5 × 100.
Dalam perduaan, setiap tempat bernilai dua kali ganda tempat di sebelah kanannya. Bagi 10110101:
| kedudukan | 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 |
Tambahkan nilai tempat yang bitnya 1: 128 + 32 + 16 + 4 + 1 = 181. Bit 0 tidak menambah apa-apa. Rajah dibaca dari kiri ke kanan; setiap 1 menjatuhkan nilai tempatnya ke dalam jumlah.
ambil nilai tempat terbesar yang muat
Untuk menulis nombor bulat positif dalam perduaan, bekerja dari nilai tempat terbesar ke bawah: jika nilai tempat itu muat dalam baki, tulis 1 dan tolaknya; jika tidak muat, tulis 0.
Bagi 100 dengan lapan bit:
| nilai tempat | baki | muat? | bit | baki selepas |
|---|---|---|---|---|
| 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. Sifar di hadapan tidak mengubah apa-apa, maka 01100100 dan 1100100 ialah nombor yang sama.
Kaedah kedua: bahagi dengan 2 berulang kali, dan baca baki dari yang terakhir ke yang pertama. 100 ÷ 2 = 50 b 0; 50 ÷ 2 = 25 b 0; 25 ÷ 2 = 12 b 1; 12 ÷ 2 = 6 b 0; 6 ÷ 2 = 3 b 0; 3 ÷ 2 = 1 b 1; 1 ÷ 2 = 0 b 1. Baca ke atas: 1100100.
Dalam rajah, palang biru ialah baki 100; setiap 1 memecahkan nilai tempatnya daripada palang itu dan menjadikan jubinnya merah.
dan membandingkan nombor perduaan
Satu bit mempunyai 2 corak. Setiap bit tambahan menggandakan bilangannya: setiap corak lama sekali dengan 0 di hadapan, dan sekali lagi dengan 1. Jadi n bit mempunyai 2n corak.
Rajah membinanya: 1 bit, 2; 2 bits, 4; 3 bits, 8; 4 bits, 16. Satu bait mempunyai 28 = 256 corak, iaitu nombor bulat 0 hingga 255. Nombor n bit yang terbesar ialah semuanya 1: 2n − 1.
Berapa bitkah yang diperlukan untuk memberi setiap satu daripada 26 huruf coraknya sendiri? 24 = 16 terlalu sedikit; 25 = 32 mencukupi: 5 bit.
Membandingkan dan menyusun. Beri kedua-dua nombor bilangan bit yang sama (lapik dengan sifar di hadapan) dan imbas dari kiri. Kedudukan pertama yang berbeza menentukan: nombor yang mempunyai 1 di situ lebih besar, kerana satu nilai tempat itu bernilai lebih daripada semua tempat di sebelah kanannya digabungkan (2p > 2p − 1).
01101100 dan 01011111 mula berbeza pada kedudukan 5, tempat 32, yang mana yang pertama mempunyai 1: 108 > 95, apa-apa pun bit selepasnya.
limpahan dan ralat pembundaran
Dalam banyak bahasa pengaturcaraan, integer diwakili oleh bilangan bit yang tetap. Itu mengehadkan julat nilai integer dan pengiraan yang dilakukan ke atasnya, dan boleh menyebabkan limpahan (overflow) atau ralat lain.
Pembilang dalam rajah (hipotesis) mempunyai 4 bit: ia memuatkan 0 hingga 15. Menambah 1 kepada 15 (1111) memerlukan bit kelima; nombor bawa tiada tempat untuk pergi, dan pembilang menunjukkan 0. Itulah limpahan.
Bahasa lain menyediakan pengabstrakan yang saiz integernya hanya dihadkan oleh saiz memori komputer. Bahasa pada helaian rujukan peperiksaan ialah salah satu daripadanya: integernya tidak melimpah.
Nombor nyata (dengan bahagian pecahan) juga disimpan dalam bilangan bit yang tetap, yang mengehadkan julat dan pengiraannya serta boleh menyebabkan ralat pembundaran dan ralat lain: sesetengah nombor nyata hanya disimpan sebagai anggaran. Dengan 3 bit pecahan (rajah, hipotesis) hanya gandaan 1/8 = 0.125 wujud; 0.1 disimpan sebagai 0.125, tersasar sebanyak 0.025.
Bahasa sebenar menggunakan lebih banyak bit, maka ralatnya jauh lebih kecil tetapi tidak hilang: dalam banyak bahasa, 0.1 + 0.2 bernilai 0.30000000000000004. Had julat tertentu bagi nombor nyata berada di luar skop kursus dan peperiksaan.
anggaran digital
Data analog mempunyai nilai yang berubah secara licin, bukan pada sela diskret, sepanjang masa: ton dan kenyaringan muzik, warna sebuah lukisan, kedudukan seorang pelari pecut semasa perlumbaan.
Komputer menyimpan bit, jadi ia hanya dapat menganggarkan data analog. Menggunakan data digital untuk menganggarkan data analog dunia sebenar ialah contoh pengabstrakan.
Data analog boleh dianggarkan dengan hampir tepat secara digital melalui pensampelan: mengukur nilai isyarat analog pada sela yang sekata, yang dipanggil sampel. Setiap sampel diukur untuk menentukan bit tepat yang diperlukan untuk menyimpannya.
Rajah menyampel isyarat licin yang sama dua kali. Mula-mula 8 sampel, masing-masing dibundarkan kepada salah satu daripada 4 aras (2 bit): 8 × 2 = 16 bit, tangga yang kasar. Kemudian 16 sampel pada 8 aras (3 bit): 16 × 3 = 48 bit, dan tangga itu mengikuti lengkung dengan lebih rapat (jarak puratanya daripada isyarat berkurang sebanyak 43%).
Lebih banyak sampel dan lebih banyak bit bagi setiap sampel memberikan anggaran yang lebih hampir, dan memerlukan lebih banyak bit untuk disimpan atau dihantar. Tiada bilangan sampel terhingga yang menjadikannya tepat.
lebih kecil, dan kembali dengan tepat
Pemampatan data boleh mengurangkan saiz (bilangan bit) data yang dihantar atau disimpan. Algoritma tanpa kehilangan biasanya dapat mengurangkannya sambil menjamin pembinaan semula data asal sepenuhnya.
Baris dalam rajah mempunyai 20 piksel, satu bait setiap satu: 20 bait (hipotesis). Pengekodan jarak larian menyimpan setiap larian satu warna sebagai kiraan dan warna: 7W 4R 6W 3B, 4 larian × 2 bait = 8 bait.
Penyahkodan menulis 7 white, 4 red, 6 white, 3 blue: tepat baris asal, piksel demi piksel. Tiada yang hilang, jadi bit yang lebih sedikit tidak semestinya bermakna maklumat yang lebih sedikit.
Jumlah pengurangan saiz bergantung pada jumlah lewahan dalam data asal dan algoritma pemampatan yang digunakan. Larian yang panjang dimampatkan dengan baik. Baris yang menukar warna pada setiap piksel (WRWRWR…) mempunyai 20 larian sepanjang 1: apabila dikodkan, ia mengambil 40 bait, lebih daripada 20 yang asalnya.
lebih kecil lagi, tetapi hanya anggaran
Algoritma dengan kehilangan boleh mengurangkan dengan ketara bilangan bit yang disimpan atau dihantar, tetapi hanya membenarkan pembinaan semula anggaran data asal.
16 piksel dalam rajah (kecerahan hipotesis, satu bait setiap satu) hanya menyimpan purata setiap pasangan: 8 bait, separuh daripada saiz asal. Penyahkodan memberi setiap piksel purata pasangannya: 14 daripada 16 kembali berbeza, sehingga 10. Bayang kelabu ialah yang asal, dan tiada apa dalam 8 bait itu yang dapat mengembalikannya: pasangan 200, 180 dan 190, 190 kedua-duanya mempunyai purata 190.
Algoritma dengan kehilangan biasanya dapat mengurangkan bilangan bit lebih banyak daripada yang tanpa kehilangan. Pilihan bergantung pada keadaan:
| apa yang paling penting | lazimnya dipilih |
|---|---|
| kualiti, atau keupayaan membina semula yang asal dengan tepat (fail aturcara, dokumen teks) | tanpa kehilangan |
| meminimumkan saiz data atau masa penghantaran (penstriman video melalui sambungan perlahan) | dengan kehilangan |
corak, dan apa yang tidak dibuktikannya
Maklumat ialah himpunan fakta dan corak yang diekstrak daripada data. Data memberi peluang untuk mengenal pasti aliran, membuat kaitan dan menangani masalah.
Rajah memplot 24 hari hipotesis di sebuah pekan tepi pantai: aiskrim yang dijual berbanding kes kulit terbakar. Apabila satu meningkat, begitu juga yang lain: korelasi yang kuat (pekali korelasi r = 0.86; 1 ialah garis lurus yang sempurna).
Aiskrim tidak menyebabkan kulit terbakar. Warnakan hari mengikut suhu dan sebabnya jelas: 7 hari panas (merah, 27 °C atau lebih) membawa lebih banyak aiskrim dan lebih banyak cahaya matahari. Korelasi yang ditemui dalam data tidak semestinya menunjukkan wujudnya hubungan sebab-akibat; kajian tambahan diperlukan untuk memahami sifat sebenar hubungan itu.
Di sini rekod jualan sahaja tidak dapat menunjukkannya. Selalunya satu sumber tidak mengandungi data yang diperlukan untuk membuat kesimpulan, dan data daripada beberapa sumber (jualan, lawatan klinik, rekod cuaca) mesti digabungkan.
data tentang data
Metadata ialah data tentang data. Foto itu ialah data; metadatanya mungkin termasuk tarikh ia dicipta, saiz failnya, dimensinya dan tegnya.
Perubahan dan pemadaman yang dibuat pada metadata tidak mengubah data primer. Dalam rajah, teg “matahari terbenam” dipadam; tidak satu pun daripada 64 piksel berubah.
Metadata digunakan untuk mencari, menyusun dan mengurus maklumat: pustaka foto boleh menyenaraikan setiap foto yang diambil pada 14 Jun, atau setiap foto yang bertanda “pantai”, tanpa melihat satu piksel pun. Metadata meningkatkan penggunaan data yang berkesan dengan menyediakan maklumat tambahan, dan membolehkan data distrukturkan dan disusun.
Dalam peperiksaan, sesuatu senario memberikan data dan metadata yang dikumpulkan serta bertanya apa yang boleh ditemui. Tanya apa yang direkodkan oleh setiap medan. Pustaka yang hanya ada tarikh dan teg boleh menjawab “berapa banyak foto diambil pada bulan Jun?” tetapi tidak “di manakah foto ini diambil?”: tiada medan yang merekodkan tempat.
seragam, tanpa mengubah makna
Set data menimbulkan cabaran tanpa mengira saiznya: keperluan untuk membersihkan data, data yang tidak lengkap, data yang tidak sah, dan keperluan untuk menggabungkan sumber data. Keupayaan memproses data bergantung pada keupayaan pengguna dan alat mereka.
Bergantung pada cara data dikumpulkan, data mungkin tidak seragam. Apabila pengguna menaip dalam medan terbuka, cara mereka menyingkat, mengeja atau menggunakan huruf besar berbeza-beza antara pengguna. Borang pendaftaran dalam rajah (hipotesis) mempunyai 7 ejaan berbeza bagi 2 bandar.
Pembersihan menjadikan data seragam tanpa mengubah maknanya, dengan menggantikan semua singkatan, ejaan dan penggunaan huruf besar yang setara dengan perkataan yang sama: 5 entri ditulis semula, dan 7 ejaan menjadi 2. Kini aturcara yang mengira pendaftaran bagi setiap bandar mengira dengan betul.
Pembersihan tidak dapat mereka apa yang tiada. Satu baris tiada umur (tidak lengkap) dan satu lagi memberi −4 (tidak sah); kedua-duanya ditandakan, untuk disemak atau ditinggalkan daripada analisis, bukan diteka.
lebih banyak data tidak bermakna data yang lebih baik
Masalah bias sering timbul daripada jenis atau sumber data yang dikumpulkan. Bias tidak dihapuskan hanya dengan mengumpulkan lebih banyak data.
Tinjauan pendapat dalam rajah (hipotesis) hanya mencapai bahagian kiri populasi, katakan pembaca satu laman web. Dalam seluruh populasi, 41% berpendapat merah. Selepas 30 jawapan, tinjauan itu menyatakan 80%; selepas 60, 78%. Jawapan digandakan, gambaran salah yang sama, kerana setiap jawapan datang daripada sumber tidak mewakili yang sama.
Saiz masih penting: saiz sesuatu set data menjejaskan jumlah maklumat yang boleh diekstrak daripadanya. Tetapi set data yang besar sukar diproses menggunakan satu komputer dan mungkin memerlukan sistem selari, iaitu banyak pemproses yang mengerjakan bahagian data serentak.
Kebolehskalaan sistem ialah pertimbangan penting apabila bekerja dengan set data, kerana kapasiti pengiraan sesebuah sistem menjejaskan cara set data boleh diproses dan disimpan.
aturcara yang memproses senarai
Aturcara boleh digunakan untuk memproses data bagi memperoleh maklumat. Alat carian berguna untuk mencari maklumat dengan cekap, dan sistem penapisan data ialah alat penting untuk mencari maklumat dan mengenal pasti corak dalam data.
Penapisan hanya mengekalkan elemen yang memenuhi sesuatu syarat, seperti mengekalkan nombor positif sahaja daripada senarai, atau pelajar yang mendaftar untuk band sahaja:
data ← [4, -2, 7, 0, -5, 3] positives ← [] FOR EACH n IN data { IF(n > 0) { APPEND(positives, n) } } Rajah melarikannya dengan baris yang sedang berjalan berwarna merah. Setiap n diuji; hanya yang n > 0 ditambah. positives berakhir sebagai [4, 7, 3]; 0 tidak dikekalkan, kerana 0 > 0 ialah false.
Pengubahan mengubah setiap elemen, seperti menggandakan setiap elemen dalam senarai, atau menambah e-mel ibu bapa pada setiap rekod pelajar. Dengan doubled ← [] dahulu:
FOR EACH n IN data { APPEND(doubled, 2 * n) } doubled berakhir sebagai [8, −4, 14, 0, −10, 6]. Pemahaman boleh datang daripada menterjemah dan mengubah data, dan corak boleh muncul apabila data diubah menggunakan aturcara. Pengaturcara juga menggunakan aturcara untuk menapis dan membersihkan data.
satu nombor daripada banyak nombor, dan satu carta
Menggabungkan atau membandingkan data mengurangkan banyak nilai kepada satu jawapan: menjumlahkan senarai nombor, atau mencari pelajar yang GPA-nya tertinggi. Visualisasi menunjukkan set data sebagai carta, graf atau perwakilan visual yang lain.
Sebuah kelab merekodkan pendaftaran selama 6 minggu (hipotesis): 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) Ia memaparkan 96 22: 6 minggu, 96 pendaftaran keseluruhannya, 22 pada minggu terbaik. most bermula pada signups[1], nilai pertama, bukan 0, jadi ia masih berfungsi walaupun setiap nilai negatif. Semasa ia berjalan, rajah melukis setiap minggu sebagai palang: carta terbentuk apabila data dibaca.
Jadual, gambar rajah, teks dan alat visual lain boleh digunakan untuk menyampaikan pemahaman dan pengetahuan yang diperoleh daripada data. Aturcara seperti hamparan membantu menyusun dan mencari aliran dalam maklumat dengan cekap.
Aturcara digunakan secara lelaran dan interaktif: lihat carta, tanya soalan baharu, tapis atau ubah sekali lagi. Menggabungkan sumber data, pengelompokan data (mengumpulkan item yang serupa) dan pengelasan data (menyusun item ke dalam kategori) ialah sebahagian daripada penggunaan aturcara untuk memperoleh pemahaman dan pengetahuan daripada data.