Saya ingin menganggap diri saya seorang programmer yang cukup berpengalaman. Saya sudah pemrograman selama lebih dari 5 tahun sekarang. Titik lemah saya adalah terminologi. Saya belajar sendiri, jadi sementara saya tahu cara memprogram, saya tidak tahu beberapa aspek formal dari ilmu komputer. Jadi, apa algoritma / struktur data praktis yang bisa saya kenali dan ketahui namanya?

Catatan, saya tidak meminta rekomendasi buku tentang penerapan algoritma. Saya tidak peduli tentang penerapannya, saya hanya ingin bisa mengenali kapan algoritma / struktur data akan menjadi solusi yang baik untuk suatu masalah. Saya meminta lebih banyak untuk daftar algoritma / struktur data yang harus saya "kenali". Misalnya, saya tahu solusi untuk masalah seperti ini:

Anda mengelola satu set loker berlabel 0-999. Orang-orang mendatangi Anda untuk menyewa loker dan kemudian kembali untuk mengembalikan kunci loker. Bagaimana Anda membangun perangkat lunak untuk mengelola mengetahui loker mana yang gratis dan mana yang digunakan?

Solusinya, akan berupa antrian atau tumpukan.

Apa yang saya cari adalah hal-hal seperti "dalam situasi apa B-Tree harus digunakan - Algoritma pencarian apa yang harus digunakan di sini" dll. Dan mungkin pengantar cepat tentang bagaimana struktur data yang lebih kompleks (tetapi umum digunakan) / algoritma bekerja.

Saya mencoba melihat daftar Wikipedia struktur data dan algoritma tetapi saya pikir itu agak berlebihan. Jadi saya mencari lebih banyak hal penting apa yang harus saya kenali?

Respons objektif:

Sementara tanggapan awal saya terhadap pertanyaan ini didasarkan pada pengalaman empiris saya sebagai mahasiswa CS yang akan segera lulus dan pendapat saya yang diproyeksikan tentang tipe orang yang ingin saya ajak bekerja di bidang CS. Sebenarnya ada tujuan (sehubungan dengan pendapat subjektif dari ACM SIGCSE dan masyarakat komputasi IEEE) jawaban. Setiap 10 tahun ACM dan badan-badan IEEE bekerja sama dalam publikasi bersama yang merinci saran-saran untuk kurikulum ilmu komputer sarjana berdasarkan pengetahuan profesional dari keadaan industri komputasi. Informasi lebih lanjut dapat ditemukan di cs2013.org . Komite menerbitkan laporan akhir yang berisi daftar rekomendasi kurikulum mereka .

Yang mengatakan, saya masih berpikir daftar saya cukup bagus.

Jawaban asli di bawah ini.

Apa yang Harus Saya Ketahui?

Minimum

Saya pikir seorang programmer mahir harus memiliki setidaknya pengetahuan tingkat sarjana dalam Ilmu Komputer. Tentu, Anda bisa efektif di banyak pekerjaan dengan hanya sebagian kecil Ilmu Komputer karena komunitas CS yang solid, dan fokus yang sempit dari sebagian besar posisi profesional. Juga, banyak orang akan lebih mengkhususkan diri setelah studi sarjana. Namun, saya tidak berpikir baik adalah alasan untuk tidak mengetahui rahasia pengetahuan CS dasar.

Untuk menjawab pertanyaan judul, inilah yang harus diketahui oleh mahasiswa CS sarjana (dasar untuk seorang programmer mahir) setelah lulus:

Struktur data

• Representasi Data Mesin
  • Yang, Komplemen Dua, dan Aritmatika Terkait
  • Kata-kata, Pointer, Floating Point
  • Akses Bit, Pergeseran, dan Manipulasi
• Daftar Tertaut
• Hash Tables (peta atau kamus)
• Array
• Pohon
• Tumpukan
• Antrian
• Grafik
• Database

Algoritma

• Penyortiran:
  • Sortir Bubble (untuk mengetahui mengapa itu buruk)
  • Penyisipan Sortir
  • Gabungkan Sortir
  • Sortir Cepat
  • Jenis gaya radix, Sorting Counting dan Bucket Sort
  • Heap Sort
  • Bogo dan Urut Kuantum (=
• Mencari:
  • Pencarian Linier
  • Pencarian Biner
  • Pencarian Pertama Kedalaman
  • Luasnya Pencarian Pertama
• Manipulasi String
• Perulangan
• Traversal Pohon
• Daftar Traversal
• Fungsi Hashing
• Implementasi konkret dari Tabel Hash, Pohon, Daftar, Stack, Antrian, Array, dan Set atau Koleksi
• Algoritma Penjadwalan
• Traversal dan Manipulasi Sistem File (pada inode atau level yang setara).

Pola desain

• Modularisasi
• Pabrik
• Pembangun
• Singleton
• Adaptor
• Penghias
• Kelas terbang
• Pengamat
• Iterator
• Negara [Mesin]
• Pengontrol Tampilan Model
• Pola Pemrograman Threading dan Paralel

Paradigma

• Imperatif
• Berorientasi pada objek
• Fungsional
• Deklaratif
• Pemrograman Statis dan Dinamis
• Markup Data

Teori Kompleksitas

• Ruang Kompleksitas
• Komputasi
• Regular, Context Free, dan Universal Turing Machine melengkapi Bahasa
• Ekspresi Reguler
• Penghitungan dan Kombinatorik Dasar

Luar

Untuk mengetahui apa yang Anda tanyakan nanti dalam pertanyaan Anda, jika Anda terbiasa dengan hal di atas, Anda harus dapat dengan mudah mengidentifikasi pola, algoritma, dan struktur data yang sesuai untuk skenario tertentu. Namun, Anda harus menyadari bahwa seringkali tidak ada solusi terbaik. Kadang-kadang Anda mungkin diminta untuk memilih yang kurang dari dua kejahatan atau bahkan hanya memilih di antara dua solusi yang sama-sama layak. Karena itu, Anda perlu pengetahuan umum untuk dapat mempertahankan pilihan Anda terhadap rekan-rekan Anda.

Berikut ini beberapa kiat untuk algoritma dan struktur data:

• Pencarian Biner hanya dapat (dan harus) digunakan pada data yang diurutkan.
• Jenis gaya radix mengagumkan, tetapi hanya ketika Anda memiliki kelas terbatas hal-hal yang diurutkan.
• Pohon baik untuk hampir semua hal seperti halnya Hash Tables. Fungsi dari Tabel Hash dapat diekstrapolasi dan digunakan untuk menyelesaikan banyak masalah dengan biaya efisiensi.
• Array dapat digunakan untuk mendukung sebagian besar struktur data tingkat yang lebih tinggi. Kadang-kadang "struktur data" tidak lebih dari beberapa matematika pintar untuk mengakses lokasi dalam array.
• Pilihan bahasa bisa menjadi perbedaan antara menarik rambut Anda keluar, atau berlayar melalui, masalah.
• Tabel ASCII dan 128 elemen array membentuk tabel hash implisit (=
• Ekspresi reguler dapat memecahkan banyak masalah, tetapi tidak dapat digunakan untuk mem-parsing HTML .
• Terkadang struktur data sama pentingnya dengan algoritma.

Beberapa di atas mungkin tampak seperti tidak punya otak, dan beberapa mungkin tampak tidak jelas. Jika Anda ingin saya membahas lebih detail, saya bisa. Tapi, harapan saya adalah ketika bertemu dengan pertanyaan yang lebih konkret seperti, "Desain fungsi yang menghitung jumlah kemunculan setiap karakter dalam sebuah String", Anda melihat ke ujung tentang tabel ASCII dan 128 elemen array membentuk hash implisit yang rapi tabel untuk jawabannya.

Berdasarkan ide-ide ini, saya akan mengusulkan jawaban masalah loker yang diuraikan dalam pertanyaan Anda.

Jawaban untuk masalah yang diajukan dalam pertanyaan Anda.

Ini mungkin bukan jawaban terbaik untuk pertanyaan Anda, tetapi saya pikir ini adalah jawaban yang menarik yang tidak memerlukan hal yang terlalu rumit. Dan itu pasti akan mengalahkan kompleksitas waktu menggunakan antrian, atau tumpukan yang membutuhkan waktu linier untuk menentukan apakah loker gratis atau tidak.

Anda memiliki 0-999 loker. Sekarang, karena Anda memiliki jumlah loker yang tetap, Anda dapat dengan mudah membayangkan fungsi hashing tanpa tabrakan pada rentang 0-999. Fungsi ini cukup h (x) = x mod 1000. Sekarang, [secara konseptual] buat tabel hash dengan kunci integer dan isi array elemen 1000 sebagai nilai Anda. Jika pelanggan ingin memesan loker 78 untuk digunakan, cukup masukkan 78 ke fungsi hash (mengembalikan 78), dan kemudian tambahkan angka itu ke pointer dasar array - menyimpan nilai sebenarnya di lokasi yang ditunjuk oleh nilai offset . Demikian pula, jika Anda perlu memeriksa apakah 78 sedang digunakan, cukup baca nilai yang disimpan di lokasi itu dan periksa benar.

Solusi ini beroperasi dalam waktu yang konstan untuk pencarian dan penyimpanan yang bertentangan dengan penyimpanan dan pencarian waktu log (n) dalam hal antrian prioritas yang didukung oleh pohon biner. Deskripsi ini sengaja diverbose sehingga Anda dapat melihat konsep yang lebih tinggi dirubah menjadi algoritma yang efisien.

Sekarang, Anda mungkin bertanya, bagaimana jika saya perlu mengetahui semua loker yang tersedia, bukankah antrian prioritas lebih baik? Jika ada k loker yang tersedia di antrian prioritas, iterasi atas semuanya akan mengambil langkah k. Selanjutnya, tergantung pada implementasi antrian prioritas Anda, Anda mungkin harus membangun kembali antrian prioritas saat Anda melihat semuanya .. yang akan mengambil langkah k * log (k): (k <1000). Dalam solusi array, Anda hanya perlu mengulang dari array elemen 1000 dan memeriksa mana yang terbuka. Anda juga dapat menambahkan daftar yang tersedia atau bekas ke dalam implementasi untuk memeriksa waktu k saja.

Manual Desain Algoritma oleh Steven S. Skiena sepertinya adalah sumber yang Anda cari. Bagian kedua adalah daftar masalah dengan ulasan tentang algoritma terkait. Ada versi web .

Tidak ada "seharusnya". A. Berkenalan dengan kelas kompleksitas dasar (linier, logaritmik, dll.) B. Sadarilah bahwa Anda dapat melakukan apa saja dengan array sederhana yang Anda bisa dengan struktur data mewah seperti B-tree. Trik dalam memilih struktur / algoritma yang tepat terletak pada keseimbangan kinerja, ukuran input yang diharapkan dan kompleksitas implementasi.

Lalu ada hal-hal abstrak tetapi sangat berguna (meskipun kegunaannya tidak segera jelas): mesin negara, teori grafik, teori konveksitas (pemrograman linier, dll).

MIT menerbitkan catatan kuliah gratis, video, tugas dan materi ujian untuk Pengantar Algoritma . The judul ceramah daftar algoritma / struktur data tertutup.

Ini adalah konsensus peer-review tentang apa yang harus Anda ketahui. Mungkin sumber belajar yang bagus juga.