- Published on
Software Development Fundamentals(ソフトウェア開発基礎)
- Authors
- Name
- ryyta
- @fubar1346
概要
- ソフトウェア開発に必要な基本概念と技術を扱う
- コンピュータサイエンスプログラムの初年度で習得すべき概念とスキルを示し、アルゴリズムの設計と簡単な解析、プログラミングの基本概念とデータ構造、基本的なソフトウェア開発方法とツールを学ぶ
目的
- ソフトウェア開発における基礎となる概念をまず浅く広く学び、今後Programming Languages、Algorithms and Complexity、Software Engineeringを学ぶ基礎を作る
目標
- ソフトウェア開発の全体を念頭に、開発の中で理解しておく概念(アルゴリズム、データ構造、ソフトウェア開発の基礎知識等)について非プログラマーに対してそれぞれの役割と概要について説明できる
リソース
- CS50
- 約180minの講義 x 10 weeks + CyberSecurity50min = 約30時間
- 『プログラミングの基礎』
- 「デザインレシピ」というアプローチを用いたプログラムの実装方法とデータ構造とアルゴリズムについて
学習まとめ
CS50
- Lectures
- Week 0: Scratch
- Week 1: C
- Week 2: Arrays
- Week 3: Algorithms
- Week 4: Memory
- Week 5: Data Structures
- Week 6: Python
- Week 7: SQL
- Week 8: HTML, CSS, JavaScript
- Week 9: Flask
- Week 10: Emoji
- Cybersecurity
ハーバード大学で行われているコンピュータサイエンスの入門講座。
受講生のうち約2/3程度がプログラミング未経験者で、講義を通じてコンピュータサイエンスの入門から実際のプログラムの構築までを学ぶ基礎講座なので Software Delelopment Fundamentals
として採用。
コンピュータサイエンスとは何か、2進数やバイナリ、アルゴリズム、Scratchを用いたプログラミングの概要からスタートする。
Week1からは実際のプログラミングを通してデータ構造やアルゴリズムについて理解するためにC言語を用いた内容になる。
適宜受講生からの質問を受け付る時間を設けているが、「この質問をしたら恥ずかしいかな」というような日本では良くある質問を恐れるような雰囲気はなく、 どんなことでも質問する受講生の積極性と、どんな質問でも真摯かつ丁寧に答える講師の姿勢が印象強い。
「どんな質問も肯定する」「少しズレた質問でもそれに答える形の回答をする」という講師の姿勢が特に印象強く、良い環境だなーと思った。
閑話休題。
データ構造やアルゴリズムの実装から動作確認も行っていくが、その際のコンパイルという仕組みからバイナリとマシンコードの違いやコンパイラの内部挙動(preproccessing/compiling/assembling/linking)についての話もあり、CSを学んできていないエンジニアであればWeek1といえど学ぶことが多いのでは。
アルゴリズムについては、計算量について最悪計算量を表現するビッグO(ビッグオー)記法、裁量計算量を示すビッグΩ(ビッグオメガ)記法、最悪・最良ともに同じ場合に用いられるビッグΘ(ビッグシータ)記法の3つの記法を用いて説明する。
特に強調されていることは、
- アルゴリズムの効率性という観点で重要なことは「何を繰り返し実行しているかだけ」であり、ループでn回繰り返すような処理に注目し、それ以外の瑣末なことは無視して良い
- 時間とリソースはトレードオフの関係にあり、早くこなしたいのであれば使用するリソースが増える、リソースを節約したいのであれば時間が増える
上記については何度も強調した説明がある。
プログラムを作る場合には必ず時間的な制約かリソース的な制約が存在するので、アルゴリズムを考える場合にはどちらを優先するべきなのかを考えることは必須。銀の弾丸はない。
アルゴリズムの講義では、まずコードを書かない形でのアルゴリズムの説明などが行われ、そこからコードに落とし込んでいくため、アルゴリズムの実装のアプローチ自体も参考になった。
プログラミングにおけるアルゴリズムは数学とは違い厳密な数値を表現するのではなくあくまでも目安としての計算量に着目する必要があるが、 これまでは個人的には計算量・アルゴリズムについては苦手意識も強かった。
ただ講義でピックアップするアルゴリズム(選択ソート、バブルソート、マージソート)については計算量の観点からも解説があるので、だいぶん理解がマシになったのではと感じる。
一方でその他の場合のものについてはまだまだ計算量の計算が苦手なので、ここは今後も練習していきたいし、このプロジェクト後に特に取り組むべき課題として挙げておきたい。
Week4ではメモリを扱う。
16進数での表現やポインタ、メモリのアドレスなどについて学ぶ。 malloc
でのメモリー領域の確保や free
でのメモリの解放の仕組み、配列で管理するデータのメモリ上での配置などもみていく。
自分は過去RustやGolangで少しポインタ周りは扱ったことはあるが、C言語で意識してメモリの確保・解放などを行った経験はなかったので良い経験になった。
図を使った解説も豊富で、さらにコードでもメモリの中身を確認したりということも行うので、メモリについての理解も基本的な部分はしっかり深まる。
メモリとかの挙動は気になったので、確保した領域にデータを突っ込んでいき、その領域にポインタのアドレスでアクセスして値を確認したり、アドレスに+1してその隣の領域に格納されている値を確認したりとかしてた。
汚ったないですが以下のような感じ。
#include <stdio.h>
int main(void){
char *s = "hello!";
char *t = "world!";
printf("%c\n", s[0]);
printf("%c\n", s[1]);
printf("%c\n", s[2]);
printf("%c\n", s[3]);
printf("%c\n", s[4]);
printf("%c\n", s[5]);
printf("%c\n", s[6]);
printf("%c\n", s[7]);
printf("%c\n", s[8]);
printf("%c\n", s[9]);
printf("%c\n", s[10]);
printf("%c\n", s[11]);
printf("%c\n", s[12]);
printf("%c\n", s[13]);
printf("%c\n", s[14]);
printf("%c\n", s[15]);
printf("%c\n", s[30]);
printf("%c\n", s[31]);
printf("%c\n", s[32]);
printf("%c\n", s[33]);
}
// 出力結果
h
e
l
l
o
!
w
o
r
l
d
!
%
c
Week5ではデータ構造について。
ここまではメモリ上に連続した形でデータを保持する配列を用いたデータ管理を行っていたが、 ここからは連結リスト(linked list)やツリー(trees)、ハッシュテーブル(hash table)などを使ったデータ管理を学ぶ。
ここでも特に今日供されたのは CSにおいてはメモリの使用量を最小にするか、計算量を最小にするかはトレードオフの関係にある
ということ。
例えば非常に高速な検索が可能なデータ構造として tries
という巨大なデータセットであっても一定時間で検索が可能なツリーが紹介されるが、これは膨大なメモリーを必要とするためあまり採用されないとのこと。
それぞれのデータ構造のPros/Consを理解し、適切に選択することが重要。
Week6以降はPythonを用いたプログラミングやJavaScript, HTML, CSSの基礎とそれを使ったプロジェクトづくりの話がメインなので割愛。
- まとめ
普段からプログラミングをやっている人であれば、Week0~Week5までの内容が主な学習で、それ以降はざっとみていく程度でも良い気がする。
そもそも仕事でやっている人であれば、Week5までの内容も当たり前に知っているべきという話はそもそも論なのでナシで。
コンピュータサイエンスとは何かにはじまり、C言語を使ってのメモリの解説やアルゴリズム、データ構造の解説など個人的には非常にわかりやすく理解が進んだ。
プログラミング未経験者も前提にした講義で、受講生からの質問も簡単な部分からどんどん上がってくるしかつそれも丁寧に答えていくので、しっかりと理解が定着していく感じがする。
実際にC言語を使って自分でもメモリに格納されている値を確認したり、ソートの実装やデータ構造の実装をしっかりと解説をうけつつ行っていくのはよかった。
これまでは少しLeetCode齧った中でやったりRustの本読みながらやったことはあったが、それらをやったときよりも一段丁寧に取り組んだ感じ。
全体を通しては、まさに Software Development Fundamentals
としての内容で、ソフトウェア開発における基礎となる概念をまず浅く広く学ぶことができた。
『プログラミングの基礎』 - 著: 浅井健一
CS50の後、もう少しこの Software Development Fundamentals
のことを学びたいなと考えていた。
CS50が動画ベースのリソースであったので、次は書籍ベースで探していたところ、複数のところで本書がお勧めされていた。
Software Development Fundamentalas
は「ソフトウェア開発に必要な基本概念と技術を扱う」「アルゴリズムの設計と簡単な解析、プログラミングの基本概念とデータ構造、基本的なソフトウェア開発方法とツールを学ぶ」 ということがスコープになっているので、本書の「プログラムの作り方を学ぶ」「アルゴリズムとデータ構造に触れる」という部分が今回の知識エリアを満たしていると 思ったので本書を進めることにした。
ざっくりまとめると、「デザインレシピ」というプログラムを作るときのある種の方法論を用いて、OCamlという言語を使ってプログラムの書き方を学ぶ。
デザインレシピに沿ったプログラムの作成を進めていくこと、なかなか理解が難しい再帰の処理などもうまく実装していくことができる。
実装する際に、疑似コードを使ってある程度の骨子を作ってから実装に移るというアプローチを取っている方もいるかと思いますが、このデザインレシピはその考え方に近い感じ。
ただしそれを「デザインレシピ」というある種の体系化された方法論として定義しているので、より汎用的に、均一のレベルでのプログラミングができるようになるイメージ。
経験のあるエンジニアの方でも本書をお進める方を結構見かけたのですが、キャリア序盤というか、プログラミングを学び始めたときに本書を読むと実装について良い習慣を身につけられるのかなと思う。
またOCamlを使っており、再帰処理などの実装もイメージがよりしやすく、また関数型言語の特徴を学ぶこともできるので関数型言語に興味がある方にもお勧めできる。