Variabel Memori, Array , Dan Argumentasi

Variabel Memori
Adalah sama dengan bahasa pemrograman lain. Sebuah tempat untuk menyimpan nilai. Variabel mungkin jenis yang berbeda, termasuk logis,, tanggal string numerik.

Array
Adalah pengaturan sistematis dari obyek, biasanya dalam baris dan kolom. Serta serangkaian unsur-unsur dari jenis yang sama ditempatkan di lokasi memori yang berdekatan yang dapat secara individual direferensikan dengan menambahkan indeks unik pengenal.
Itu berarti bahwa, misalnya, kita dapat menyimpan 5 nilai bertipe int dalam array tanpa harus mendeklarasikan 5 variabel yang berbeda, masing-masing dengan identifier yang berbeda. Daripada itu, menggunakan array, kita dapat menyimpan 5 nilai yang berbeda dari jenis yang sama, int misalnya, dengan identifikasi unik.
Umumnya, koleksi item data yang dapat dipilih oleh indeks dihitung pada saat run-time, termasuk:
Array struktur data
Pengaturan barang di spasi alamat yang sama di memori komputer
Array tipe data
Di gunakan dalam bahasa pemrograman untuk menentukan variabel yang dapat diindeks
Array asosiatif
Struktur model abstrak data yang generalizes indeks array untuk sewenang-wenang atau berbagai jenis di atas, seperti
Bit array atau vektor bit
Array dinamis , dialokasikan pada waktu berjalan
Paralel array catatan, dengan setiap bidang disimpan sebagai array terpisah
Jarang array , dengan unsur-unsur yang paling dihilangkan, untuk menyimpan matriks tipis
Variable-length array
Bergerigi array , dimana memiliki panjang baris yang berbeda secara individual atau terkait berbagai konsep:
Array prosesor , komputer untuk mengolah data array (jangan dikelirukan dengan array processor)
Array pemrograman , menggunakan notasi aljabar matriks dalam program (tidak sama dengan pengolahan array)
Array mengiris , ekstraksi sub-array dari array atau juga:
Global Array , perpustakaan untuk pemrosesan paralel
Intel Array Visualizer , sepotong perangkat lunak grafis ilmiah
Inisialisasi array.
Ketika mendeklarasikan array regular dari lingkup lokal (dalam satu fungsi, misalnya), jika kita tidak menentukan lain, unsur-unsur yang tidak akan diinisialisasi ke nilai default, sehingga konten mereka akan belum ditentukan sampai kita menyimpan beberapa nilai di dalamnya. Elemen-elemen array global dan statis, di sisi lain, secara otomatis diinisialisasi dengan nilai standar, yang untuk semua jenis fundamental ini berarti mereka penuh dengan nol.

Mengakses nilai array.
Dalam setiap titik di mana sebuah program array terlihat, kita dapat mengakses nilai dari setiap elemen secara sendiri seolah-olah itu adalah variabel normal, sehingga bisa baik membaca dan memodifikasi nilainya. Formatnya adalah yang sederhana seperti:
Nama [indeks
Berikut contoh sebelumnya di mana billy memiliki 5 elemen dan masing-masing unsur adalah bertipe int.

Variabel Argumentasi

Mungkin Anda ingin memiliki fungsi yang akan menerima sejumlah nilai dan kemudian kembali rata-rata. Anda tidak tahu berapa banyak argumen akan dilewatkan ke fungsi. Salah satu cara Anda bisa membuat fungsi akan menerima pointer ke array. Cara lain adalah dengan menulis fungsi yang dapat mengambil sejumlah argumen. Jadi anda bisa menulis avg (4, 12,2, 23,3, 33,3, 12.1), atau Anda bisa menulis avg (2, 2.3, 34.4); Beberapa fungsi perpustakaan dapat menerima daftar variabel argumen (seperti printf terhormat).
Untuk menggunakan fungsi dengan jumlah variabel argumen, atau lebih tepatnya, fungsi tanpa nomor set argumen, Anda akan menggunakan file header cstdarg. Ada empat bagian yang dibutuhkan: va_list, yang menyimpan daftar argumen, va_start, yang menginisialisasi daftar, va_arg, yang mengembalikan argumen berikutnya dalam daftar, dan va_end, yang membersihkan daftar argumen variabel. Setiap kali fungsi dinyatakan untuk memiliki jumlah tak tentu argumen, di tempat argumen terakhir Anda harus menempatkan suatu ellipsis (yang terlihat seperti'...'), begitu, a_function int (int x, ...); akan memberitahu compiler fungsi harus menerima namun banyak argumen bahwa programmer menggunakan, asalkan sama dengan setidaknya satu, yang menjadi yang pertama, x.

va_list adalah seperti variabel lain. Misalnya,

va_list a_list;
va_start adalah makro yang menerima dua argumen, sebuah va_list dan nama variabel yang langsung mendahului elipsis yang (...). Jadi, dalam a_function fungsi, untuk menginisialisasi a_list dengan va_start, Anda akan menulis va_start (a_list, x);

va_arg mengambil va_list dan jenis variabel, dan mengembalikan argumen berikutnya dalam daftar dalam bentuk apa pun jenis variabel itu diberitahu. Kemudian bergerak ke bawah daftar untuk argumen berikutnya. Sebagai contoh, va_arg (a_list, ganda) akan mengembalikan argumen selanjutnya, dengan asumsi itu ada, dalam bentuk ganda. Kali berikutnya itu disebut, itu akan mengembalikan argumen berikut nomor kembali terakhir, jika ada.

Untuk menunjukkan bagaimana masing-masing dari karya-karya bagian, ambil fungsi contoh:

# Include
# Include

using namespace std;

ganda rata-rata (int num, ...)
{
va_list argumen; / / tempat A untuk menyimpan daftar argumen
double sum = 0;

va_start (argumen, num); / / Inisialisasi argumen untuk menyimpan semua nilai setelah num
for (int x = 0; x jumlah + = va_arg (argumen, double); / / Menambahkan nilai berikutnya dalam daftar argumen untuk penjumlahan.
va_end (argumen); / / Membersihkan daftar

return sum / num; / / Mengembalikan beberapa angka (typecast mencegah pemotongan)
}
int main ()
{
cout < cout < }
Ini tidak selalu merupakan ide yang baik untuk menggunakan daftar argumen variabel sepanjang waktu, karena potensi ada untuk asumsi nilai adalah satu jenis, ketika sedang pada kenyataannya lain, seperti pointer null yang dianggap integer. Akibatnya, daftar argumen variabel harus digunakan hemat.

Algoritma Binary Search

Algoritma Binary Search


Jika kita mempunyai sebuah file dari record-record yang telah dijalankan, kita dapat melanjutkan menghapuskan memory pemeriksaan yang diperlukan untuk mendapatkan kembali sebuah record yang telah dipakai oleh suatu teknik binary search. Suatu binary search dibandingkan dengan kunci dari pencarian record dengan record tengah dari sebuah file. Kemudian masing-masing pencarian record yang telah ditempatkan atau setengah dari file yang telah dihilangkan dengan pertimbangan yang lebih lanjut. Dalam kasus yang sebelumnya, proses pembandingan dari record tengah dilanjutkan dalam record-record selanjutnya. Jika kita harus menghilangkan bagian atas dari sebuah file termasuk record yang telah dibandingkan berlawanan. Selanjutnya jika kita harus menghilangkan bagian bawah dari sebuah file termasuk record yang telah dibandingkan berlawanan. Dalam pengulangan proses dari pembandingan berlawanan dari record tengah, kita akhirnya akan menempatkan record yang kita inginkan atau menentukan bahwa itu tidak ada dalam file ketika tidak ada record-record selanjutnya.

Pencarian Biner (Binary Search) dilakukan untuk :
1. memperkecil jumlah operasi pembandingan yang harus dilakukan antara data yang dicari dengan data yang ada di dalam tabel, khususnya untuk jumlah data yang sangat besar ukurannya.
2. Prinsip dasarnya adalah melakukan proses pembagian ruang pencarian secara berulang-ulang sampai data ditemukan atau sampai ruang pencarian tidak dapat dibagi lagi (berarti ada kemungkinan data tidak ditemukan).
3. Syarat utama untuk pencarian biner adalah data di dalam tabel harus sudah terurut, misalkan terurut menaik.

Menemukan nilai dalam urutan diurutkan
Dalam bentuk yang paling sederhana, pencarian biner digunakan untuk cepat menemukan nilai dalam urutan diurutkan (pertimbangkan berurutan array biasa untuk sekarang). Kami akan menelepon nilai mencari nilai target untuk kejelasan. pencarian biner mempertahankan subsequence berdekatan dari urutan mulai dimana nilai target pasti berada. Ini disebut ruang pencarian. Ruang pencarian awalnya adalah seluruh urutan. Pada setiap langkah, algoritma membandingkan nilai rata-rata di ruang pencarian dengan nilai target. Berdasarkan perbandingan dan karena urutan diurutkan, kemudian dapat menghilangkan setengah dari ruang pencarian. Dengan melakukan ini berulang kali, akhirnya akan ditinggalkan dengan ruang pencarian yang terdiri dari elemen tunggal, nilai target.

Sebagai contoh, perhatikan urutan berikut bilangan bulat diurutkan dalam urutan dan mengatakan kami sedang mencari nomor 55:
0 5 13 19 22 41 55 68 72 81 98



Kami tertarik pada lokasi nilai target dalam urutan jadi kita akan mewakili ruang pencarian sebagai indeks ke dalam urutan. Awalnya, ruang pencarian berisi indeks 1 sampai 11. Karena ruang pencarian benar-benar interval, itu hanya cukup untuk menyimpan dua nomor, indeks rendah dan tinggi. Seperti dijelaskan di atas, kita sekarang memilih nilai tengah, yang adalah nilai pada indeks 6 (titik tengah antara 1 dan 11): nilai ini adalah 41 dan itu lebih kecil dari nilai target. Dari ini kita tidak hanya menyimpulkan bahwa elemen pada indeks 6 bukanlah nilai target, tetapi juga bahwa tidak ada elemen pada indeks antara 1 dan 5 bisa menjadi nilai target, karena semua elemen di indeks ini lebih kecil dari 41, yang lebih kecil dari nilai target. Hal ini membawa ruang pencarian ke indeks 7 sampai 11:
55 68 72 81 98



Berjalan dengan cara yang sama, kita memotong paruh kedua ruang pencarian dan yang tersisa dengan:
55 68



Tergantung pada bagaimana kita memilih median bahkan jumlah elemen kami baik akan menemukan 55 pada langkah berikutnya atau memenggal 68 untuk mendapatkan ruang pencarian hanya satu elemen. Either way, kita menyimpulkan bahwa indeks dimana nilai target terletak adalah 7.

Jika nilai target tidak hadir dalam urutan, pencarian biner akan mengosongkan ruang pencarian seluruhnya. Kondisi ini mudah untuk memeriksa dan menangani. Berikut adalah beberapa kode untuk pergi dengan deskripsi:
binary_search (A, target): lo = 1, hi = size (A) sedangkan lo <= hi: pertengahan = lo + (hi-lo) / 2 jika A target == [pertengahan]: kembali pertengahan lain jika A pertengahan [ ] y x. Properti ini adalah apa yang kita gunakan ketika kita membuang paruh kedua ruang pencarian. Hal ini setara dengan mengatakan bahwa p ¬ (x) menyiratkan ¬ p (y) untuk semua y x atau bahwa ¬ p (x) menyiratkan ¬ p (y) untuk semua
Ketika domain predikat adalah bilangan bulat, itu sudah cukup untuk membuktikan bahwa p (x) menyiratkan p (x +1) atau yang p ¬ (x) menyiratkan ¬ p (x-1), sisanya kemudian diikuti dengan induksi.

Kedua bagian yang paling sering interleaved: ketika kita berpikir masalah bisa diselesaikan dengan pencarian biner, kami bertujuan untuk merancang predikat sehingga memenuhi kondisi dalam teorema utama.

Orang mungkin bertanya-tanya mengapa kita memilih untuk menggunakan abstraksi ini daripada algoritma sederhana yang tampak kami telah digunakan sejauh ini. Hal ini karena banyak masalah tidak dapat dimodelkan sebagai mencari nilai tertentu, tetapi mungkin untuk mendefinisikan dan mengevaluasi predikat seperti "Apakah ada tugas yang biaya x atau kurang?", Ketika kita sedang mencari beberapa jenis penugasan dengan biaya terendah. Misalnya, masalah perjalanan salesman biasa (TSP) terlihat untuk perjalanan putaran termurah yang dilihat setiap kota tepat satu kali. Di sini, nilai target tidak didefinisikan seperti itu, tapi kita dapat mendefinisikan sebuah predikat "Apakah ada pulang-pergi yang biaya x atau kurang?" Dan kemudian menerapkan pencarian biner untuk menemukan terkecil x yang memenuhi predikat. Ini disebut mengurangi masalah asli untuk suatu keputusan (ya / tidak) masalah. Sayangnya, kita tahu tidak ada cara efisien mengevaluasi ini predikat tertentu dan sehingga masalah TSP tidak mudah diselesaikan dengan pencarian biner, tapi masalah optimasi banyak.

Mari kita sekarang mengkonversi biner pencarian sederhana pada array diurutkan diuraikan dalam pendahuluan ini definisi abstrak. Pertama, mari kita rephrase masalah sebagai: "A array dan target, nilai return indeks yang pertama dalam elemen A sama dengan atau lebih besar dari target. Nilai Mengingat" Kebetulan, ini lebih atau kurang bagaimana lower_bound berperilaku di C + +.

Kami ingin mencari index dari nilai target, sehingga setiap indeks ke array adalah solusi kandidat. Pencarian ruang S adalah himpunan semua solusi calon, sehingga interval yang mengandung semua indeks. Pertimbangkan predikat "Apakah A [x] lebih besar dari atau sama dengan nilai target?". Jika kita adalah untuk menemukan yang pertama x yang predikatnya kata ya, kita akan mendapatkan apa yang memutuskan kami cari di paragraf sebelumnya.

Kondisi dalam teorema utama puas karena array diurutkan dalam urutan menaik: jika A [x] lebih besar dari atau sama dengan nilai target, semua elemen setelah itu yang pasti juga lebih besar dari atau sama dengan nilai target.

Jika kita mengambil urutan sampel dari sebelumnya:
0 5 13 19 22 41 55 68 72 81 98



Dengan ruang pencarian (indeks):
1 2 3 4 5 6 7 8 9 10 11



Dan menerapkan predikat kami (dengan nilai target 55) untuk itu kita mendapatkan:
tidak ada tidak ada tidak ada tidak ada tidak ada tidak ada ya ya ya ya ya



Ini merupakan rangkaian ada jawaban yang diikuti oleh serangkaian jawaban ya, karena kami mengharapkan. Perhatikan bagaimana indeks 7 (dimana nilai target terletak) adalah pertama yang menghasilkan predikat ya, jadi ini adalah apa pencarian biner kita akan menemukan.

Melaksanakan algoritma diskrit
Satu hal penting yang perlu diingat sebelum mulai kode untuk menetap pada apa dua angka Anda menjaga (batas bawah dan atas) berarti. Jawaban mungkin adalah suatu interval tertutup yang pasti berisi pertama x yang p (x) benar. Semua kode Anda kemudian harus diarahkan untuk mempertahankan invarian ini: ia memberitahu Anda bagaimana benar memindahkan batas, yang merupakan tempat bug dapat dengan mudah menemukan jalan dalam kode Anda, jika Anda tidak hati-hati.

Hal lain yang harus berhati-hati dengan adalah bagaimana tinggi untuk mengatur batas. Dengan "tinggi" Saya benar-benar berarti "lebar" karena ada dua batas perlu khawatir. Setiap sehingga sering terjadi bahwa programmer menyimpulkan selama coding bahwa batas-batas ia mengatur yang cukup luas, hanya untuk menemukan-balik selama istirahat (ketika itu sudah terlambat). Sayangnya, sedikit membantu saran dapat diberikan di sini selain untuk selalu double dan triple-memeriksa batasan Anda! Juga, karena waktu eksekusi meningkat logaritmis dengan batas-batas, Anda selalu dapat mengatur mereka lebih tinggi, asalkan tidak melanggar evaluasi predikat. Jauhkan mata Anda keluar untuk kesalahan overflow di sekitar, terutama dalam menghitung median.

Sekarang kita akhirnya sampai ke kode yang mengimplementasikan pencarian biner seperti yang dijelaskan dalam hal ini dan bagian sebelumnya:
binary_search (lo, hi, p):
sedangkan pertengahan = + lo (hi-lo) / 2
jika p (pertengahan) == benar:
hi = pertengahan
lain:
lo = mid +1

jika p (lo) == false:
mengeluh / / p (x) adalah salah untuk semua x dalam S!

kembali lo / / lo adalah yang paling x yang p (x) benar
Dua garis penting yang hi = mid dan lo = mid +1. Ketika p (pertengahan) benar, kita dapat membuang paruh kedua ruang pencarian, karena predikat tersebut benar untuk semua elemen di dalamnya (oleh teorema utama). Namun, kita tidak bisa membuang pertengahan sendiri, karena mungkin menjadi elemen pertama yang p benar. Inilah sebabnya mengapa memindahkan batas atas hingga pertengahan adalah sebagai agresif bisa kita lakukan tanpa memperkenalkan bug.

Dalam nada yang sama, jika p (pertengahan) adalah palsu, kita dapat membuang paruh pertama ruang pencarian, tapi kali ini termasuk pertengahan. P (pertengahan) adalah salah sehingga kita tidak perlu di ruang pencarian kami. Hal ini secara efektif berarti kita dapat memindahkan batas bawah hingga pertengahan +1.

Jika kita ingin menemukan terakhir x yang p (x) adalah palsu, kami akan merancang (menggunakan alasan yang sama seperti di atas) sesuatu seperti:
/ / Peringatan: ada bug jahat dalam potongan ini!
binary_search (lo, hi, p):
sedangkan pertengahan = lo + (hi-lo) / 2 / / catatan: divisi memotong
jika p (pertengahan) == benar:
hi = pertengahan 1
lain:
lo = pertengahan

jika p (lo) == benar:
mengeluh / / p (x) benar untuk semua x dalam S!

kembali lo / / lo adalah yang terbesar x p (x) adalah palsu
Anda dapat memverifikasi bahwa ini memenuhi kondisi kami bahwa unsur kita cari selalu hadir dalam interval (lo, hi). Namun, ada masalah lain. Pertimbangkan apa yang terjadi ketika Anda menjalankan kode ini pada beberapa ruang pencarian yang memberi predikat:
tidak ada ya
Kode akan terjebak dalam satu lingkaran. Selalu akan memilih elemen pertama sebagai pertengahan, tetapi kemudian tidak akan memindahkan batas bawah karena ingin menjaga pencari ruang di no. Solusinya adalah mengubah pertengahan = lo + (hi-lo) / 2 sampai pertengahan = lo + (hi-lo +1) / 2, yaitu sehingga putaran Facebook bukannya turun. Ada cara lain untuk mendapatkan sekitar masalah, tetapi yang satu ini mungkin merupakan terbersih. Tapi ingatlah untuk selalu menguji kode Anda pada-elemen dua set mana predikat salah untuk elemen pertama dan benar untuk yang kedua.

Anda juga mungkin bertanya-tanya seperti mengapa pertengahan dihitung menggunakan pertengahan = lo + (hi-lo) / 2 bukannya pertengahan biasa = (lo + hi) / 2. Hal ini untuk menghindari bug lain pembulatan potensial: dalam kasus pertama, kita ingin divisi untuk selalu putaran bawah, menuju batas bawah. Tapi divisi memotong, jadi ketika lo + hi akan negatif, hal itu akan mulai pembulatan ke arah yang lebih tinggi terikat. Coding perhitungan cara ini memastikan bahwa jumlah dibagi selalu positif dan karenanya selalu babak seperti yang kita inginkan. Meskipun bug tersebut tidak muncul ketika ruang pencarian hanya terdiri dari bilangan bulat positif atau bilangan real, saya telah memutuskan untuk kode dengan cara ini seluruh artikel untuk konsistensi.

Real nomor
pencarian biner juga dapat digunakan pada fungsi monoton yang domain adalah himpunan bilangan real. Melaksanakan pencarian biner pada real biasanya lebih mudah dari pada bilangan bulat, karena Anda tidak perlu diwaspadai bagaimana cara memindahkan batas:
binary_search (lo, hi, p):
sementara kita memilih untuk tidak berakhir:
pertengahan = + lo (hi-lo) / 2
jika p (pertengahan) == benar:
hi = pertengahan
lain:
lo = pertengahan

kembali lo / / lo dekat dengan perbatasan antara tidak dan ya
Karena himpunan bilangan real yang padat, harus jelas bahwa kita biasanya tidak akan dapat menemukan nilai target yang tepat. Namun, kita dengan cepat dapat menemukan beberapa x sedemikian sehingga f (x) adalah dalam beberapa toleransi perbatasan antara tidak dan ya. Kami memiliki dua cara untuk memutuskan kapan untuk mengakhiri: berakhir pada saat ruang pencarian semakin kecil dari beberapa yang telah ditentukan terikat (katakanlah 10 -12) atau melakukan sejumlah tetap iterasi. Pada TopCoder, Anda terbaik adalah dengan hanya menggunakan beberapa ratus iterasi, ini akan memberikan presisi terbaik tanpa berpikir terlalu banyak. 100 iterasi akan mengurangi ruang pencarian untuk sekitar 10 -30 dari ukuran awal, yang harus cukup untuk sebagian besar (jika tidak semua) masalah.

Jika Anda perlu lakukan sebagai sedikit iterasi mungkin, Anda dapat berakhir pada saat interval semakin kecil, tetapi cobalah untuk melakukan perbandingan relatif dari batas, bukan hanya salah satu yang mutlak. Alasan untuk ini adalah bahwa menggandakan pernah dapat memberikan Anda lebih dari 15 digit desimal presisi jadi jika ruang pencarian mengandung jumlah besar (katakan pada urutan miliar), Anda tidak pernah mendapatkan perbedaan mutlak kurang dari 10 -7.

Contoh
Pada titik ini saya akan menunjukkan bagaimana semua pembicaraan ini dapat digunakan untuk memecahkan masalah TopCoder. Untuk ini saya telah memilih masalah agak sulit, FairWorkload , yang merupakan divisi 1 tingkat 2 masalah dalam SRM 169.

Dalam masalah ini, sejumlah pekerja harus memeriksa sejumlah lemari arsip. Lemari tidak semua ukuran yang sama dan kita diberitahu untuk setiap kabinet berapa banyak folder di dalamnya. Kita diminta untuk mencari tugas sehingga setiap pekerja mendapat serangkaian berurutan kabinet harus melalui dan bahwa hal itu meminimalkan jumlah maksimum folder yang seorang pekerja harus melihat melalui.

Setelah mendapatkan akrab dengan masalah, sentuhan kreativitas diperlukan. Bayangkan bahwa kita memiliki jumlah yang tidak terbatas pekerja di pembuangan kami. Pengamatan penting adalah bahwa, untuk beberapa MAX nomor, kita dapat menghitung jumlah minimum pekerja diperlukan sehingga setiap pekerja harus memeriksa tidak lebih dari folder MAX (jika ini mungkin). Mari kita lihat bagaimana kita akan melakukannya. Beberapa pekerja perlu memeriksa kabinet pertama sehingga kami menetapkan pekerja apapun untuk itu. Namun, karena kabinet harus ditugaskan dalam urutan (pekerja tidak dapat memeriksa lemari 1 dan 3 tanpa memeriksa 2 juga), selalu optimal untuk menugaskannya untuk kabinet kedua juga, jika ini tidak membawanya ke atas batas kita memperkenalkan (MAX). Jika itu akan membawanya ke atas batas, kami menyimpulkan bahwa karyanya dilakukan dan menetapkan seorang pekerja baru ke kabinet kedua. Kami melanjutkan dengan cara yang sama sampai semua lemari telah ditetapkan dan menegaskan bahwa kita telah menggunakan jumlah minimum pekerja mungkin, dengan batas buatan kami memperkenalkan. Perhatikan di sini bahwa jumlah pekerja berbanding terbalik dengan MAX: semakin tinggi kita menetapkan batas kami, para pekerja lebih sedikit kita akan membutuhkan.

Sekarang, jika Anda pergi kembali dan hati-hati memeriksa apa yang kita minta dalam pernyataan masalah, Anda dapat melihat bahwa kita benar-benar diminta untuk MAX terkecil sehingga jumlah pekerja yang dibutuhkan adalah kurang dari atau sama dengan jumlah tenaga kerja yang tersedia . Dengan itu dalam pikiran, kita hampir selesai, kita hanya perlu menghubungkan titik-titik dan melihat bagaimana semua ini cocok dalam frame kita diletakkan untuk memecahkan masalah menggunakan pencarian biner.

Dengan masalah diulang sesuai dengan kebutuhan kita lebih baik, sekarang kita dapat memeriksa predikat Dapat menyebar beban kerja sehingga setiap pekerja harus memeriksa tidak lebih dari x folder, dengan jumlah tenaga kerja yang tersedia terbatas? Kita dapat menggunakan algoritma serakah digambarkan efisien mengevaluasi predikat untuk setiap x. Hal ini menyimpulkan bagian pertama dari membangun solusi pencarian biner, sekarang kita hanya perlu membuktikan bahwa kondisi dalam teorema utama puas. Tapi amati bahwa peningkatan x sebenarnya melemaskan batas pada beban kerja maksimal, sehingga kita hanya bisa memerlukan nomor yang sama pekerja atau kurang, tidak lebih. Jadi, jika predikat mengatakan ya untuk beberapa x, juga akan mengatakan ya untuk semua yang lebih besar x.

Untuk jelasnya, berikut adalah potongan STL-driven yang memecahkan masalah:
int getMostWork (vektor folder, pekerja int) {
int n = folders.size ();
int lo = * max_element (folders.begin (), folders.end ());
int hi = menumpuk (folders.begin (), folders.end (), 0);

while (lo int x = lo + (hi-lo) / 2;

int diperlukan current_load = 1, = 0;
for (int i = 0; i if (current_load + folder [i] <= x) {
/ / Pekerja saat ini dapat mengatasinya
current_load + = folder [i];
}
else {
/ / Menetapkan pekerja berikutnya
+ + Diperlukan;
current_load = map [i];
}
}

jika ( hi = x;
lain
lo = x +1;
}

kembali lo;
}
Perhatikan batas bawah dan atas dengan hati-hati dipilih: Anda bisa mengganti atas terikat dengan integer cukup besar, tetapi batas bawah tidak boleh kurang dari kabinet terbesar untuk menghindari situasi di mana sebuah lemari tunggal akan terlalu besar bagi pekerja apapun, kasus yang tidak akan benar ditangani oleh predikat. Alternatif akan mengatur batas bawah nol, kemudian menangani terlalu kecil x sebagai kasus khusus dalam predikat.

Untuk memverifikasi bahwa solusi tidak mengunci, saya menggunakan tidak kecil / ya misalnya dengan folder = {1,1} dan pekerja = 1.

Kompleksitas keseluruhan dari solusi adalah O (n log SIZE), dimana SIZE adalah ukuran ruang pencarian. Ini sangat cepat.

Seperti yang Anda lihat, kami menggunakan algoritma greedy untuk mengevaluasi predikat. Dalam masalah lain, mengevaluasi predikat bisa turun ke apapun dari ekspresi matematika sederhana untuk mencari pencocokan kardinalitas maksimum pada graf bipart.

Spanning Tree

SPANING TREE

Sebuah pohon rentang dari graf adalah himpunan bagian dari tepi yang membentuk sebuah pohon (Skiena 1990, hal 227). Misalnya, mencakup pohon dari grafik siklus , berlian grafik , dan grafik lengkap diilustrasikan di atas.
Jumlah pohon mencakup nonidentical dari grafik sama untuk setiap kofaktor dari matriks derajat dari dikurangi matriks adjacency dari (Skiena 1990, hal 235). Hasil ini dikenal sebagai teorema pohon matriks . Sebuah pohon berisi pohon rentang yang unik, sebuah grafik siklus mengandung mencakup pohon, dan sebuah grafik yang lengkap berisi mencakup pohon (Trent 1954; Skiena 1990, hal 236). Sebuah hitungan pohon rentang dari grafik dapat ditemukan dengan menggunakan perintah NumberOfSpanningTrees [ g ] pada Mathematica paketCombinatorica ` .

Contoh dari spaning tree antara lain:

Tutte polynomial
Adalah polinomial dalam dua variabel yang memainkan peran penting dalam teori graph , cabang dari matematika dan ilmu komputer teoritis . Ini didefinisikan untuk setiap graf tak berarah dan berisi informasi tentang bagaimana grafik tersambung.
Pentingnya Tutte polinomial T G berasal dari informasi yang berisi tentang G . Meskipun awalnya belajar di teori graph aljabar sebagai generalisasi dari menghitung masalah yang berkaitan dengan pewarnaan grafik dan tempat-nol aliran , terkenal mengandung beberapa spesialisasi dari ilmu-ilmu lain seperti polinomial Jones dari teori simpul dan fungsi partisi dari model Potts dari statistik fisika . Itu juga merupakan sumber dari beberapa pusat masalah komputasi dalam ilmu komputer teoritis .
Polinom Tutte memiliki beberapa definisi setara. Hal ini setara dengan Whitney polinomial pangkat , Tutte sendiri polinomial dwiwarna dan Fortuin-Kasteleyn's acak cluster model bawah transformasi sederhana. Ini pada dasarnya adalah sebuah fungsi pembangkit untuk jumlah set tepi ukuran yang diberikan dan komponen yang terhubung, dengan generalisasi segera matroids . Hal ini juga yang paling umum invarian grafikyang dapat didefinisikan oleh-kontraksi kambuh penghapusan.

Definisi dari Tutte polynomial.
Untuk graf tak berarah G = ( V , E ) orang dapat mendefinisikan polinomial Tutte sebagai

Di sini, c ( A ) menunjukkan jumlah komponen yang terhubung dari grafik ( V , A ) . Dalam definisi ini jelas bahwa T G baik-pasti dan polinomial dalam x dan y . Definisi yang sama dapat diberikan dengan menggunakan notasi berbeda sedikit dengan membiarkan r ( A ) = | V | - c ( A ) menunjukkan pada peringkat grafik ( V , A ) . Kemudian peringkat Whitney fungsi pembangkit didefinisikan sebagai

dua fungsi yang setara dengan perubahan sederhana variabel: T G ( x , y ) = R G ( x - 1, y - 1) . Tutte's dwiwarna polinomial Q G adalah hasil lain transformasi sederhana:
T G ( x , y ) = ( x - 1) - k ( G ) Q G ( x - 1, y - 1).
asli definisi's Tutte dari T G adalah setara tapi kurang mudah lain. Untuk tersambung G kita tentukan
T G ( x , y ) = Σ t i j x i y j ,
i , j
dimana t i j menunjukkan jumlah pohon rentang dari "aktivitas internal i dan kegiatan eksternal j . "
Definisi ketiga menggunakan-kontraksi kambuh penghapusan. Para tepi kontraksi G / u v dari graf G adalah graf yang diperoleh dengan menggabungkan simpul u dan v dan menghapus tepi u v .Kami menulis G - u v untuk grafik dimana tepi u v hanya dihapus. Kemudian polinomial Tutte didefinisikan oleh hubungan terulangnya
T G = T G - e + T G / e jika e bukan sebuah loop atau jembatan
dengan kasus dasar
T G ( x , y ) = x i y j jika G mengandung i jembatan dan j loop dan tidak ada sisi lainnya.
Terutama, T G = 1 jika G tidak berisi tepi.
Model cluster random dari mekanika statistik memberikan definisi lain setara. Polinom

setara dengan T G bawah transformasi
T G ( x , y ) = ( x - 1) - k ( E ) ( y - 1) - | V | Z G (( x - 1) ( y - 1), y - 1) .

Linked List

Linked list adalah salah satu struktur data dasar yang sangat fundamental dalam bidang ilmu komputer. Dengan menggunakan linked list maka programmer dapat menimpan datanya kapanpun dibutuhkan. Linked list mirip dangan array, kecuali pada linked list data yang ingin disimpan dapat dialokasikan secara dinamis pada saat pengoperasian program (run-time).

Pada array, apabila programmer ingin menyimpan data, programmer diharuskan untuk mendefinisikan besar array terlebih dahulu, seringkali programmer mengalokasikan array yang sangat besar(misal 100). Hal ini tidak efektif karena seringkali yang dipakai tidak sebesar itu. Dan apabila programmer ingin menyimpan data lebih dari seratus data, maka hal itu tidak dapat dimungkinkan karena sifat array yang besarnya statik. Linked list adalah salah satu struktur data yang mampu menutupi kelemahan tersebut.

Secara umum linked list tersusun atas sejumlah bagian-bagian data yang lebih kecil yang terhubung (biasanya melalui pointer). Linked list dapat divisualisasikan seperti kereta, bagian kepala linked list adalah mesin kereta, data yang disimpan adalah gerbong, dan pengait antar gerbong adalah pointer.
-------- -------- --------
Mesin Data Data
-------- -------- --------
(kepala) ---> Pointer ---> Pointer --
-------- -------- --------

Programmer membaca data menyerupai kondektur yang ingin memeriksa karcis penumpang. Programmer menyusuri linked list melalui kepalanya, dan kemudian berlanjut ke gerbong (data) berikutnya, dan seterusnya sampai gerbong terakhir (biasanya ditandai dengan pointer menunjukkan alamat kosong (NULL)). Penyusuran data dilakukan secara satu persatu sehingga penyusuran data bekerja dengan keefektifan On. Dibandingkan array, ini merupakan kelemahan terbesar linked list. Pada array, apabilan programmer ingin mengakses data ke-n (index n), maka programmer dapat langsung mengaksesnya. Sedangkan dengan linked list programmer harus menyusuri data sebanyak n terlebih dahulu.

Jenis – Jenis Linked List Ada 3 Macam Yaitu :

A Singly Linked List
Field pointer-nya hanya satu buah saja dan satu arah serta pada akhir node, pointernya menunjuk NULL. Node-node tersebut saling terhubung satu sama lain.
Setiap node pada linked list mempunyai field yang berisi pointer ke node berikutnya, dan juga memiliki field yang berisi data.
Node terakhir akan menunjuk ke NULL yang akan digunakan sebagai kondisi berhenti pada saat pembacaan isi linked list.
Deklarasi Node
typedef struct TNode{
int data;
TNode *next;
};

Penjelasan:

• Pembuatan struct bernama TNode yang berisi 2 field, yaitu field data bertipe integer dan field next yang bertipe pointer dari TNode
• Setelah pembuatan struct, buat variabel head yang bertipe pointer dari TNode yang berguna sebagai kepala linked list.
Pembuatan Single Linked List non Circular (2)
• Digunakan keyword new yang berarti mempersiapkan sebuah node baru berserta alokasi memorinya, kemudian node tersebut diisi data dan pointer nextnya ditunjuk ke NULL.
TNode *baru;
baru = new TNode;
baru->data = databaru;
baru->next = NULL;

B.Double Linked List
Adalah sebuah Linked List yang terdiri dari dua arah pointer, dengan node yang saling terhubung, namun kedua pointernya menunjuk ke NULL. Setiap node pada linked list mempunyai field yang berisi data dan pointer yang saling berhubungan dengan node yang lainnya.

GAMBARAN NODE Duble Linked List



C. Circular Linked List

Teknik Sorting Dan Searcing

Sorting adalah sebuah proses merangkai benda dalam urutan tertentu dan/atau dalam himpunan yang berbeda, dan oleh karena itu dia memiliki dua arti umum yang berbeda:
1.pengurutan: merangkai benda yang sejenis, sekelas, dll, dalam urutan yang teratur,
2.kategorisasi: pengelompokan dan pemberian label kepada benda dengan sifat yang serupa.

Mensortir informasi atau data
Salah satu cara sorting yang penting adalah mengatur benda informasi dalam urutan alfabetik sesuai dengan hubungan penyusunan yang telah didefinisikan sebelumnya, misal ketika seseorang mensortir buku-buku di perpustakaan berdasarkan judul, subyek atau penulis (Biasanya diurutkan dalam urutan membesar).
Urutan yang dihasilkan dapat membesar atau mengecil, karena biasanya seluruh sorting adalah sorting angka. Sorting dalam ilmu komputer adalah salah satu subjek riset yang paling luas karena kebutuhan mempercepat operasi dalam ribuan atau jutaan data selama operasi pencarian; lihat algoritma sorting.
Tujuan utama mensortir informasi adalah untuk mengoptimalkan tugas tertentu. Pada umumnya, ada dua cara pengelompokan informasi: berdasarkan kategori, misal sebuah katalog belanja di mana barang disusun bersama di bawah judul seperti 'rumah', 'olah raga', 'pakaian wanita', dll. dan berdasarkan intensitas seperti harga, misal dari yang termurah sampai yang termahal.

Macam – macam teknik dalam sorthing:
•Straight Selection Sort. teknik sorting ini dibuat dengan cara melakukan pengecek'an 1 persatu, bila kita akan mengurutkan secara ascending maka kita lakukan pengecek'an nilai tempat yang pertama (index pertama pada array) bila lebih kecil daripada index berikutnya (index 1 dengan index 2, index 1 dengan index 3, ..... index 1 dengan index terakhi) maka kita lakukan pertukaran nilai pada array index tersebut. proses ini dilakukan terus menerus sampai pada pengecekan index terakhir - 1 dengan nidex terakhir.

•Selection Sort.Teknik sorting ini dibuat dengan cara melakukan pengecek'an 1 persatu, bila kita akan mengurutkan secara ascending maka kita lakukan pengecek'an nilai tempat yang pertama (index pertama pada array)kita bandingkan dengan semua nilai yang ada kita cari nilai minimalnya. lalu simpan index/ letak nilai minimum itu di temukan, setelah pengecekan selesai tukar index awal pengecekan dengan nilai minimum yang telah di simpan tadi. Proses ini dilakukan terus menerus sampai pada pengecekan index terakhir min 1 dengan index terakhir. beda dengan streith selection sort adalah dengan teknik ini melakukan pertukaran nilai lebih sedikit, hanya jumlah data - 1 pertukaran. jadi waktu untuk melakukan proses sorting lebih cepat.listing program (open in Inrternet eplorer only)

•Bubble Sort. Teknik ini dilakukan degan pola membawa nilai terbesar menjadi nilai index terakhir array. jadi sistem ini melakukan pengecekan nilai 1 dengan 2, lalu 2 dengan 3 samapai dengan data terakhir, bila nilai index yang lebih kecil lebih besar maka akan dilakukan pertukaran. proses ini dilakuan hingga jumlah data - 1. listing program (open in Inrternet eplorer only)

•Modified Bubble Sort. Teknik ini dilakukan degan pola membawa nilai terbesar menjadi nilai index terakhir array. Jadi sistem ini melakukan pengecekan nilai 1 dengan 2, lalu 2 dengan 3 samapai dengan data terakhir, bila nilai index yang lebih kecil lebih besar maka akan dilakukan pertukaran. proses ini dilakuan hingga jumlah data dikurangi 1 atau sampai program tidak melakukan pertukaran. jadi waktu untuk melakukan proses sorting lebih cepat.listing program.

Searching
Dalam pencarian data juga terdapat beberapa jenis algoritma, tujuan dari adanya banyak algoritma yang di temukan adalah karena memiliki keuntungan-keuntungan tersendiri, seperti lebih cepatnya bila mengolah data yang jumlahnya lebih dari juta data, ada yang lebih efisien dengan jumlah kurang dari jutaan. serta ada pula yang tidak perlu untuk mengurutkan data terlebih dahulu, tetapi memakan waktu lebih lama.

•Line Search. teknik searching ini dibuat dengan cara melakukan pengecek'an 1 persatu, yaitu antara data yang di cari dengan kumpulan data yang di miliki, Keuntungan metode ini adalah kita tidak perlu mengurutkan data yang ada, bila mencari data pada kumpulan data yang tidak urut hanya terdapat metode ini yang dapat di lakukan.

•Binnary Search. teknik ini hanya dapat digunakan hanya pada kumpulan data yang sudah di urutkan, karena teknik ini melakukan pencarian dengan mencari data pada index yang tengah, apakah lebih besar/lebih kecil/sama dengan. bila hasil sama dengan maka nilai yang di cari telah di temukan. bila lebih kecil/lebih besar maka akan di buang setengah data dari yang salah, dan mencari dari indeks yang tengah dari sisanya. demikian samapi data ditemukan atau tidak di temukan.

•Fibonachi Search. Teknik ini hanya dapat digunakan hanya pada kumpulan data yang sudah di urutkan, karena teknik ini melakukan pencarian dengan mencari data melalui pola bilangan fibonachi. Bila pada binnary search pembandingnya adalah nilai pada index tengahnya jumlah data, pada fibonachi search berbeda yaitu: bilangan fibonachi, yang bilangan fibonachinya terdekat dengan jumlah data tetapi tidak lebih besar dari jumlah data yang akan di proses. Bilangan fibonachi itu di jumlahkan dengan batas paling awal data dikurangi 1. Contohnya: jumlah data yang akan di cari adalah 15, maka batas paling bawah adalah 1 dan batas paling akhir=15 dan index pembandingnya= 13(nilai awal + dijumlahkan Bilangan fibonachi - 1) karena bilangan fibonachi terdekat dengan 15 (data ke 1- data ke 15) adalah 13 (1,2,3,5,8,13,21,34.....), bila data yang di cari lebih besar dari bilangan indeks ke tengahnya maka. batas paling bawah= tetap, batas akhir nilai tengah-1, bila data yang dicari lebih kecil maka batas bawah = nilai tengah +1 dan batas akhir tetap, sedangkan nilai tengahnya memakai fungsi tadi.

Sejarah perkembangan komputer

Sejarah perkembangan komputer
Alat hitung tradisional dan Kalkulator mekanik
Abacus, yang muncul sekitar 5000 tahun yang lalu di Asia kecil dan masih digunakan di beberapa tempat hingga saat ini, dapat dianggap sebagai awal mula mesin komputasi. Alat ini memungkinkan penggunanya untuk melakukan perhitungan
menggunakan biji-bijian geser yang diatur pada sebuah rak. Para pedagang di masa itu menggunakan abacus untuk menghitung transaksi perdagangan. Seiring dengan munculnya pensil dan kertas, terutama di Eropa, abacus kehilangan popularitasnya. Setelah hampir 12 abad, muncul penemuan lain dalam hal mesin komputasi. Pada tahun 1642, Blaise Pascal (1623-1662), yang pada waktu itu berumur 18 tahun, menemukan apa yang ia sebut sebagai kalkulator roda numerik (numerical wheel calculator) untuk membantu ayahnya melakukan perhitungan pajak
Kotak persegi kuningan ini yang dinamakan Pascaline, menggunakan delapan roda putar bergerigi untuk menjumlahkan bilangan hingga delapan digit. Alat ini,merupakan alat penghitung bilangan berbasis sepuluh. Kelemahan alat ini adalah hanya terbatas untuk melakukan penjumlahan
Tahun 1694, seorang matematikawan dan filsuf Jerman, Gottfred Wilhem von Leibniz (1646-1716) memperbaiki Pascaline dengan membuat mesin yang dapat mengalikan. Sama seperti pendahulunya, alat mekanik ini bekerja dengan menggunakan roda-roda gerigi. Dengan mempelajari catatan dan gambar- gambar yang dibuat oleh Pascal, Leibniz dapat menyempurnakan alatnya. Barulah pada tahun 1820, kalkulator mekanik mulai populer. Charles Xavier Thomas de Colmar menemukan mesin yang dapat melakukan empat fungsi aritmatik dasar. Kalkulator mekanik Colmar, arithometer, mempresentasikan pendekatan yang lebih praktis dalam kalkulasi karena alat tersebut dapat melakukan penjumlahan, pengurangan, perkalian, danpembagian. Dengan kemampuannya, arithometer banyak dipergunakan hingga masa Perang Dunia I. Bersama-sama dengan Pascal dan Leibniz, Colmar membantu membangun era komputasi mekanikal. Awal mula komputer yang sebenarnya dibentuk oleh seoarng profesor matematika Inggris, Charles Babbage (1791-1871).
Tahun 1812, Babbage memperhatikan kesesuaian alam antara mesin mekanik dan matematika:mesin mekanik sangat baik dalam mengerjakan tugas yang sama berulangkali tanpa kesalahan; sedang matematika membutuhkan repetisi sederhana dari suatu langkah-langkah tertenu. Masalah tersebut kemudain berkembang hingga menempatkan mesin mekanik sebagai alat untuk menjawab kebutuhan mekanik. Usaha Babbage yang pertama untuk menjawab masalah ini muncul pada tahun 1822 ketika ia mengusulkan suatu mesin untuk melakukan perhitungan persamaan differensial
Mesin tersebut dinamakan Mesin Differensial. Dengan menggunakan tenaga uap, mesin tersebut dapat menyimpan program dan dapat melakukan kalkulasi serta mencetak hasilnya secara otomatis. Setelah bekerja dengan Mesin Differensial selama sepuluh tahun, Babbage tiba-tiba terinspirasi untuk memulai membuat komputer general-purpose yang pertama, yang disebut Analytical Engine. Asisten Babbage, Augusta Ada King (1815-1842) memiliki peran penting dalam pembuatan mesin ini. Ia membantu merevisi rencana, mencari pendanaan dari pemerintah Inggris, dan mengkomunikasikan spesifikasi
Anlytical Engine kepada publik. Selain itu, pemahaman Augusta yang baik tentang mesin ini memungkinkannya membuat instruksi untuk dimasukkan ke dlam mesin dan juga membuatnya menjadi programmer wanita yang pertama.
Pada tahun 1980, Departemen Pertahanan Amerika Serikat menamakan sebuah bahasa pemrograman dengan nama ADA sebagai penghormatan kepadanya. Mesin uap Babbage, walaupun tidak pernah selesai dikerjakan, tampak sangat primitif apabila dibandingkan dengan standar masa kini. Bagaimanapun juga, alat tersebut menggambarkan elemen dasar dari sebuah komputer modern dan juga mengungkapkan sebuah konsep penting. Terdiri dari sekitar 50.000 komponen, desain dasar dari Analytical Engine menggunakan kartu-kartu perforasi (berlubang-lubang) yang berisi instruksi operasi bagi mesin tersebut. Pada 1889, Herman Hollerith (1860-1929) juga menerapkan prinsip kartu perforasi untuk melakukan penghitungan. Tugas pertamanya adalah menemukan cara yang lebih cepat untuk melakukan perhitungan bagi Biro Sensus Amerika Serikat. Sensus sebelumnya yang dilakukan di tahun 1880
membutuhkan waktu tujuh tahun untuk menyelesaikan perhitungan. Dengan berkembangnya populasi, Biro tersebut memperkirakan bahwa dibutuhkan waktu sepuluh tahun untuk menyelesaikan perhitungan sensus
Hollerith menggunakan kartu perforasi untuk memasukkan data sensus yang kemudian diolah oleh alat tersebut secara mekanik. Sebuah kartu dapat menyimpan hingga 80 variabel. Dengan menggunakan alat tersebut, hasil sensus dapat diselesaikan dalam waktu enam minggu. Selain memiliki keuntungan dalam bidang kecepatan, kartu tersebut berfungsi sebagai media penyimpan data. Tingkat kesalahan perhitungan juga dapat ditekan secara drastis. Hollerith kemudian mengembangkan alat tersebut dan menjualny ke masyarakat luas. Ia mendirikan Tabulating Machine Company pada tahun 1896 yang kemudian menjadi International Business Machine (1924) setelah
mengalami beberapa kali merger. Perusahaan lain seperti Remington Rand and Burroghs juga memproduksi alat pembac kartu perforasi untuk usaha bisnis. Kartu perforasi digunakan oleh kalangan bisnis dan pemerintahan untuk permrosesan data hingga tahun 1960. Pada masa berikutnya, beberapa insinyur membuat penemuan baru lainnya. Vannevar Bush (1890- 1974) membuat sebuah kalkulator untuk menyelesaikan persamaan differensial di tahun 1931. Mesin tersebut dapat menyelesaikan persamaan differensial kompleks yang selama ini dianggap rumit oleh kalangan akademisi. Mesin tersebut sangat besar
dan berat karena ratusan gerigi dan poros yang dibutuhkan untuk melakukan perhitungan. Pada tahun 1903, John V. Atanasoff dan Clifford Berry mencoba membuat komputer elektrik yang menerapkan aljabar Boolean pada sirkuit elektrik.

Pendekatan ini didasarkan pada hasil kerja George Boole (1815-1864) berupa sistem biner aljabar, yang menyatakan bahwa setiap persamaan matematik dapat dinyatakan sebagai benar atau salah. Dengan mengaplikasikan kondisi benar-salah ke dalam sirkuit listrik dalam bentuk terhubung-terputus, Atanasoff dan Berry membuat komputer elektrik pertama di tahun 1940. Namun proyek mereka terhenti karena kehilangan sumber pendanaa.
Dari dahulu , proses pengolahan data telah dilakukan oleh manusia. Manusia juga menemukan alat-alat mekanik dan elektronik untuk membantu manusia dalam penghitungan dan pengolahan data supaya bisa mendapatkan hasil lebih cepat. Komputer yang kita temui saat ini adalah suatu evolusi panjang dari penemuan-penemuan manusia sejah dahulu kala berupa alat mekanik maupun elektronik. Saat ini komputer dan piranti pendukungnya telah masuk dalam setiap aspek kehidupan dan pekerjaan. Komputer yang ada sekarang memiliki kemampuan yang lebih dari sekedar perhitungan matematik biasa. Diantaranya adalah sistem komputer di kassa supermarket yang mampu membaca kode barang belanjaan, sentral telepon yang menangani jutaan panggilan dan komunikasi, jaringan komputer dan internet yang mennghubungkan berbagai tempat di dunia.Bagaimanapun juga alat pengolah data dari sejak jaman purba sampai saat ini bisa kita golongkan ke dalam 4 golongan besar.

1. Peralatan manual: yaitu peralatan pengolahan data yang sangat sederhana,
dan faktor terpenting dalam pemakaian alat adalah menggunakan tenaga
tangan manusia.

2. Peralatan Mekanik: yaitu peralatan yang sudah berbentuk mekanik yang
digerakkan dengan tangan secara manual.

3. Peralatan Mekanik Elektronik: Peralatan mekanik yang digerakkan secara
otomatis oleh motor elektronik.

4. Peralatan Elektronik: Peralatan yang bekerjanya secara elektronik penuh
Tulisan ini akan memberikan gambaran tentang sejarah komputer dari masa ke
masa, terutama alat pengolah data.




Kemunculan Beberapa Jenis Komputer Berdasarkan Generasinya:

Komputer Generasi Pertama
Komputer genarasi pertama ini disebut juga sebagai komputer dinosaurus karena ukurannya yang relatif besar. Hanya orang yang ahli sajalah yang dapat menggunakan komputer ini karena sangat sulit dan daya komputesinya sangatlah lambat.
Ciri ciri komputer pada generasi pertama adalah sebagai berikut :
•Komponen elektronikanya dari Tabung Hampa (Vacuum Tube)
•Program dibuat dalam bahasa mesin (Machine Language), yang programnya tersimpan dalam memori komputer. Programnya masih menggunakan bahasa mesin dengan menggunakan kode 0 dan 1 dalam urutan tertentu.
•Sifat-sifatnya:
oUkurannya besar dan memerlukan tempat yang sangat luas
oMemerlukan banyak Pendingin (AC) karena banyak mengeluarkan panas
oProsesnya relatif lambat
oKapasitas untuk menyimpan data kecil.
•Pabrik yang memproduksi; UNIVAC, IBM, BURROGHS, HONEYWELL
•Contoh mesin; ENIAC, MARK II, EDSAC, MARK III, UNIVAC I & II, IBM 650, ADVAC
Komputer generasi pertama berawal dari tahun 1942 hingga tahun 1959

Komputer Generasi Kedua
Komputer generasi kedua ini muncul pada era 1960-an dan dulu komputer ini banyak di gunakan di berbagai perusahaan perusahaan khususnya dalam bidang bisnis. Ukurannya lebih kecil ketimbang komputer generasi pertama yaitu kira kira seukuran lemari saja. Pada era ini juga manusia telah mengenal printer, memori, disket ataupun sitem operasi.
Ciri ciri komputer generasi kedua adalah sebagai berikut :
•Komponen elektronikanya dari Transistor
•Program dibuat dengan Assembly Language, Common Business-Oriented Language (COBOL) dan Formula Translator (FORTRAN) dan ALGOL
•Sifat-sifatnya:
oUkurannya relatif kecil
oTidak banyak mengeluarkan panas
oTelah mengenal Magnetic Tape dan Magnetic Disk untuk menyimpan data
oMulai mengenal Tele Processing (time sharing yang memungkinkan beberapa user dapat memakai kokmputer secara bersama-sama)
oProses relatif lebih cepat
oKapasitas untuk menyimpan data semakin besar.
•Pabrik yang memproduksi; UNIVAC, IBM, BURROGHS, HONEYWELL, CDC (Control Data Corporation), NCR
•Contoh mesin; IBM (IBM 1620, IBM 1401, IBM 7070, IBM 7080, IBM 7094), UNIVAC III, CDC 6600 Super dan CDC 7600, BURROGHS 5500, HONEYWELL 400, PDP 1 & 5
Walaupun komputer ini telah menggunakan transistor yang mana menggantikan fungsi tabung hampa tetapi tetap saja mengeluarkan panas walaupun tidak sebanyak yang di keluarkan oleh komputer generasi pertama dan itu dapat berpotensi untuk merusak komponen komponen yang ada pada komputer. Pada generasi ini juga bermunculan banyak programmer, analyst dan ahli di bidang komputer serta juga bermunculan dan mulai berkembang industr piranti lunak atau softwere.

Komputer Generasi Ketiga
Komputer generasi ketiga merupakan perkembangan yang paling pesat dari perkembangan komputer yang ada. Komputer generasi ketiga muncul sejak era 1965-1971-an. Transistor yang dianggap tidak effisien lagi membuat manusia mencari solusi lain dan solusi itu di temukan pada batu kuarsa ( Quartz rock ). Jack Kilby, seorang insinyur di Texas Instrument, mengembangkan sirkuit terintegrasi (IC : integrated circuit) di tahun 1958. Hal ini merupakan sebuah inovasi yang dapat mendongkrak munculnya komputer generasi ketiga.
Ciri ciri komputer generasi ketiga adalah sebagai berikut :
•Komponen elektronikanya dari Integrated Circuit (IC) yang berbentuk lempengan atau chip
•Program dibuat dengan bahasa tingkat tinggi (High Level Language), yaitu: BASIC, FORTRAN, COBOL
•Sudah menerapkan konsep multi processing dan dapat menjalankan program lebih dari satu multi programming dalam waktu yang bersamaan
•Dapat berkomunikasi dengan peralatan lain untuk melakukan komunikasi data seperti telepon dengan komputer.
•Sifat-sifatnya:
oUkurannya lebih kecil dari komputer generasi kedua
oMulai mengenal Multi Programming dan Multi Processing
oAdanya integrasi antara Software dan Hardware dalam Sistem Operasi
oProsesnya sangat cepat
oKapasitas untuk menyimpan data lebih besar.
•Pabrik yang memproduksi; IBM, BURROGHS, HONEYWELL, NCR
•Contoh mesin; IBM S/360, UNIVAC 1108, PDP 8 & 11, HONEYWELL 200, RCA, SPECTRA 70.
Pada era ini juga mulai digunakannya sistem operasi (operation sistem) yang memungkinkan mesin menjalankan berbagai program yang berbeda secara serentak dengan sebuah program utama yang memonitor dan mengkoordinasi memori komputer. Sistem operasi komputer pada generasi ketiga adalah UNIX dan Windows. Walapupun grafiknya masihlah sangat minim.

Komputer Generasi Keempat
Komputer generasi keempat adalah komputer yang kita temui pada saat ini. Komputer yang dalam komponen elektriknya masih menggunakan mikrochip walaupun ukurannya dan bahan yang digunakan berbeda. Ukurannya lebih kecil membuat ukuran komputerpun lebuh sederhana.
Ciri ciri komputer generasi keempat adalah sebagai berikut :
•Komponen elektronikanya dari miniaturisasi yang disebut LSI dan mulai memperkenalkan VLSI (Very Large Scale Integration) yang merupakan paduan dari IC dengan kapasitas rangkaian dapat mencapai 100.000 komponen tiap chip
•Mulai dikembangkan suatu jaringan komputer lokal yang menggunakan ARCNET (Attach Research Computing Network)
•Program dibuat dengan bahasa: BASIC, FORTRAN, COBOL, PASCAL
•Sifat-sifatnya:
oUkurannya relatif lebih kecil
oSudah menerapkan Multi Programming dan Multi Processing
oMengenal DataBase Management System (DBMS).
•Pabrik yang memproduksi; IBM, BURROGHS, HONEYWELL, INTEL
•Contoh mesin; IBM (IBM S/34, IBM S/36, IBM PC/AT & XT, IBM PS/2), HONEYWELL 700, BURROGHS 600, CRAY I, CYBER, PC Aplle II, COMMODORE PC ,INTEL i386 sampai dengan intel Pentium I, II, III, IV, Dual Core, Core 2 Duo, dan Quad Core.
Komputer genarasi ini telah berkembang sangat pesat karena penggunannya yang sangat mudah (friendly user) dan serba guna apalagi di bidang industri dan teknologi informasi, peranan komputer sangatlah membantu.

Komputer Generasi Kelima
Rencana masa depan komputer generasi ke lima adalah komputer yang telah memiliki Artificial Intelligence (AI). Sehingga komputer di masa depan dapat memberikan respon atas keinginan manusia.
Ciri ciri komputer generasi kelima adalh sebagai berikut :
•Komputer generasi ini masih dalam tahap pengembangan dan pemakainya belum banyak. Pengembangan komputer genarasi ini dipelopori oleh negara Jepang
•Komponen elektronikanya menggunakan bentuk paling baru dari chip VLSI
•Program dibuat dalam bahasa PROLOG (Programming Logic) dan LISP (List Processor)
•Komputer generasi kelima difokuskan kepada AI (Artificial Inteligence / Kecerdasan Buatan), yaitu sesuatu yang berhubungan dengan penggunaan komputer untuk melaksanakan tugas-tugas yang merupakan analog tingkah laku manusia.
•Sifat-sifatnya:
oDapat membantu menyusun program untuk dirinya sendiri
oDapat menerjemahkan dari suatu bahasa ke bahasa lain
oDapat membuat pertimbangan-pertimbangan logis
oDapat mendengar kalimat perintah yang diucapkan serta melaksanakannya
oDapat memilih setumpuk fakta serta menggunakan fakta yang diperlukan
oDapat mengolah gambar-gambar dan grafik dengan cara yang sama dengan mengolah kata, misalnya dapat melihat serta mengerti sebuah foto.
Dua tanda tanda akan munculnya inovasi komputer generasi kelima adalah komputer paralel yang berarti memungkinkan banyak CPU bekerja sama membentuk suatu jaringan yang efisien. Selin itu ditemukannya superkonduktor yang memungkinkan aliran listrik mengalir tanpa hambatan sedikitpun sehingga dapat meningkatkan kecepatan informasi yang di dapat. Lembaga ICOT (Institute for new Computer Technology) juga dibentuk untuk merealisasikan keberadaan komputer generasi kelima ini.
Berikut ini beberapa kejadian penting yang memberi dampak besar bagi sejarah perkembangan komputer:
•1917 – John Napier membuat “Napier’s Bones,” yaitu berupa sekumpulan ranting kayu ivory yang digunakan untuk membantu dalam hal perhitungan.
•1942 – Blaise Pascal memperkenalkan the Pascaline digital adding machine.
•1822 – Charles Babbage mengkonsepkan sebuah mesin yang disebutnya Analytical Engine, sebuah mesin yang berfungsi untuk melakukan perhitungan-perhitungan umum.
•1906 – Lee De Forest mempatenkan vacuum tube triode, yang digunakan sebagai electronic switch pada sebuah komputer elektronik pertama.
•1936 – Alan Turing mempublikasikan “On Computable Numbers,” yang berisi konsep mengenai sebuah mesin penghitung fantasy yang disebutnya the Turing Machine, yang akhirnya dijadikan sebagai pondasi bagi mesin penghitung modern.
•1937 – John V. Atanasoff mulai mengerjakan the Atanasoff-Berry Computer (ABC), yang kemudian secara resmi dianggap sebagai komputer elektronik pertama.
•1943 – Thomas (Tommy) Flowers mengembangkan Colossus, sebuah komputer yang digunakan oleh Inggris sebagai pemecah kode untuk mesin Enigma cipher yang dibuat oleh pihak Jerman.
•1945 – John von Neumann menulis “First Draft of a Report on the EDVAC,” yang berisi konsep mengenai arsitekture dari media penyimpan modern untuk program komputer.
•1946 – ENIAC diperkenalkan, sebuah mesin penghitung elektronik yang dibuat oleh John Mauchly dan J. Presper Eckert.
•1947 – Pada 23 December, William Shockley, Walter Brattain, dan John Bardeen, sukses melakukan percobaan point-contact transistor, yang akhirnya menjadi revolusi dalam dunia semiconductor.
•1949 – Maurice Wilkes berhasil menyatukan EDSAC, media penyimpan program komputer yang pertama, di Cambridge University.
•1950 – Engineering Research Associates yang berpusat di Minneapolis membuat ERA 1101, komputer pertama yang diproduksi untuk komersial.
•1952 – UNIVAC I dikirim ke U.S. Census Bureau, komputer komersial pertama yang digunakan untuk memancing perhatian publik.
•1953 – IBM memasarkan komputer elektronik yang pertama, yaitu 701.
•1954 – Sebuah silicon-based junction transistor, disempurnakan oleh Gordon Teal dari Texas Instruments, Inc., yang memberikan kontribusi besar dalam hal pengurangan biaya produksi.
•1954 – IBM 650 magnetic drum calculator memantapkan dirinya sebagai komputer pertama yang diproduksi secara masal.
•1955 – Bell Laboratories mempublikasikan TRADIC, komputer pertama yang full transistorized.
•1956 – MIT melakukan penelitian untuk membuat TX-0, komputer transistor pertama yang bisa di program.
•1956 – Dijadikan sebagai era dari magnetic disk storage dengan dipasarkannya 305 RAMAC oleh IBM ke Zellerbach Paper di San Francisco.
•1958 – Jack Kilby berhasil membuat integrated circuit pertama di Texas Instruments, ini untuk membuktikan bahwa resistor dan kapasitor bisa bersatu dalam materi semiconductor yang sama.
•1959 – IBM’s 7000 series mainframes adalah komputer transistor pertama yang digunakan oleh perusahaan-perusahaan.
• 1959 – Robert Noyce’s mengaplikasikan integrated circuit yang berhasil meyakinkan Fairchild Camera dan Instrument Corp., untuk mencetak conducting channels secara langsung para permukaan silicon.
•1960 – Bell Labs mendesign Dataphone, yaitu modem komersial pertama, yang dikhususkan untuk mengkonversi data digital menjadi sinyal analog untuk di transmisikan pada jaringan yang luas.
•1960 – DEC’s PDP-1, terjual seharga $120,000, dari Precursor ke Minicomputer.
•1961 – Berdasarkan data dari majalah Datamation, IBM has menguasai 81,2% pasar komputer, dimana pada tahun itu juga seri 1400 diperkenalkan.
•1964 – CDC’s 6600 supercomputer, yang di design oleh Seymour Cray, mampu melakukan lebih dari tiga juga instruksi perdetik—kemampuan ini tiga kali lebih cepat di banding pesaing terdekatnya, IBM Stretch.
•1964 – IBM memperkenalkan System/360.
•1964 – Transaksi online menjadi debut bagi IBM’s SABRE reservation system, yang dibuat untuk American Airlines
•1965 – Digital Equipment Corp. memperkenalkan PDP-8, mini komputer komesial pertama yang sukses.
•1966 – Hewlett-Packard mulai memasuki dunia bisnis komputer dengan diluncurkannya HP-2115.
•1969 – Awal kelahiran internet saat Departemen Pertahanan US membuat 4 buah server untuk ARPAnet: dua di kampus University of California (satu di Santa Barbara dan satunya lagi di Los Angeles) yang ketiga di SRI International dan yang ke empat di University of Utah.
•1971 – Sebuah tim di IBM’s San Jose Laboratories berhasil membuat 8” floppy disk.
•1971 – Iklan pertama untuk sebuah microprocessor, Intel 4004, muncul di Electronic News.
•1971 – Kenbak-1, salah satu PC pertama di iklankan dan dijual dengan harga $750 di Scientific American.
•1972 – Hewlett-Packard mengumumkan HP-35 sebagai “a fast, extremely accurate electronic slide rule” dengan sebuah solid-state memory yang sama dari sebuah komputer.
•1972 – Intel’s 8008 microprocessor membuat debutnya.
•1972 – Steve Wozniak membuat “blue box,” sebuah tone generator untuk melakukan panggilan telephone secara gratis.
•1973 – Robert Metcalfe mengembangkan metode Ethernet dari network connection di Xerox Palo Alto Research Center.
•1973 – Micral, non-kit personal computer komersial pertama yang berbasis pada sebuah microprocessor, Intel 8008.
•1973 – TV Typewriter, yang di design oleh Don Lancaster, diperkenalkan.
•1974 – Para peneliti dari Xerox Palo Alto Research Center mendesign Alto, workstation pertama yang dilengkapi dengan sebuah built-in mouse sebagai input.
•1974 – Scelbi mengiklankan 8H computer-nya, komputer berbasis microprocessor (Intel’s 8008) pertama di US.
•1975 – Telenet, packet-switching network komesial dan civilian equivalent dari ARPAnet, lahir.
•1975 – Majalah Popular Electronics edisi Januari, memperkenalkan Altair 8800, yang berbasis pada microprocessor Intel’s 8080.
•1975 – Prototype dari Visual Display Module (VDM), di design oleh Lee Felsenstein, ditandai sebagai implementasi dari sebuah memory-mapped alphanumeric video display pertama untuk personal computers.
•1976 – Steve Wozniak mendesign Apple I, komputer dengan single-board.
•1976 – 5 1/4” flexible disk drive dan disk diperkenalkan oleh Shugart Associates.
•1976 – Cray I mencatatkan namanya sebagai Vector Processor komersial pertama yang sukses.
•1977 – Tandy Radio Shack memperkenalkan TRS-80.
•1977 – Apple Computer memperkenalkan Apple II.
•1977 – Commodore memperkenalkan PET (Personal Electronic Transactor).
•1978 – VAX 11/780 dari Digital Equipment Corp. memperkenalkan fitur virtual memory yang mampu mencapai 4.3GB, menyediakan ratusan kali kapasitas bagi banyak minicomputer.
•1979 – Motorola memperkenalkan microprocessor 68000.
•1980 – John Shoch, dari Xerox Palo Alto Research Center, mengembangkan “worm,” sebuah program kecil yang mencari network untuk idle processors.
•1980 – Seagate Technology hard disk drive pertama untuk microcomputers, ST-506.
•1980 – Optical data storage disk yang mempunyai kapasitas 60 kali dari sebuah 5 1/4” floppy disk, dibuat.
•1981 – Xerox memperkenalkan Star, personal computer pertama yang memiliki Graphical User Interface (GUI).
•1981 – Adam Osborne menyelesaikan Komputer portable yang pertama, Osborne I, yang mempunyai berat 24 lbs. dengan biaya $1,795.
•1981 – IBM memperkenalkan PC-nya, dan menjadi kakek moyangnya PC modern.
•1981 – Sony memperkenalkan 3 1/2” floppy disk dan drives pertama.
•1981 – Philips dan Sony memperkenalkan CD-DA (Compact Disc Digital Audio) drive. Sony adalah CD player pertama yang ada di pasaran.
•1983 – Apple memperkenalkan Lisa, yang bekerja dengan GUI, yang mana mirip dengan yang pertama kali diperkenalkan oleh Xerox Star.
•1983 – Compaq Computer Corp. memperkenalkan PC clone pertama yang menggunakan software yang sama dengan yang digunakan oleh IBM PC.
•1984 – Apple Computer meluncurkan Macintosh, komputer pertama yang dikendalikan oleh mouse dengan sebuah GUI.
•1984 – IBM merelease PC-AT (PC Advanced Technology), yang tiga kali lebih cepat dari PC originalnya, dan berbasis pada Intel 286 chip. The AT juga memperkenalkan 16-bit ISA bus dan menjadi basis bagi semua PC modern.
•1985 – Philips memperkenalkan CD-ROM drive pertama.
•1986 – Compaq mempublikasikan Deskpro 386, komputer pertama di pasaran yang menggunakan Intel’s new 386 chip.
•1987 – IBM memperkenalkan mesin PS/2, yang membuat 3 1/2” floppy disk drive dan VGA video standard untuk PC. PS/2 memperkenalkan MicroChannel Architecture (MCA) bus, plug-and-play bus pertama untuk PC.
•1988 – Steve Jobs cofounder dari Apple, meninggalkan Apple untuk mendirikan perusahaanya sendiri, NeXT.
•1988 – Compaq dan PC-clone lainnya menandai pengembangan Enhanced Industry Standard Architecture (EISA).
•1988 – Worm dari Robert Morris’s memenuhi ARPAnet. Yang menimbulkan masalah bagi 6,000 dari 60,000 hosts yang terhubung ke network.
•1989 – Intel merelease 486 (P4) microprocessor, yang berisi lebih dari satu juta transistors. Intel juga memperkenalkan chipsets untuk motherboard 486.
•1990 – World Wide Web (WWW) lahir saat Tim Berners-Lee, seorang peneliti dari CERN—the high-energy physics laboratory di Geneva—mengembangkan Hypertext Markup Language (HTML).
•1993 – Intel merelease Pentium (P5) processor. Intel juga merelease chipsets untuk motherboardnya.
•1995 – Intel merelease Pentium Pro processor, P6 processor family yang pertama.
•1995 – Microsoft merelease Windows 95, sistem operasi 32-bit yang pertama.
•1997 – Intel merelease Pentium II processor, yang secara essensial adalah Pentium Pro dengan tambahan MMX instructions.
•1997 – AMD memperkenalkan K6, yang kompatible dengan Intel P5 (Pentium).
•1998 – Microsoft merelease Windows 98.
•1998 – Intel merelease Celeron, versi hemat dari Pentium II processor.
•1999 – Intel merelease Pentium III, yang secara essensial adalah Pentium II dengan tambahan SSE (Streaming SIMD Extensions).
•1999 – AMD mempekenalkan Athlon.
•2000 – Microsoft meluncurkan Windows Me (Millennium Edition) dan Windows 2000.
•2000 – Intel and AMD memperkenalkan processors yang berkecepatan 1GHz
•2000 – AMD memperkenalkan Duron, Athlon versi hemat dengan pengurangan pada L2 cache.
•2000 – Intel memperkenalkan Pentium 4, processor terakhir Intel dengan Architecture 32-bit (IA-32) family.
•2001 – Intel mengeluarkan Itanium processor, processor 64-bit (IA-64) untuk PC.
•2001 – Industri komputer merayakan ulang tahun ke 20 untuk original IBM PC.
•2001- Intel memperkenalkan processor 2GHz pertama, sebuah versi lain dari Pentium 4.
•2001 – Microsoft merelease Windows XP edisi Home dan Professional, yang merupakan sistem operasi gabungan dari sistem operasi untuk konsumen rumahan (9x/Me), dan konsumen bisnis (NT/2000).
•2002 – Intel merelease processor 3GHz-class, sebuah versi 3.06GHz dari Pentium 4. Processor ini juga memperkenalkan Intel’s Hyper-Threading (HT) technology (yang membuat sebuah processor mampu mengerjakan dua threads aplikasi secara bersamaan) untuk komputer desktop.
•2003 – AMD merelease Athlon 64, processor 64-bit pertama, yang ditargetkan untuk konsumen mainstream dan pasar bisnis.

Jenis – jenis Kompter Berdasarkan :

Menurut Jenis Data Yang Diolah
1. Komputer Analog; adalah komputer yang bekerja secara paralel (analog) untuk mengolah data yang sifatnya kontinyu, datanya berupa besaran fisik dan angka-angka (kuantitatif) seperti temparatur, tekanan udara, kecepatan angin, arus listrik gelombang suara, dll
Contoh: Amperemeter, Voltmeter, Barometer, Termometer
2. Komputer Digital; adalah komputer yang bekerja berdasarkan operasi hitung. Variabel dalam komputer ini dinyatakan dengan angka-angka. Penyelesaian masalah dilakukan dengan proses aritmatik dan logik (kuantitatif).
Contoh: Calculator, Apple IIe, IBM PC
3. Komputer Hibrid; adalah komputer yang bekerja secara kualitatif dan kuantitatif. Komputer ini merupakan gabungan antara komputer analog dan komputer digital.
Contoh dari komputer jenis ini adalah komputer yang digunakan pada robot-robot yang dipakai sebagai pekerja pada pabrik.
2. Menurut Kemampuan Mengolah Data
1. Komputer ukuran kecil (Micro Computer)
2. Komputer ukuran sedang (Mini Computer)
3. Komputer ukuran besar (Large Computer)
4. Komputer ukuran super (Super Computer)

Menurut Bidang Masalah
1.General Purpose Computer; digunakan untuk menangani seluruh jenis masalah baik masalah bisnis maupun yang lainnya. Komputer jenis ini biasanya cocok untuk komputer pribadi (PC).
2.Special Purpose Computer; adalah komputer yang digunakan untuk menangani satu jenis masalah khusus. Komputer jenis ini biasanya telah diisikan suatu program kkomputer khusus, yang biasanya digunakan sebagai pengontrol proses-proses tertentu pada mesin pabrik, kepentingan militer atau pemeriksaan kesehatan. Dengan demikian bila ditinjau dari segi data yang diolah maka komputer jenis ini biasanya menggunakan koputer yang memiliki kemampuan hybrid.

Menurut Komponen Elektronika (Processor)
1.Mainframe Computer; Komputer jenis ini menggunakan prosessor yang mempunyai kemampuan yang sangat besar dan ditujukan untuk multi user. Dengan menggunakan teknologi time sharing maka efeknya tidak begitu dirasakan oleh user. Jenis Komputer ini memiliki suatu Central Processing Unit, Storage Device yang agak besar (kira-kira sebesar 2 lemari pakaian) dan ditempatkan pada tempat tersendiri. Peralatan CPU dan Storage tersebut dihubungkan dengan banyak terminal yang terdiri dari keyboard dan monitor saja. Terminal yang disambungkan dapat dalam jumlah ribuan sesuai dengan kebutuhan san seri dari komputer mainframenya. jenis komputer ini cocok digunakan untuk perusahaan dengan skala besar yang banyak memiliki banyak cabang.
2.Mini Computer; Kapasitas prosessor yang digunakan hampir sama dengan mainframe, hanya jumlah terminal yang dapat disambungkan ke dalam ke komputernya tidak sebanyak seperti pada jenis komputer mainframe. Jumlah terminal yang dapat disambungkan hanya puluhan. Oleh karena itu komputer jenis ini hanya cocok digunakan untuk perusahaan kelas menengah yang tidak begitu besar dan tidak terlalu kecil. Ukuran fisik komputer ini tidak sebesar komputer mainframe.
3.Personal Computer (PC); Jenis prosessor yang digunakan kemampuannya tidak begitu besar dibandingkan dengan komputer mainframe. Karena komputer ini memang ditujukan untuk seorang pemakai. Karena kegunaannya maka komputer jenis ini disebut komputer pribadi atau Personal Computer (PC). Komputer ini memiliki semua perangkat IPO yang telah dirangkai menjadi satu. Saat ini PC terus dikembangkan kemampuan dan kegunaannya.

Menurut Bentuk dan Ukuran Fisik
1.Komputer Desktop; Ukuran fisiknya lumayan kecil, biasanya cocok diletakkan di atas meja. Bhakan sekarang dikembangkan bentuk komputer desktop yang semakin tipis yang dikenal dengan bentuk desktop slim. Bentuk desktop ini bisanya dilengkapi dengan banyak ruang yang disebut expantion slot sebagai tempat untuk card tambahan.
2.Komputer Tower; Ukuran fisk relatif lebih besar dibandingkan dengan komputer jenis desktop, cocok untuk diletakkan di samping atau di atas meja. Memiliki ruang untuk expantion slot lebih banyak.
3.Komputer Portable; Ukuran fisiknya sedikti lebih kecil dari komputer desktop dan tower. Seluruh bagian-bagiannya dijadikan satu agar mudah dibawa kemana-mana. Jenis komputer ini diciptakan untuk orang yang sering bekerja berpindah-pindah atau dilapangan. Secara bebas portable artinya mudah dibawa-bawa.
4.Komputer Laptop; Adalah komputer dengan ukuran fisik yang dapat dipangku, ukurannya lebih kecil dari komputer portable, semua komponennya dibuat menyatu.
5.Komputer NoteBook; Sesuai dengan jenisnya ukuran fisik komputer ini sebesar notebook, bentuk dan ukurannya hampir sama dengan komputer Laptop.
6.Komputer SubNotebook; Ukurannya sebesar kertas kwarto, tebal kira-kira 5 cm, dan masih terus dikembangkan untuk mengecilkan ukurannya.
7.Komputer Palmtop; Komputer ini dibuat untuk bisa digenggam, bila dibandingkan dengan ukuran kaset kira-kira sebesar kaset video beta. Arus listriknya didapatkan lewat baterai.

Jenis – jenis Komputer Tabg Ada Saat Ini
1.PC atau Personal Computer
Sesuai dengan namanya personal komputer,maka PC adalah komputer yang ditujukan untuk pemakaian satu orang atau dimiliki secara pribadi. Sebelum PC ini muncul, komputer dahulunya berwujud sangat besar, sehingga hanya dimiliki oleh perusahaan tertentu saja. PC pertama bernama Altair yang diproduki oleh MITS pada tahun 1975.

2.Komputer Desktop
Yaitu komputer yang dirancang untuk tidak dapat dipindahkan-pindahkan, atau khusus dirancang untuk diletakkan disuatu tempat seperti diatas meja kerja. Komputer jenis ini sangat banyak beredar dipasaran, terutama dikalangan perguruan tinggi, kantor dan perusahaan.

3.Laptop
Dahulu istilah laptop berbeda dengan Notebook ditinjau dari segi ukuran, namun sekarang laptop atau notebook mengacu ke maksud yang sama, yaitu komputer portable (mudah dibawa-bawa) yang terintegrasi langsung dengan monitor, keyboard, mouse pad/trackbal, processor, harrdisk, memory dan peripheral lainnya dengan ukuran yang kecil dan ringan. Kemampunya bahkan melebihi komputer dekstop maupun PC..

4.PDA, Personal Digital Assistants
PDA adalah komputer canggih yang menggunakan flash memory sebagai pengganti media penyimpanan. PDA tidak memiliki keyboard, namun menggunakan teknologi layar sentuh (touchscreen) sebagai media input. PDA mempunyai ukuran yang sangat kecil, sedikit diatas ukuran handphone dan dapat dengan mudah dibawa kemana-mana.

5.Komputer Workstation
Workstation sebenarnya adalah komputer desktop yang memiliki kelebihan utama dalam hal kemampuan prosesor, memory yang besar, dan kemampuannya dalam menjalankan aplikasi-aplikasi yang membutuhkan performa tinggi, seperti aplikasi 3 dimensi, grafik, multimedia dan lain sebagainya.

6.Komputer Server
Server adalah komputer diperuntukan untuk menyediakan layanan terhadap komputer lainnya (client) dalam sebuah jaringan. Komputer server memiliki prosesor yang powerfull, memory yang besar dan kapasitas harddisk yang lebih besar.

7.Komputer Mainframe
Adalah komputer dengan ukuran besar yang mampu melayani ratusan program aplikasi secara bersamaan, mendukung puluhan bahasa pemrograman yang berbeda, mampu menyimpan dan mengakses library rutin dengan kapasitas yang besar, mampu melayani ratusan transaksi secara bersamaan, bahkan lebih dan kelebihan lainnya. Komputer ini biasanya berfungsi sebagai pusat data pada perusahaan besar. Namun dengan perkembangan zaman, komputer-komputer terbaru saat ini secara bertahap akan mampu menyaingi kelebihan dari komputer mainframe ini. Untuk ukuran yang sedang disebut dengan mini komputer dan ukuran lebih kecil disebut dengan mikro komputer.

8.Wearable Computer
Wearable Computer adalah perkembangan terbaru dalam bidang komputer, yaitu perangkat komputer menyatu seperti layaknya pakaian saja. Aplikasi-aplikasi yang biasa digunakan seperti email, database, multimedia, kalender terintegrasi langsung dengan jam tangan, handphone atau dalam bentuk lainnya. Sehingga perangkat komputer sudah menyatu dalam kehidupan kita sehari-hari.

Pada zaman yang sekarang ini perkembangan teknologi khusunya di bidang komputer sangatlah cepat.Hal ini di karenakan dengan kebutuhan manusia yang semakin tinggi dan Mobile. Sehengga harus di ikuti dengan Kemajaun Teknologi tang Signifikan.

Alogaritma

ALOGARITMA

Kata algoritma berasal dari latinisasi nama seorang ahli matematika dari Uzbekistan Al Khawārizmi (hidup sekitar abad ke-9), sebagaimana tercantum pada terjemahan karyanya dalam bahasa latin dari abad ke-12 "Algorithmi de numero Indorum". Pada awalnya kata algorisma adalah istilah yang merujuk kepada aturan-aturan aritmetis untuk menyelesaikan persoalan dengan menggunakan bilangan numerik arab (sebenarnya dari India, seperti tertulis pada judul di atas). Pada abad ke-18, istilah ini berkembang menjadi algoritma, yang mencakup semua prosedur atau urutan langkah yang jelas dan diperlukan untuk menyelesaikan suatu permasalahan.

algoritma merupakan kumpulan perintah untuk menyelesaikan suatu masalah. Perintah-perintah ini dapat diterjemahkan secara bertahap dari awal hingga akhir. Masalah tersebut dapat berupa apa saja, dengan catatan untuk setiap masalah, ada kriteria kondisi awal yang harus dipenuhi sebelum menjalankan algoritma. Algoritma akan dapat selalu berakhir untuk semua kondisi awal yang memenuhi kriteria, dalam hal ini berbeda dengan heuristik. Algoritma sering mempunyai langkah pengulangan (iterasi) atau memerlukan keputusan (logika Boolean dan perbandingan) sampai tugasnya selesai.
Desain dan analisis algoritma adalah suatu cabang khusus dalam ilmu komputer yang mempelajari karakteristik dan performa dari suatu algoritma dalam menyelesaikan masalah, terlepas dari implementasi algoritma tersebut. Dalam cabang disiplin ini algoritma dipelajari secara abstrak, terlepas dari sistem komputer atau bahasa pemrograman yang digunakan. Algoritma yang berbeda dapat diterapkan pada suatu masalah dengan kriteria yang sama.
Kompleksitas dari suatu algoritma merupakan ukuran seberapa banyak komputasi yang dibutuhkan algoritma tersebut untuk menyelesaikan masalah. Secara informal, algoritma yang dapat menyelesaikan suatu permasalahan dalam waktu yang singkat memiliki kompleksitas yang rendah, sementara algoritma yang membutuhkan waktu lama untuk menyelesaikan masalahnya mempunyai kompleksitas yang tinggi.
 

Jenis - Jenis Alogaritma:

• Alogaritma Divide and Conquer
  Divide and Conquer dulunya adalah strategi militer yang dikenal dengan nama divide ut imperes.
  Alogaritma Divide and Conquer Adalah mengabungkan solusi masing-masing upa-masalah sehingga membentuk solusi masalah semula.
  Contoh Alogaritma Divide and Conquer

  procedure DIVIDE_and_CONQUER(input n : integer) { Menyelesaikan masalah dengan algoritma D-and-C.   Masukan: masukan yang berukuran n   Keluaran: solusi dari masalah semula        } Deklarasi      r, k : integer Algoritma   if n £ n0 then  {ukuran masalah sudah cukup kecil }                        SOLVE upa-masalah yang berukuran n ini   else      Bagi menjadi r upa-masalah, masing-masing berukuran n/k      for masing-masing dari r upa-masalah do          DIVIDE_and_CONQUER(n/k)       endfor           COMBINE solusi dari r upa-masalah menjadi solusi masalah semula }   endif

  
  
   Jika pembagian selalu menghasilkan dua upa-masalah yang berukuran sama:
  
  

  procedure DIVIDE_and_CONQUER(input n : integer) { Menyelesaikan masalah dengan algoritma D-and-C.   Masukan: masukan yang berukuran n   Keluaran: solusi dari masalah semula        } Deklarasi      r, k : integer Algoritma   if n £ n0 then {ukuran masalah sudah cukup kecil }                   SOLVE upa-masalah yang berukuran n ini   else      Bagi menjadi 2 upa-masalah, masing-masing berukuran n/2      DIVIDE_and_CONQUER(upa-masalah pertama yang berukuran n/2)       DIVIDE_and_CONQUER(upa-masalah kedua yang berukuran n/2)         COMBINE solusi dari 2 upa-masalah    endif

  
  
  Kompleksitas Waktu algoritma:
  
  
  
                                     
  Persoalan Minimum dan Maksimum (MinMaks)
  ·         Persoalan: Misalkan diketahui tabel A yang berukuran n elemen sudah berisi nilai integer. Kita ingin menentukan nilai minimum dan nilai maksimum sekaligus di dalam tabel tersebut.
  
  
  
  
  Penyelesaian dengan Algoritma Brute Force
  
  
  
  

  procedure MinMaks1(input A : TabelInt, n : integer,                    output min, maks : integer) { Mencari nilai minimum dan maksimum di dalam tabel A yang berukuran n elemen, secara brute force. Masukan: tabel A yang sudah terdefinisi elemen-elemennya Keluaran: nilai maksimum dan nilai minimum tabel } Deklarasi     i : integer Algoritma:     min¬ A1   { inisialisasi nilai minimum}     maks¬A1   { inisialisasi nilai maksimum }     for i¬2 to n do       if Ai < min then        min¬Ai       endif       if Ai > maks then        maks¬Ai       endif          endfor

             
  
  
  Jika T(n) dihitung dari  jumlah perbandingan elemen-elemen tabel:
  
  
                          T(n) = (n – 1) + (n – 1)
          = 2n – 2
          = O(n)
  
  
  
  
  Penyelesaian dengan Algoritma Divide and Conquer
  
  
  Contoh 4.1. Misalkan tabel A berisi elemen-elemen sebagai berikut:
  
  
  4          12        23        9          21        1          35        2          24       
  
  
  Ide dasar algoritma secara Divide and Conquer: 
  
  
  
  
  4          12        23        9          21        1          35        2          24       
   
  
  
                                                     DIVIDE
  
  
  4          12        23        9          21        1          35        2          24       
  
  
   
  
  
                                 SOLVE: tentukan min &
         maks pada  tiap bagian
  
  
  4          12        23        9          21        1          35        2          24       
              min = 4                                    min = 1
              maks = 23                                maks = 24
   
  
  
  
  
  
  
   COMBINE
  
  
  4          12        23        9          21        1          35        2          24       
              min = 1                                               
              maks = 24                               
    
  Ukuran tabel hasil pembagian dapat dibuat cukup kecil sehingga mencari minimum dan maksimum dapat diselesaikan (SOLVE) secara lebih mudah. Dalam hal ini, ukuran kecil yang dipilih adalah 1 elemen atau 2 elemen.
  
  
  Algoritma MinMaks:
  
  
  1.      Untuk kasus n = 1 atau n = 2,
         SOLVE:  Jika n = 1, maka min = maks = A_n.
                         Jika n = 2, maka bandingkan kedua elemen untuk
               menentukan min dan maks.
  2.      Untuk kasus n > 2,
  (a)      DIVIDE: Bagi dua tabel A secara rekursif menjadi dua bagian yang berukuran sama, yaitu bagian kiri dan bagian kanan.
  
  
  (b)        CONQUER: Terapkan algoritma Divide and Conquer untuk masing-masing bagian, dalam hal ini min dan maks dari tabel bagian kiri dinyatakan dalam peubah min1 dan maks1, dan min dan maks dari tabel bagian kanan dinyatakan dalam peubah min2 dan maks2.
  
  
  (c)      COMBINE:
   Bandingkan min1 dengan min2 untuk menentukan min tabel A
  Bandingkan maks1 dengan maks2 untuk menentukan maks tabel A.
  
  
  
  
  • Dynamic programming, paradigma pemrograman dinamik akan sesuai jika digunakan pada suatu masalah yang mengandung sub-struktur yang optimal (, dan mengandung beberapa bagian permasalahan yang tumpang tindih . Paradigma ini sekilas terlihat mirip dengan paradigma Divide and Conquer, sama-sama mencoba untuk membagi permasalahan menjadi sub permasalahan yang lebih kecil, tapi secara intrinsik ada perbedaan dari karakter permasalahan yang dihadapi.
  
  
  • Metode serakah. Sebuah algoritma serakah mirip dengan sebuah Pemrograman dinamik, bedanya jawaban dari submasalah tidak perlu diketahui dalam setiap tahap; dan menggunakan pilihan "serakah" apa yang dilihat terbaik pada saat itu.