Skip to content

Latest commit

 

History

History
357 lines (279 loc) · 23 KB

pembelajaran-tambahan.md

File metadata and controls

357 lines (279 loc) · 23 KB

Pembelajaran Tambahan

Saya menambahkannya untuk membantu Anda menjadi insinyur perangkat lunak yang berpengetahuan luas, dan untuk mengetahui teknologi dan algoritme tertentu, sehingga Anda akan memiliki kotak peralatan yang lebih besar.

Kompilator

Emacs and vi(m)

Unix command line tools

  • Saya mengisi daftar di bawah ini dari alat yang bagus.
  • bash
  • cat
  • grep
  • sed
  • awk
  • curl or wget
  • sort
  • tr
  • uniq
  • strace
  • tcpdump

Teori Informasi (video)

Pariti & Kode Hamming

Entropy

Kriptografi

Kompresi

Keamanan komputer

Pengumpulan sampah

Pemrograman Paralel

Pengiriman Pesan, Serialisasi, dan Sistem Queueing

A*

Transformasi Fourier Cepat

Bloom Filter

HyperLogLog

Locality-Sensitive Hashing

van Emde Boas Trees

Augmented Data Structures

Balanced search trees

  • Ketahui setidaknya satu jenis pohon biner yang seimbang (dan ketahui bagaimana implementasinya):

  • "Di antara pohon pencarian seimbang, AVL dan 2/3 trees sekarang sudah ketinggalan zaman, dan red-black trees tampaknya lebih populer. Struktur data pengorganisasian mandiri yang sangat menarik adalah splay trees, yang menggunakan rotasi untuk memindahkan kunci apa pun yang diakses ke root." - Skiena

  • Dari jumlah tersebut, saya memilih untuk menerapkan splay tree. Dari apa yang saya baca, Anda tidak akan menerapkan pohon pencarian seimbang (balanced search tree) dalam wawancara Anda. Tapi saya ingin eksposur ke pengkodean satu dan hadapi saja, splay trees adalah lutut lebah. Saya memang membaca banyak kode red-black tree code

    • Splay tree: menyisipkan, mencari, menghapus fungsi Jika Anda akhirnya menerapkan pohon merah / hitam coba ini saja:
    • Fungsi pencarian dan penyisipan, melewatkan penghapusan

  • Saya ingin mempelajari lebih lanjut tentang B-Tree karena digunakan secara luas dengan kumpulan data yang sangat besar

  • Self-balancing binary search tree

  • AVL trees

    • Dalam praktek: Dari apa yang saya tahu, ini tidak banyak digunakan dalam praktiknya, tetapi saya bisa melihat di mana mereka akan berada: AVL trees (Pohon AVL) adalah struktur lain yang mendukung pencarian, penyisipan, dan penghapusan O(log n). Ini lebih seimbang daripada red-black trees, menyebabkan penyisipan dan pemindahan lebih lambat tetapi pengambilan lebih cepat. Ini membuatnya menarik untuk struktur data yang dapat dibangun sekali dan dimuat tanpa rekonstruksi, seperti kamus bahasa (atau kamus program, seperti opcode assembler atau interpreter)
    • MIT AVL Trees / AVL Sort (video)
    • AVL Trees (video)
    • Implementasi AVL Tree (video)
    • Split Dan Merge

  • Splay trees

    • Dalam praktek: Splay trees (pohon bentang) biasanya digunakan dalam implementasi cache, pengalokasi memori, router, pengumpul sampah, kompresi data, tali (pengganti string yang digunakan untuk string teks panjang), di Windows NT (dalam memori virtual, jaringan, dan kode sistem file) dll.
    • CS 61B: Splay Trees (video)
    • Kuliah MIT: Splay Trees:
      • Menjadi sangat matematis, tetapi perhatikan 10 menit terakhir dengan pasti.
      • Video

  • Red/black trees

    • Ini adalah terjemahan dari sebuah 2-3 tree (lihat dibawah).
    • Dalam praktek: Red/black trees (Pohon merah / hitam) menawarkan jaminan kasus terburuk untuk waktu penyisipan, waktu penghapusan, dan waktu pencarian. Hal ini tidak hanya membuatnya berharga dalam aplikasi yang sensitif terhadap waktu seperti aplikasi waktu nyata, tetapi juga menjadikannya sebagai blok bangunan yang berharga dalam struktur data lain yang memberikan jaminan kasus terburuk; sebagai contoh, banyak struktur data yang digunakan dalam geometri komputasi dapat didasarkan pada red/black trees, dan Penjadwal yang Benar-Benar Adil yang digunakan dalam kernel Linux saat ini menggunakan red/black trees. Di Java versi 8, Collection HashMap telah dimodifikasi sedemikian rupa sehingga alih-alih menggunakan LinkedList untuk menyimpan elemen identik dengan kode hash yang buruk, red/black trees digunakan
    • Aduni - Algoritma - Kuliah 4 (link lompat ke titik awal) (video)
    • Aduni - Algoritma - Kuliah 5 (video)
    • Red-Black Tree
    • Pengantar Pencarian Biner Dan Red-Black Tree

  • 2-3 search trees

  • 2-3-4 Trees (aka 2-4 trees)

    • Dalam praktek: Untuk setiap 2-4 trees, ada red–black trees yang sesuai dengan elemen data dalam urutan yang sama. Operasi penyisipan dan penghapusan pada 2-4 trees juga setara dengan pembalikan warna dan rotasi pada red–black trees. Hal ini membuat 2-4 trees menjadi alat penting untuk memahami logika di balik red–black trees, dan inilah mengapa banyak teks algoritme pengantar memperkenalkan 2-4 trees tepat sebelum red–black trees, meskipun 2-4 trees tidak sering digunakan dalam praktik.
    • CS 61B Kuliah 26: Pohon Pencarian Seimbang (video)
    • Bawah Atas 234-Trees (video)
    • Atas Bawah 234-Trees (video)

  • N-ary (K-ary, M-ary) trees

    • catatan: N atau K adalah faktor percabangan (cabang maks)
    • pohon biner adalah pohon 2-ary, dengan faktor percabangan = 2
    • 2-3 pohon adalah 3-ary
    • K-Ary Tree

  • B-Trees

    • Fakta menyenangkan: ini adalah misteri, tetapi B bisa berarti Boeing, Balanced, atau Bayer (co-inventor).
    • Dalam praktek: B-Trees banyak digunakan dalam database. Kebanyakan filesystem modern menggunakan B-tree (atau Variants). Sebagai tambahannya penggunaannya dalam database, B-tree juga digunakan dalam sistem file untuk memungkinkan akses acak cepat ke sembarang blokir di file tertentu. Masalah dasarnya adalah mengubah alamat file blok i menjadi blok disk (atau mungkin ke alamat sektor kepala silinder)
    • B-Tree
    • Struktur Data B-Tree
    • Pengantar B-Trees (video)
    • Definisi dan Penyisipan B-Tree (video)
    • Penghapusan B-Tree (video)
    • MIT 6.851 - Model Hirarki Memori (video) - covers cache-oblivious B-Trees, very interesting data structures - the first 37 minutes are very technical, may be skipped (B is block size, cache line size)

k-D Trees

Skip lists

-"Ini adalah semacam struktur data kultus" - Skiena

Aliran Jaringan

Disjoint Sets & Union Find

Matematika untuk Pemrosesan Cepat

Treap

Pemrograman Linear (video)

Geometry, Convex hull (video)

Matematika diskrit

  • lihat video di bawah ini

Pembelajaran Mesin (Machine Learning)

Selanjutnya - Detail Tambahan tentang Beberapa Subjek