OSの本、コンパイラの本あるある

どの書籍もタイトルがほとんど同じ例）「コンパイラ」、「コンパイラの仕組み」、「コンパイラの理論」表紙もシンプル昔の本ばかりだからしょうがないけど、わかりにくいわ

2019-02-21

わかりやすい書籍とは

OSについての書籍をいくつか読んでいて感じたこと❌わかりにくい説明の仕方これにはこういう機能があります。この機能はこういう仕組みです。⭕わかりやすい説明の仕方これはこういう目的のために存在している。この目的を果たすためにこういう機能が存在…

2019-02-20

研究がーーーーーー

研究がーーーーーめんどうだよーーーーー外部に委託しなきゃいけない部分があるから、とってもめんどうだよーーー自分で完結できるテーマにしとけばよかったーーーーーー書類はめんどいし、うまくいかなかったとしてもたぶん再実験できない結果がでなかっ…

2019-02-20

NPに対する理解

間違っていると思うけど、整理のためにとりあえずまとめる。追記クラスNPの定義は非決定性チューリングマシンで多項式時間で解けること非決定性チューリングマシンとは、いろいろな分岐をすべて同時並行的に調べ尽くしてしまうようなもの（まだ存在しない…

2019-02-20

今後のアルゴリズムの勉強について

現状、全探索はかけるようになった。次の目標は・具体的にどの程度の計算量から計算できなくなるかを判断できるように（現在、オーダーが累乗になるとまずいぐらいしかわかんない順列も階乗だからやばそうだけど、何桁からまずいのかわかってないレベル）…

2019-02-20

魔法陣

ruby プログラミング基礎

魔法陣を解く順列をすべて作ってから、魔法陣を満たすかチェックしてる。対称解、枝切りなどは何も行っていない。単純な全探索。rejectって書いた覚えないなって思ったらselect notのことか。フォーマッター使うと勝手に変換されるのか def magicSquare …

2019-02-20

O(2^n)を全探索

ruby プログラミング基礎

各要素を選ぶか、選ばないかの問題を全探索で解く O(2^n)かかるが、とりあえずここまでをぱっと作れることが大切引数にiを使って、i番目の要素を選ぶことを表現するこの書き方よく見るから覚えよう（個人的にはnを引数で渡して、マイナスしていきたいけど…

2019-02-20

ナイト巡回問題

プログラミング基礎 ruby

3×4の盤面でのナイト巡回問題お気楽 OCaml プログラミング入門次のノードがわかる問題の全探索はぱっとできるようになった気がする # 隣接リストバージョン $adjList = [ [5, 7], [6, 8], [3, 7], [2, 8, 10], [9, 11], [0, 6, 10], [1, 5, 11], [0, 2], […

2019-02-19

動的計画法を学ぶ

プログラミング基礎

動的計画法とは再帰で表現したものを下から計算することで計算の重複をなくすことが目的。再帰で解けるけど、計算量がやばいから動的計画法にしようっていう発想だから、僕が問題を解く上では動的計画法を意識せず、普段どおり再帰で解く。計算量が指数…

2019-02-19

動的計画法について

プログラミング基礎

再帰で解けるときは再帰でいい。下から積み上げていく解法のときに動的計画法がぱっと使えるようになりたい。

2019-02-19

最長増加部分列（LIS）

ruby プログラミング基礎

螺旋本読んでもLISがわかんなかった。以下のページがとてもわかり易かった。最長増加部分列・最長共通部分列 [いかたこのたこつぼ]誤解してたこと・Lは昇順に並んでいるから、これが最長増加部分列になると思ってた。・そうじゃなく、異なる長さの増加部…

2019-02-18

メモ化と動的計画法

ruby プログラミング基礎

# 素直にフィボナッチ def fib_normal(n) return 1 if n == 0 || n == 1 fib_normal(n - 1) + fib_normal(n - 2) end # メモ化 # 再帰の結果を配列に保存 # あくまで再利用がメイン $memo = [] def fib_memo(n) return $memo[n] = 1 if n == 0 || n == 1 ret…

2019-02-16

ヒープソート

ruby プログラミング基礎

def build_heap(arr) (arr.length / 2 - 1).downto(0) do |i| sift_down(arr, i) end arr end def heap_sort(arr) build_heap(arr) result =[] (arr.length - 1).downto(0) do |i| arr[0], arr[i] = arr[i], arr[0] result.push(arr.pop) sift_down(arr, 0) …

2019-02-16

ヒープの操作

ruby プログラミング基礎

配列で表現された2分ヒープに対しての操作完全2分木は配列で表現できる def deleteMin_heap(arr) arr[0] = arr.pop # 最後尾をrootへ sift_down(arr, 0) end # i番目の要素を適切な位置まで下げていく def sift_down(arr, i) leftIdx = 2 * i + 1 rightIdx …

2019-02-15

アルゴリズムのお勉強

アルゴリズムとデータ構造 (未来へつなぐデジタルシリーズ 10)作者: 原隆浩,水田智史,大川剛直,西尾章治郎出版社/メーカー: 共立出版発売日: 2012/06/07メディア: 単行本この商品を含むブログを見るとても良い本。擬似コードが多く、図も多いため読みやす…

2019-02-15

ハッシュのオープンアドレス法

プログラミング基礎

ハッシュのオープンアドレス法では格納場所に衝突が生じた際、再ハッシュを行う。そのやり方 hi(d) = ( h(d)+i ) mod B (i=1,2,...) 衝突したら次をチェックを繰り返す。iを足すだけだと配列の一番うしろを超えてしまう。 modすることで円のような感じにな…

2019-02-14

素数を求める

ruby プログラミング基礎

## エラトステネスのふるいを用いて素数を求める def getPrime(num) return [2] if num == 2 return [2, 3] if num == 3 rootPrime = getPrime(Math.sqrt(num).floor) eratosu(rootPrime, num) end ## エラトステネスのふるい ## rootPrime:numの平方根より…

2019-02-11

挿入ソート、マージソート

# ソートされた配列arrにnumを入れ、ソートされた配列を返す def insert(arr, num) return [num] if arr.empty? if arr[0] < num [arr[0], *insert(arr[1..-1], num)] else [num, *arr] end end def insertSort(arr) return arr if arr.empty? insert(insert…

2019-02-10

adobeで問題

adobeのcreative cloud入れたら "Failed to start CoreSync - Could not create ~/Library/Application Support/Adobe/CoreSync" って出た。この状態だとadobe xdが起動できない。アプリがdockで跳ねたあと落ちる。解決策は以下のページ dslr-astrophotogr…

2019-02-10