様式９ +-------------------------------------+----------------+----------------------+ | ｼｽﾃﾑ名(ｺｰﾄﾞ): ＡＬＧＯＰＡＫ | | システム報告書概要 | +-------------------------------------+ +----------------------+ | ﾓｼﾞｭｰﾙ名(ｺｰﾄﾞ): BITMULT (A605) | ﾗｲﾌﾞﾗﾘ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者･学生番号: 増沢善子 21SS1159 | 文書作成者･学生番号: 増沢善子21SS1159 | +-------------------------------------+---------------------------------------+ | 作成期間: 62/ 1/ ー / / | 文書作成期間: 62/ 2/ ー / / | +-------------------------------------+---------------------------------------+ | 親モジュール: ＡＬＧＯＳ | 子モジュール: POWER | +-------------------------------------+---------------------------------------+ | 講義名・課題名: 卒業研究 | 参考文献(著者名、書名、出版社、発行年)| +-------------------------------------+ | | 開発形態: 移植 | SARA BAASE,COMPUTER ALGORITHMS, | +-------------------------------------+ | | 形式: サブルーチン | ADDISON WESLEY,1978. | +-------------------------------------+---------------------------------------+ | 利用対象者: 一般 | 格納ﾒﾃﾞｨｱ形式: フロッピーディスク | +-------------------------------------+---------------------------------------+ | 目的（問題解説、機能解説−制限事項）| 格納ﾒﾃﾞｨｱ番号、ﾌｧｲﾙ名: | | +---------------------------------------+ | | 記述言語・走行ＯＳ: TURBO PASCAL | | ブール行列の積を求める +---------------------------------------+ | | 走行条件（ハードウェア、ソフトウェア）| | サブルーチン プログラム | ＰＣ−９８０１，ＭＳ−ＤＯＳ | | | | | | | +-------------------------------------+---------------------------------------+ | キーワード（適用分野、手法など） ： | 分類コード（ＣＲコードを使用） ： | | BIT MATRIX MULTIPRICATION | | +-------------------------------------+---------------------------------------+ | 呼び出し法: BITMULT (N,A,B,C) | | | +-----------------------------------------------------------------------------+ | 操作手順(ｺﾝﾌﾟﾘｰﾄﾌﾟﾛｸﾞﾗﾑ(ﾒｲﾝﾌﾟﾛｸﾞﾗﾑ)の場合:1.システム起動手順､2.データ入出力 | | 手順と形式､3.終了手順) | | (ｻﾌﾞﾙｰﾁﾝの場合:1.呼び出し形式-引き数の並べ方-､2.親ルーチン､3.子ルー | | チン､4.その他) | | | | | | １． Ｎ （入力）： 行列Ａ,Ｂの次数 （整数型，Ｎ≦15） | | | | Ａij （入力）： 行列Ａのi,j成分 （Ａij=0 or 1，i,j=1,･･･,N） | | | | Ｂij （入力）： 行列Ｂのi,j成分 (Ｂij=0 or 1，i,j=1,･･･,N) | | | | Ｃij （出力）： ＡとＢのブール積Ｃのi,j成分 (Ｃij=0 or 1， | | | | i,i,j=1,･･･,N) | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-----------------------------------------------------------------------------+ 注. システム１つにつき１枚作成 必要な場合モジュール１つにつき１枚作成(ｲﾝﾀｰﾌｪｰｽ仕様書-様式１-に追加) 様式７ +-------------------------------------+----------------+----------------------+ | システム名: ＡＬＧＯＰＡＫ | | 問題解説 | +-------------------------------------+ +----------------------+ | モジュール名: BITMULT (A605) | ﾗｲﾌﾞﾗﾘ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者: 森木 京子 10SS1249 | 文書作成者: 森木 京子 10SS1249 | +-------------------------------------+---------------------------------------+ | 作成期間: 58/ 7/ ー 58/ 8/ | 文書作成期間: 59/11/ ー 59/12/ | +-------------------------------------+---------------------------------------+ | ＋､０ １ ・､０ １ | | ブール行列の和と積が ｢ﾞ｢｢｢ ｢ﾞ｢｢｢ で | | ０､０ １ ０､０ ０ | | １､１ １ １､０ １ | | ` | | 定義されたとき、ｎ＊ｎのブール行列ＡとＢの積Ｃを求める問題である。 | | | | ｔ=｢logｎ]としてＡを行列Ａ1,Ａ2,･･･,Ａ｢n/t]つまりｎ*ｔの小行列に、Ｂを | | | | Ｂ1,Ｂ2,･･･,Ｂ｢n/t] ｔ*ｎの小行列にそれぞれ分割すると、求めるＡとＢの積 | | | | は、 ｢n/t] | | Ｃ＝ＡＢ＝ Σ ＡjＢj | | j=1 | | で求めることができる。 | | | | 12…t t+1…2t (j-1)t+1…jt …n _______________ | | / ｨ ｨ ｨ ｨ ､ /______Ｂ1______､ | | Ａ＝､Ａi1ｨ Ａi2 ｨ…ｨ Ａij ｨ… ､ Ｂ＝ ､_______:_______､ | | ､ ｨ ｨ ｨ ｨ ､ ､______Ｂj______､ | | ､ ｨ ｨ ｨ ｨ / ､ : / | | ここで ひとつひとつの積ＡjＢjはそれ自身がｎ*ｎ行列であることに注意する。 | | | | ＡjＢjを計算するために Ａjの各行ＡijについてＡijＢjを求める。ＡijＢjを | | | | 求めるには、Ａijが１をもつ列番号ｋごとにＢjの第ｋ行をみつけ こうしてＢj | | | | の中でみつけた行をｎ次BITベクトルとして全部加える。 | | | | 例えば | | /0 0 1､ /1 1 0 1 0 0 0 0､ | | ､1 0 1､ ､1 1 0 1 1 0 0 1､ | | ､1 1 1､ /0 1 0 1 1 0 0 1､ ､1 1 0 1 1 1 0 1､ | | Aj=､1 0 0､, Bj=､0 0 0 1 0 1 0 0､, Cj=AjBj=､0 1 0 1 1 0 0 1､ | | ､0 0 0､ ､1 1 0 1 0 0 0 0/ ､0 0 0 0 0 0 0 0､ | | ､1 1 0､ ､0 1 0 1 1 1 0 1､ | | ､0 0 0､ ､0 0 0 0 0 0 0 0､ | | ､0 1 1/ ､1 1 0 1 0 1 0 0/ | | となる。 | | | | この Ｃj （１≦ｊ≦｢n/t]） の結合されたものがＣである。 | | | | | | | | | | | | | | | | | | | | | | | | | | | +-----------------------------------------------------------------------------+ 様式６ +-------------------------------------+----------------+----------------------+ | システム名: ＡＬＧＯＰＡＫ | | アルゴリズム流れ図 | +-------------------------------------+ +----------------------+ | モジュール名: BITMULT (A605) | ﾗｲﾌﾞﾗﾘ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者: 森木 京子 10SS1249 | 文書作成者: 森木 京子 10SS1249 | +-------------------------------------+---------------------------------------+ | 作成期間: 58/ 7/ ー 58/ 8/ | 文書作成期間: 59/11/ ー 59/12/ | +-------------------------------------+---------------------------------------+ | | | ++-------++ +---------+ | | !! BITMU !! ! t:= ! | | !! LT !!---->! ｢logN] ! | | !! !! ^ ! ! | | ++-------++ ! +---------+ | | ! ! | | ! +---------+ | | ! ! UNIONS[ ! | | ! ! 0]:=0 ! | | ! ! ! | | ! +---------+ | | ! ! | | ! +--------++ +--------++ +---------+ +---------+ | | ! ! FOR !! ! FOR !! ! FOR i ! ! ! | | !-! j:=1 TO!!---->! k:=1 !!---->! := 1 TO !---->! 1 ! | | ! ｢N/t]!! ! TO t-1 !! ^ ! 2**k-1 ! ! ! | | +--------++ +--------++ ! +---------+ +---------+ | | ! ! | | ! +--------++ +---------+ | | ! ! FOR !! ! Ci:= Ci ! | | !-! I:=1 !!---->! vUNIONS ! | | ! TO N !! ! [Aij] ! | | +--------++ +---------+ | | | | | | | | | | | | | | | | +---------+ +-------------------------+ | | ! ! ! UNIONS[i+2**k] ! | | ! 1 !---->! :=UNIONS[i] v Bk ! | | ! ! ! ! | | +---------+ +-------------------------+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-----------------------------------------------------------------------------+ 様式９ +-------------------------------------+----------------+----------------------+ | ｼｽﾃﾑ名(ｺｰﾄﾞ): ＡＬＧＯＰＡＫ | | システム報告書概要 | +-------------------------------------+ +----------------------+ | ﾓｼﾞｭｰﾙ名(ｺｰﾄﾞ): CBITMULT (P605) | ﾗｲﾌﾞﾗﾘ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者･学生番号: 増沢善子 21SS1159 | 文書作成者･学生番号: 増沢善子21SS1159 | +-------------------------------------+---------------------------------------+ | 作成期間: 62/ 1/ ー / / | 文書作成期間: 62/ 2/ ー /　/ | +-------------------------------------+---------------------------------------+ | 親モジュール: ＡＬＧＯＰＡＫ | 子モジュール: BITMULT (A605) | +-------------------------------------+---------------------------------------+ | 講義名・課題名: 卒業研究 | 参考文献(著者名、書名、出版社、発行年)| +-------------------------------------+ | | 開発形態: 移植 | SARA BAASE,COMPUTER ALGORITHMS, | +-------------------------------------+ | | 形式: コンプリート | ADDISON WESLEY,1978. | +-------------------------------------+---------------------------------------+ | 利用対象者: 一般 | 格納ﾒﾃﾞｨｱ形式: フロッピーディスク | +-------------------------------------+---------------------------------------+ | 目的（問題解説、機能解説−制限事項）| 格納ﾒﾃﾞｨｱ番号、ﾌｧｲﾙ名: | | +---------------------------------------+ | | 記述言語・走行ＯＳ: TURBO PASCAL | | ブール行列の積を求める +---------------------------------------+ | | 走行条件（ハードウェア、ソフトウェア）| | テスト プログラム | ＰＣ−９８０１，ＭＳ−ＤＯＳ | | | | | | | +-------------------------------------+---------------------------------------+ | キーワード（適用分野、手法など） ： | 分類コード（ＣＲコードを使用） ： | | BIT MATRIX MULTIPRICATION | | +-------------------------------------+---------------------------------------+ | 呼び出し法: CBITMULT | | データ | +-----------------------------------------------------------------------------+ | 操作手順(ｺﾝﾌﾟﾘｰﾄﾌﾟﾛｸﾞﾗﾑ(ﾒｲﾝﾌﾟﾛｸﾞﾗﾑ)の場合:1.システム起動手順､2.データ入出力 | | 手順と形式､3.終了手順) | | (ｻﾌﾞﾙｰﾁﾝの場合:1.呼び出し形式-引き数の並べ方-､2.親ルーチン､3.子ルー | | チン､4.その他) | | １．＞ ＣＢＩＴＭＵＬＴ．ＳＲＣ 　　　　　 | | | | 　　　　　　　　　　　　　　　　　　　　　 　 | | | | 　　　　　　　　　 | | | | データ | | | | ２．1)入力データ | | | | Ｎ：行列Ａ，Ｂの次数 （整数型，Ｎ≦１５） | | | | Ａij：行列Ａのi,j成分 （Ａij=0 or 1，i,j=1,･･･,N） | | | | Ｂij：行列Ｂのi,j成分 （Ｂij=0 or 1，i,j=1,･･･,N） | | | | 2)出力データ | | | | Ａ,Ｂ：もとの行列 | | | | Ｃ：ＡとＢのブール積 | | | | | | | | | | | +-----------------------------------------------------------------------------+ 注. システム１つにつき１枚作成 必要な場合モジュール１つにつき１枚作成(ｲﾝﾀｰﾌｪｰｽ仕様書-様式１-に追加)