Bagaimana merumuskan masalah komputasi secara ketat?

20

Saya sering berinteraksi dengan orang-orang yang ingin meminta algoritma untuk masalah komputasi (atau kerumitannya), tetapi mereka tidak mengungkapkannya dengan cara yang sulit bagi kita (ilmuwan komputer) untuk memahaminya.

Merujuk mereka ke buku-buku seperti CLRS tidak membantu karena contoh-contoh di sana biasanya memiliki cara yang cukup mudah untuk menyatakan dengan keras, misalnya diberikan daftar adjacency grafik dan dua simpul di dalamnya menghitung jalur terpendek antara simpul-simpul tersebut.

Apakah ada buku bagus (atau sumber daya lain) di mana seseorang dengan pengetahuan CS minimal dapat belajar bagaimana seseorang harus merumuskan dan menyatakan masalah komputasi dengan cara yang ketat yang dapat dimengerti oleh para ilmuwan komputer?

Lebih disukai buku itu harus memiliki banyak contoh bagaimana merumuskan masalah komputasi secara ketat dari berbagai domain dan contoh dunia nyata.

Klarifikasi

Untuk membuat pertanyaan lebih spesifik, mari kita asumsikan bahwa mereka tahu dasar matematika / terminologi CS seperti set, fungsi, grafik, daftar, dll. Pada level 1/2 tahun mahasiswa CS sarjana (yang merupakan kasus dengan orang-orang yang saya miliki di pikiran). Sebagai contoh, mereka telah membaca beberapa buku pelajaran pengantar seperti Aho dan Ullman (walaupun mereka mungkin tidak mengerti sepenuhnya).

algorithms reference-request books Kaveh
sumber
2
Saya pikir ini adalah pertanyaan yang bagus, tetapi saya tidak tahu apakah ada jawaban yang bagus. Saya merasa seperti bertanya, "Apakah ada cara kita bisa mengajar seseorang yang bukan ilmuwan komputer untuk berpikir seperti ilmuwan komputer?" Dan jawabannya adalah "ya, jadikan mereka ilmuwan komputer." Yang mengatakan, beberapa peneliti rekayasa perangkat lunak mungkin telah melakukan studi pada hal-hal seperti ini.
jmite
3
Juga, saya pikir inilah gunanya, untuk tingkat tertentu. Jika seseorang tidak mengerti cara merumuskan masalah mereka dengan benar, buatlah daftar sejumlah skenario tentang apa yang ingin mereka lakukan, dan perilaku yang diharapkan dalam setiap kasus. Programmer kemudian mengembangkan spesifikasi dari itu. Yang mengatakan, saya adalah orang teori, bukan insinyur, jadi jika saya salah, jangan ragu untuk mengoreksi saya.
jmite
@iteite, terima kasih atas komentarnya. Anda benar bahwa bagian dari Rekayasa Perangkat Lunak adalah untuk mencoba memahami apa yang diinginkan klien (saya pikir mereka menyebutnya analisis kebutuhan ). Tapi itu biasanya untuk proyek besar. Saya tidak berbicara tentang proyek-proyek seperti itu, tetapi pertanyaan-pertanyaan sederhana seperti yang kami dapatkan di situs ini yang tidak disebutkan dengan tegas. Saya telah melihat buku-buku yang mengajarkan orang bagaimana menyatakan pernyataan dalam logika dengan banyak contoh. Saya berharap ada sesuatu yang serupa untuk algoritma dan masalah komputasi.
Kaveh
1
Yang mengatakan, saya berpendapat itu membutuhkan cara berpikir tertentu yang tidak mudah didapat, terutama oleh orang dewasa. Saya telah mencoba membuat orang untuk menjatuhkan barang-barang teknis dan menjelaskan masalahnya sesederhana mungkin dalam hal benda sehari-hari. Masalahnya adalah, mereka biasanya akan melupakan beberapa kendala, atau mereka akan membuatnya terdengar seperti operasi yang O (N) dalam sistem mereka yang sebenarnya adalah O (1), dan seterusnya. Jadi saya akan berakhir dengan sesuatu yang sangat dekat dengan definisi yang ketat tentang masalah yang salah.
svinja
2
dalam satu hal, apa yang diminta itu kontradiktif, karena merumuskan masalah secara ketat adalah salah satu keterampilan utama yang dipelajari yang memisahkan orang awam dari spesialis / profesional ...
vzn

Jawaban:

3

sumber yang bagus untuk hal ini, yang cukup dikenal oleh para akademisi tetapi tidak begitu banyak dikenal di luar spesialis, adalah Penulisan Matematika oleh Donald E. Knuth, Tracy L. Larrabee, dan Paul M. Roberts. ada buku yang diterbitkan, video ceramah, dan satu set catatan. ini lebih ditulis dari sudut pandang orang yang berusaha menguasai penulisan matematika misalnya untuk membuat makalah, tetapi semua saran sangat berlaku untuk kasus orang awam yang berusaha merumuskan masalah secara tepat. penulisan matematis yang sulit dipelajari adalah pendekatan ilmiah untuk mendefinisikan / merumuskan dengan teliti — dan ketika buku ini merinci, menyelesaikannya , misalnya melalui algoritme atau bukti — masalah komputasi / algoritmik.

juga, teks klasik Garey & Johnson, Computers & Intractability tidak persis menggambarkan bagaimana merumuskan masalah secara tepat, tetapi ia memberikan banyak contoh, dan beragam "pola" teoretis / konseptual / teknis, yang diorganisir menjadi beberapa bagian dari masalah serupa, yang dapat digunakan sebagai "blok bangunan" untuk menggambarkan masalah komputasi / algoritmik.

vzn
sumber
Terima kasih vzn, ini adalah sumber yang bagus tentang menulis matematika tetapi saya tidak mencari sesuatu yang berbeda. Masalahnya bukan menulis dengan baik dalam matematika tetapi sumber daya bagi orang untuk belajar bagaimana merumuskan masalah komputasi dengan cukup jelas sehingga seorang ahli dapat memahami apa yang dicari orang yang mengajukan pertanyaan dan membantu mereka.
Kaveh
yw; Anda mengatakan itu adalah dua hal yang berbeda, dan dalam kata-kata / frasa mereka, tapi & saya katakan mereka [untuk meminjam frase rekayasa perangkat lunak] "erat"
vzn
3

hanya berlari melintasi ref bagus / rapi, tidak biasa, relatif baru / tidak diketahui ini di halaman rumahnya oleh Emmanuele Viola , prof (T) CS di Northeastern University) tampaknya tidak dipublikasikan di tempat lain. 41pp. dimulai dengan konsep-konsep matematika yang sangat mendasar misalnya implikasi dan kemudian merambah ke topik-topik lanjutan seperti teorema Erdős-Szekeres dan Ramsey .

vzn
sumber
0

Beli buku Algoritma dan Struktur Data dari Robert Lafore.

Dalam buku ini, setiap algoritma dijelaskan sebagai sebuah cerita, sangat mirip puisi. Kemudian, berikan orang itu versi algoritma Lafore, dan kemudian versi CLRS.

Mungkin seperti ini, orang tersebut akan merasakan bagaimana menerjemahkan dari deskripsi intuitif ke yang ketat.

pengguna5193682
sumber