読者です 読者をやめる 読者になる 読者になる

大学院生(情報科学)のブログ

モチベーション維持のためのブログです。

最大部分配列問題

要素の和を最大化するの連続する部分配列を発見する問題を最大部分配列問題と呼ぶ.例えば、配列と与えられたとき、最大部分配列はで和は43である.この問題を分割統治を用いて解く.分割は配列の中央点を基準にしとに分ける.この時、最大部分配列は、または、…

分割統治法とマージソート

以前紹介した挿入ソートは逐次添加法を用いている.部分配列をソートした後、1つの要素を正しい場所に挿入する事によってソートされたを得た. 多くの結うようなアルゴリズムの構造は再帰的であり、その多くの場合、分割統治法に基づいて設計されている.分割統…

ループ不変式

前回の記事で挿入ソートのソースコードを示したが、その正当性を今回は示す. def insert_sort(A): for j in range(1,len(A)): key = A[j] i = j - 1 while i >= 0 and A[i] > key: A[i+1] = A[i] i = i - 1 A[i+1] = key return A for文のは、トランプで言う…

・ソーティング問題の定式化と言葉の定義入力: 個の数の列 出力: である入力列の置換キー(key):ソートしたいと思っている数値・挿入ソート 少数の要素を効率よくソートするアルゴリズムex) トランプの手札をソート 左手を空にする 裏向きに置かれたカードを1…

M1になるまでにアルゴリズムとデータ構造を復習しようと思って学校の図書館から「アルゴリズムイントロダクション」を借りてきました。 アルゴリズムイントロダクション 第3版 総合版 (世界標準MIT教科書) 作者: T.コルメン,R.リベスト,C.シュタイン,C.ライ…

はじめまして

はじめまして。 卒業研究が無事終わり、学部生としての4年間は残すところ卒業式だけとなりました。 そこで、来春から大学院生になるので、研究、勉強のモチベーションを維持するための(自己満)ブログを開設することにしました。 とりあえず自己紹介 在籍…