JIPDEC AITEC NEWS |
August 29, 1996 |
| Issue #5 |
皆さん、奮って御参加下さい！ (参加申し込みはお早めに！)
また、コンテストに参加するため、KLICを学ぼう／勉強し直そうという方のために、 10月4日(金)東京周辺で講習会(参加無料)を開きます。希望者は、
事務局: klic-contest@icot.or.jpまで、お申し込み下さい。
さて、以下に を示します。
第五世代プロジェクトで開発された並列論理型言語 KL1 で書かれたプログラ ムを以下の 3 部門について募集します。 (1) 逐次環境部門: (2) 並列環境部門: 両部門とも、与えられた課題(この後の「8. KLIC プログラミング・ コンテスト逐次環境部門、並列環境部門の課題 」を御覧下さい)の 仕様を満たすプログラムを作成して下さい。 逐次と並列の動作環境の違いで 2 部門に分かれています。 (3) 自由課題部門 特に課題は出しません。自由にプログラムを作成して下さい。 動作環境は逐次・並列のどちらを想定していただいても結構です。 応募プログラムの著作権は作成者本人に帰属します。但し入選作品につきましては、 その作成者に対して、(財) 日本情報処理開発協会 先端情報技術研究所 (AITEC) が今後の KLIC 普及活動等のための無償利用許諾をお願いしますので、予めご 了承下さい。
2. 優秀作品の表彰
審査委員会の定める選定規準に基づき、応募作品の中から各部門ごとに最優秀 賞、優秀賞、佳作、各 1 作品ずつを選定し、表彰状および副賞を贈呈致しま す。なお、入選した作品は Web 上にて公開させて頂く予定です。 ◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆ ◆ ◆ ◆ 副賞 ◆ ◆ 最優秀賞：５０万円 ◆ ◆ 優秀賞：３０万円 ◆ ◆ 佳作：１０万円 ◆ ◆ ◆ ◆ 参加賞：図書券 (5000円) ◆ ◆ ◆ ◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆ なお参加賞の対象となるのは以下の条件をみたす作品とします。 逐次環境部門および並列環境部門: 審査委員会の定めた制限時間以内に正しい解を出した作品。 自由課題部門: 審査委員会で別途定める基準に達した作品。 入選結果は 11 月 29 日までに参加者全員に電子メールにて通知します。また、 World Wide Web や雑誌等にても発表致します。12 月初旬 AITEC にて表 彰式を行う予定です。
3. コンテスト実施日程
平成８年 ９月３０日(月): 参加申し込み締切 １０月 ４日(金): KLIC 講習会 (東京周辺の予定) １０月３１日(木): 応募作品の提出締切 １１月２９日(金): 入選作品発表 １２月 上旬 : 表彰式 ◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆ ◆ ◆ ◆ 参加申し込みはお早めに！ ◆ ◆ ◆ ◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆ なお KLIC 講習会は無料です。希望者は参加申し込み時に事務局までお知らせ 下さい。
4. 応募の方法
コンテスト参加ご希望の方は、まず参加申し込みをして下さい。参加申し込み は電子メールでのみ受け付けております。宛先と Subject: を To: klic-contest@icot.or.jp Subject: ENTRY とし、メイル本文中に以下の項目を列記して下さい。 (1) 氏名 (グループでの参加申し込みの場合は、代表者名を先頭にして全員 の氏名を記入して下さい) (2) 所属（グループの場合は代表者） (3) 電子メールアドレス（グループの場合は代表者） (4) 電話番号（グループの場合は代表者） (5) 住所（グループの場合は代表者） (6) 応募を予定している部門 (複数可) (7) KLIC 講習会聴講希望の有無。希望の場合は 1 回目か 2 回目を明記。 （グループでお申し込みの場合は予定参加人数も書いて下さい） 参加申し込みされた方には応募方法等の詳細を送付します。この送付をもって 受け付け手続き完了通知にかえさせて頂きます。また Web からも参加申し込 みをすることができます。以下の URL にアクセスして下さい。 http://www.icot.or.jp/AITEC/FGCS/KLICON/main-J.html 応募資格については特に制限はありません。KL1 を初めて使用するような新規 ユーザの方々の積極的な応募も大歓迎です。コンテストに参加申し込みされた 方には、もれなく KLIC システムのチュートリアル・テキストを差し上げます。
5. 参加作品の作成環境
プログラムの作成および動作確認は参加者ご自身の計算機環境で行って下さい。 並列環境での最終的な動作確認に必要な環境が用意できない方は個別に事務局 (klic-contest@icot.or.jp) までご相談下さい。 KLIC の処理系は以下の URL から FTP できます: http://www.icot.or.jp/ARCHIVE/Museum/IFS/abst/085-J.html /ifs/symbolic-proc/unix/klic/klic.tgz
6. 審査方法
逐次、並列環境部門への応募作品は、与えられた課題が正しく解けるかどうか を AITEC 内の計算機環境にて動作確認致します。正しく動作した作品に対し て、そのアルゴリズム、処理速度、プログラム構造及び添付された説明書の判 りやすさ等に関して総合的に厳正なる審査を行い、入選作品を決定します。 また自由課題部門の作品については、動作確認に先立ちまず添付されたプログ ラム概要説明書による予備審査を行います。後は、逐次、並列環境部門同様に 動作確認、審査を行って入選作品を決定します。動作確認に際して、応募者御 自身にお手伝いして頂く場合もあります。 なお AITEC が動作確認のために使用を予定している計算機は以下の通りです: 逐次環境部門: UNIX ワークステーション 並列環境部門: 共有メモリ型並列 UNIX サーバ 自由課題部門: プログラムの性質により上記のいずれか AITEC での動作確認環境の詳細は参加申し込みされた方に別途お知らせします。
7. 問い合わせ先
本コンテストについての最新情報、KLIC 講習会の日程等は随時 Web 上 http://www.icot.or.jp/AITEC/FGCS/KLICON/main-J.html に掲示いたしますのでお見逃しなきようご注意下さい。 本コンテストへの質問、御意見、詳細情報の入手等は電子メールで事務局 klic-contest@icot.or.jp までお気軽にお問い合わせ下さい。
8. KLIC プログラミング・コンテスト逐次環境部門、並列環境部門の課題
まずコンテスト参加者の方々に, 課題の中心的な概念である「マルチ集合」と いうものに親しんで頂くために, 次に簡単な解説文を用意しました. 理解を 深めてから課題に取りかかるよう, 是非ご一読下さい.--------------------- 8.1. 「マルチ集合」とは --------------------- ある放送局がいくつかのプレゼント企画をしました. それぞれ多くの応募が あり, 中には一つのプレゼント企画に対して一人で複数の応募をしている応募 者もいます. この放送局は応募者に電話番号を記入させることで, 応募の整 理をしやすくしています. この電話番号で応募者は一意に決まるものとしま しょう. 一人が家族の名前を使って複数応募した場合や, 同じ家庭から数人 が応募した場合は, 電話番号で整理しているのですべて同一人物の複数応募と みなされてしまいますが, これは構わないことにします. この応募者のリス トはプレゼントの賞品の抽選に用いることはもちろんですが, どの家庭がどの 賞品に興味を持ったかを知ることで, 今後の賞品の選定やマーケティングなど にも役立てることができます. 例えば, プレゼント A に応募した人の電話番号をそれぞれ 7, 1, 2, 7, 7 とし ましょう. 例文のスペースを節約するために, ここでは電話番号を数字 1 桁 で表すことにします. 7 の電話番号を持つ人は 3 通も応募しています. 一 方, プレゼント B に応募した人の電話番号は 5, 7, 2, 7 だとしましょう. こ の状況は, {7,1,2,7,7} というマルチ集合 A と, {5,7,2,7} というマルチ集合 B で表現することができます. なおマルチ集合では, 要素の順序に意味がありま せん. ですから {7,1,2,7,7} も {2,1,7,7,7} も {7,2,7,1,7} なども全て同じ マルチ集合 A を表したものとみなされます. さて, このようなデータに以下の ようなマルチ集合の演算を施すと, そこから様々な情報を読み取ることができ ます. 以下に, いろいろな演算とその例を示します. Union: プレゼント A とプレゼント B は別企画だが共通で抽選を行なう賞品があるの で, 両プレゼントの応募全体を求めたい. 上の A と B の例を使って式で表 すと, {7,1,2,7,7}∪{5,7,2,7} ＝ {7,7,2,7,7,5,1,7,2} となります. Contraction: ある賞品の抽選に当たっては同一人の複数の応募をひとつと見なしたい. Contraction の操作を単項演算子↓で表すと次のようになります. ↓{7,1,2,7,7} ＝ {2,1,7} ↓{5,7,2,7} ＝ {5,7,2} Intersection: プレゼント A とプレゼント B の両方に応募しているのは誰か? 両方に複数応 募しているのなら, それはそれだけ熱心に両方を欲しているのだから, 何重 に応募しているのかも知りたい. {7,1,2,7,7}∩{5,7,2,7} ＝ {7,2,7} Difference: プレゼント B よりプレゼント A を誰がどれくらい強く欲しているのかを知り たい. 具体的には, 誰がプレゼント A にプレゼント B より何通多くの応募 を出したのか, ということになります. また, その逆はどうなっているのか も知りたい. Difference の操作を二項演算子 ＼ で表すと次のようになります. {7,1,2,7,7}＼{5,7,2,7} ＝ {7,1} {5,7,2,7}＼{7,1,2,7,7} ＝ {5} ではいよいよ, 課題の本体です.
--------- 8.2. 課題 --------- マルチ集合の演算に関して次の 7 つの述語を持つモジュール multi_set のプ ログラムを作成して下さい. 1. あるマルチ集合がリスト表現 L で与えられた時, それを適当な内部表現 M に 変換する述語: encode(L, M) 2. 逆に内部表現 M からリスト表現 L に戻す述語: decode(M, L) 3. 内部表現で与えられたマルチ集合 M0, M1 の和集合 M0 ∪ M1 = M を 計算する述語: union(M0, M1, M) 4. 同様に積集合 M0 ∩ M1 = M を計算する述語: intersection(M0, M1, M) 5. 差集合 M0 ＼ M1 = M を計算する述語: difference(M0, M1, M) 6. マルチ集合 M0 中の同一要素の重複を取り除いた集合 M を計算する述語: contraction(M0, M) 7. マルチ集合 M から適当な要素を 1 つ取り出し, その要素 E と残りの マルチ集合 S を返す述語: choose(M, E, S) (ただし M ＝ φの場合を考慮する必要はない) 応募作品の審査方法は次の通りです。
----------------------- 8.3. 応募作品の審査方法 ----------------------- AITEC で用意した審査用プログラムを使って, 1, 2 のエンコード/デコードの プログラムと, 3-7 の演算プログラムを適宜呼び出して走行テストを行い, 正 しい答えを計算するかどうかチェックします. 本課題で最初に審査用プログラムから与えられるマルチ集合のデータは, 重複 しているかも知れない整数を要素として持つリストとして表されています. 今回, このマルチ集合の要素は整数に限定します. 一方, 応募者のプログラ ムは, このリスト表現のデータを各自のフォーマットに変換して保持/演算を 行なうことが出来ます. そして最終的な答えは再びリスト表現に戻されます. この走行テストのイメージを掴んで頂くために, 8.4. に審査用プログラムの 例を示しますが, 実際の審査では, これとは異なる審査用プログラムを使用し ますので予めご了承下さい. 実際にデコーダ/エンコーダ, 演算プログラムに 与えられるマルチ集合のサイズはかなり大きくする予定です. また illegal な入力に対する処理はプログラムしなくても OK です. つまり, 1 に関して L はリスト表現であることを, 2-7 に関して M, M0, M1 は正しい内部表現の マルチ集合であることを仮定して構いません. 並行並列プログラミングの醍醐味は「非常にバラエティに富んだ現実の実行状 況を想定して, いかに美しくて効率の良いプログラムを書くことができるか」 と言っても過言ではありません. 応募者は, そのバラエティに富んだ実行状 況を各自でいろいろ想定して上記の 7 つの述語のプログラムに取り組んでみ て下さい. 並行並列プログラミングにおいては, 良いプログラムの基準は一 通りではありません. 審査プロセスには, 審査委員が応募作品のソースコー ドを読んで判断する作業も含まれています. 簡単でも良いですから, 応募者 は何故そのようなプログラミングをしたのかという考察を作品のプログラムに 添付して下さい.
-------------------------- 8.4. 審査用プログラム (例) -------------------------- 走行テストのイメージを掴んで頂くために, ここに審査用プログラムの例を 示しますが, 実際の審査では, これとは異なる審査用プログラムを使用しま すので予めご了承下さい. ---------------------------------------------------------------------------- :- module main. main :- go1(A1), go2(A2), klicio:klicio([stdout(NS)]), ( NS = normal(S) -> S = [putt(A1),nl,putt(A2),nl]). go1(L):- gen_3_ms(L0,L1,L2), % 乱数で 3 つのマルチ集合を生成する multi_set:encode(L0,M0), multi_set:encode(L1,M1), multi_set:encode(L2,M2), multi_set:intersection(M0,M1,M0i), % 以下 6 行は対称的に集合演算を行う multi_set:intersection(M1,M2,M1i), multi_set:intersection(M2,M0,M2i), multi_set:difference(M0i,M1i,Md0), multi_set:difference(M1i,M2i,Md1), multi_set:difference(M2i,M0i,Md2), multi_set:contraction(Md2,Mc), % ちょっとだけ不規則な演算 multi_set:union(Md0,Md1,M01), multi_set:union(M01,Mc,Mu), multi_set:decode(Mu,L). go2(L) :- gen_ms(13,11,S), % 要素の最大値 13, 要素数 11 のマルチ集合 multi_set:encode(S,T), pset(T,P), multi_set:decode(P,L). pset(S,P) :- % マルチ集合 S のべき集合 (power set) を求める multi_set:decode(S,D), ( D = [] -> multi_set:encode([],E), multi_set:encode([E],P) ; D \= [] -> multi_set:choose(S,C,S1), % 適当な一要素 C と残り S1 に分ける pset(S1,P1), multi_set:encode([C],Cs), % S1 のべき集合 P1 と C から map_union(P1,Cs,P2), % S のべき集合を作る multi_set:union(P1,P2,P) ). map_union(S,X,Y) :- % マルチ集合 S の各要素 (マルチ集合) multi_set:decode(S,D), % に X を加える (union する). ( D = [] -> multi_set:encode([],Y) ; D \= [] -> multi_set:choose(S,C,S1), multi_set:union(C,X,CX), % ここで各要素に X を union している multi_set:encode([CX],Z), multi_set:union(Z,S2,Y), % できあがった要素 Z を union して map_union(S1,X,S2) ). % 答えのマルチ集合 Y を作る gen_3_ms(L0,L1,L2) :- gen_ms_list(97,~(2 << 6 - 1),3,L), % 実際の審査では, これとは異なる % パラメータ値にする予定です. ( L = [M0,M1,M2] -> M0 = L0, M1 = L1, M2 = L2 ). % リストをバラして % 中身だけ取り出す /* * 要素の最大値 Max, 要素数 Card のマルチ集合を要素とするようなリストで, * 長さが ListLen のものを生成する */ gen_ms_list(Max,Card,ListLen,MSs) :- true | generic:new(random_numbers)+RDM+97, gen_ms_list_0(Max,Card,ListLen,MSs)-RDM. gen_ms_list_0(Max,Card,ListLen,MSs)-RDM :- ListLen =:= 0 | MSs = []. gen_ms_list_0(Max,Card,ListLen,MSs)-RDM :- ListLen >= 1 | gen_ms(Max,Card,MS)-RDM, MSs = [MS|N], gen_ms_list_0(Max,Card,~(ListLen-1),N)-RDM. /* 要素の最大値 Max, 要素数 Card のマルチ集合を 1 つ生成する */ gen_ms(Max,Card,MS) :- generic:new(random_numbers)+RDM+91, gen_ms(Max,Card,MS)-RDM. gen_ms(Max,Card,MS)-RDM :- Card =:= 0 | MS = []. gen_ms(Max,Card,MS)-RDM :- Card >= 1 | RDM <= Random, % demand driven で乱数を 1 個生成 MS = [~(Random mod Max)|N], gen_ms(Max,~(Card-1),N)-RDM.
9. 主催とKLICプログラミング・コンテスト実行委員会
主催: (財) 日本情報処理開発協会 先端情報技術研究所 (AITEC) (URL: http://www.icot.or.jp) KLICプログラミング・コンテスト実行委員会: 溝口文雄 東京理科大学理工学部経営工学科 教授 （委員長） 上田和紀 早稲田大学理工学部情報学科 助教授 田中二郎 筑波大学電子・情報工学系 助教授 近山 隆 東京大学工学系研究科電子工学専攻 助教授 平田圭二 日本電信電話 (株) 基礎研究所情報科学研究部 主任研究員 相場 亮 (財) 日本情報処理開発協会 先端情報技術研究所 主任研究員
「KLIC プログラミング・コンテスト」への質問、御意見、詳細情報の入手等は 電子メールで事務局 klic-contest@icot.or.jp までお気軽にお問い合わせ下さい。 皆さんの積極的参加をお待ちしております！ ☆＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊☆ ＊ ＊ ＊ ＡＩＴＥＣ ＮＥＷＳ Ｉｓｓｕｅ ＃５ ＊ ＊ 編集・配布 ＡＩＴＥＣ ＮＥＷＳ編集グループ ＊ ＊ 佐藤真紀子 高橋千恵 相場 亮 佐藤 博 内田俊一 ＊ ＊ ＊ ＊ 発行 １９９６年 ８月２９日 ＊ ＊ 財団法人 日本情報処理開発協会 ＊ ＊ 先端情報技術研究所 ＊ ＊ 東京都港区芝２丁目３番３号 芝東京海上ビル２Ｆ ＊ ＊ 電話：０３−３４５６−３１９１ ＦＡＸ：０３−３４５５−４８７７ ＊ ＊ ｅ−ｍａｉｌ：ａｉｔｅｃ−ｎｅｗｓ＠ｉｃｏｔ．ｏｒ．ｊｐ ＊ ＊ ＊ ☆＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊☆