題名 | ノイズ耐性のあるブースティング手法の実験的評価 |
著者 | *成相 光司, 藤田 慎二郎, 亀井 清華, 藤田 聡 (広島大学大学院工学研究科情報工学専攻分散システム学研究室) |
ページ | p. 200 |
キーワード | ブースティング, ノイズ耐性 |
アブストラクト | 機械学習の手法のひとつにブースティングがある。これは、分類精度のあまりよくない複数の分類器を用い、それぞれの精度に応じた多数決をとることで、精度のよい分類器を作成するアルゴリズムである。このブースティングのひとつにAdaBoostがある。AdaBoostの問題点に、訓練事例中にノイズが混じると分類精度が低下するということがある。本研究では、訓練事例中にノイズがある場合でも精度を落とさないブースティングについて、苦手なデータセットはどのようなものかといった点を明らかにする研究を行った。 |
題名 | 一般化FortyThievesの計算複雑さ |
著者 | *松井 勇太 (広島大学大学院情報工学専攻計算機基礎学研究室), 岩本 宙造 (広島大学大学院工学研究科情報工学専攻計算機基礎学研究室) |
ページ | pp. 201 - 202 |
キーワード | 計算複雑さ, パズル, NP完全 |
アブストラクト | FortyThievesとは52枚のカードデッキ二組を用いて行うカードゲームです.ゲームの目的は場と呼ばれる8つの場所に4*10のレイアウトに並べられたカードとストックのカードをすべて動かすことです.それぞれの場には同じスートでAからKまで並べなければいけません.4*10に並べられたレイアウトはそれぞれ4枚ごとに重なっており,一番上のカードだけ動かすことができます.このカードが場に出ているカードより1ランク高ければ場に出すことができます.ほかの4枚重なっている一番上のカードがこのカードより1ランク高ければそこにも移動できます.私たちはこのゲームを一般化しNP完全であることを証明しました. |
題名 | マンハッタンタワーの警備員配置問題の計算複雑さ |
著者 | *北垣 佑典, 岩本 宙造 (広島大学大学院工学研究科情報工学専攻計算機基礎学研究室) |
ページ | pp. 203 - 204 |
キーワード | NP困難, マンハッタンタワー, 警備員配置問題 |
アブストラクト | 計算機科学における幾何学分野の問題として,警備員配置問題がある.これは空間に警備員を配置し,与えられた領域を警備する警備員集合を求める問題である.本研究では,すべての面がx-y平面または,y-z平面または,x-z平面に平行なテラインであるマンハッタンタワーの警備員配置問題を考える.マンハッタンタワーの警備問題にはいくつか種類がある.セル警備員はマンハッタンタワーの面が正方形のセルで分割されるとき,セルに配置され,1つのセル上を自由に動くことができる.面警備員は面に配置され,面上を自由に動くことができる.マンハッタンタワーにおいてセル警備員と面警備員の警備員配置問題がNP困難であることを示す. |
題名 | 2状態2次元保存的セルオートマトンの数の移動 |
著者 | *竹村 陽平, 今井 克暢 (広島大学大学院工学研究科情報工学専攻計算機基礎学研究室) |
ページ | pp. 205 - 206 |
キーワード | セルオートマトン, 保存的セルオートマトン |
アブストラクト | セルオートマトンは格子状に敷き詰められた複数の状態を持ったセルの離散的な計算モデルである。各セルは周囲のセルの状態からなるルールによってステップごとに状態を変化させていく。状態を数字としたときに各セルの状態の合計が常に一定であるものを保存的セルオートマトンという。本研究では状態を0と1の2状態に絞り、2状態2次元で保存的な場合、セルオートマトンがの状態の数がどのような移動をするのかを研究する。 |
題名 | 可逆論理素子による可逆セルオートマトンの構成と遅延時間の短縮 |
著者 | *南野 遼太郎, 今井 克暢 (広島大学大学院工学研究科情報工学専攻計算機基礎学研究室) |
ページ | pp. 207 - 208 |
キーワード | 可逆論理素子, セルオートマトン, ロータリー素子, 遅延時間, 可逆性 |
アブストラクト | 可逆性とは直前の時刻にとり得る状態を1つしかもたない、状態遷移関数が単射であるような性質のことである。一方、非可逆な計算を行うと熱の発生を伴うことは Landauerにより指摘されており、近年における素子の急速な微細化から考えると、この熱の発生を防ぐことが膨大なエネルギー消費を減らす重要な鍵となるといえる。過去の研究では可逆的な計算を行う素子である可逆論理素子を用いてセルオートマトンなどの計算機を構成できることがわかっているが、とても時間のかかるものとなっていた。そこで本研究では回路の配線による時間の短縮法、また構成法を変えることによる時間の短縮法を示す。 |