ホーム » 2020

年別アーカイブ: 2020

2020年4月
 1234
567891011
12131415161718
19202122232425
2627282930  

最近の投稿(電子情報)

アーカイブ

カテゴリー

2020年度情報構造論ガイダンス

基本的なガイダンス

情報構造論のシラバスを、ここに示す。プログラムを作成する上で、どのような考え方で作れば処理速度が速いのかを議論する。基本的に、4回のテストのたびに、レポート課題を実施する。各テスト毎の評価は、テスト素点と、「テスト素点×60%+レポート評価×40%」の良い方とする。テストに自信のない人は、レポート課題をきちんと提出すること。ただし、今後の休講などの影響で評価方法は随時変更を行う。

プログラムを評価する3つのポイント

まずは以下を読む前に、質問。

  • あなたが良いプログラムを作るために何を考えて作りますか?
    • ここまでの段階で3つの要点を考えメモしておいてください。
    • ガイダンス最初のレポートに使います。

具体的な言葉で要点を考えると、いろいろなものがでてくるだろうが、端的なポイントにまとめると、次の3つに分類できるはずである。

  • プログラムの速度
  • プログラムのわかり易さ
  • メモリの使用量

プログラムを作る場合、この3要素がトレードオフの関係にある。プログラムの速度を優先すると、プログラムが分かり難くなったり、メモリを大量浪費するものだったりする。

メモリの使用量の影響

メモリを大量に使用すると、どういった影響がでるのか? OSの機能を知らないと、メモリ(主記憶)を使い果たしたら、プログラムが動かないと思うかもしれないけど、最近のOSは仮想メモリ機能があるため、主記憶がメモリが足りなければ待機状態のプロセスのメモリを補助記憶に保存することで、プログラムを動かすことはできる。(仮想記憶)

しかし、プロセスが切り替わる度に、補助記憶への読み書きが発生するため、処理性能は低下する。(スワッピング)

ソフトウェアとアルゴリズムとプログラム

用語として、ソフトウェア、アルゴリズム、プログラムという表現があるが、この違いは何か?

  • アルゴリズム – 計算手順の考え方。
  • プログラム – アルゴリズムを特定のプログラム言語によって記述したもの。
  • ソフトウェア – プログラムと、その処理に必要なデータ。(日本語を変換するプログラムは、日本語の辞書データが無いと動かない)

トレードオフ関係をプログラムで確認

例えば、配列の中から、目的データを探すプログラムの場合、最も簡単なプログラムは以下の方法であろう。

// ((case-1))
// 単純サーチ O(N)
#define SIZE 1024
int a[ SIZE ] ; // 配列
int size ;      // 実際のデータ数(Nとする)
int key ;       // 探すデータ
for( int i = 0 ; i < size ; i++ )
   if ( a[i] == key )
      break ;

しかし、もっと早く探したいのであれば、2分探索法を用いるだろう。でも、このプログラムは、case-1 のプログラムよりは分かり難い。(速度⇔わかり易さ)

// ((case-2))
// 2分探索法
int L=0 , R=size ; // プログラムは複雑になった 
while( L != R ) {
   int M = (L + R) / 2 ;
   if ( a[M] == key )
      break ;
   else if ( a[M] < key )
      L = M + 1 ;
   else
      R = M ;
}

でももっと速いプログラムとしたければ、大量のメモリを使えば一発でデータを探せる。(速度⇔メモリ使用量)

// ((case-3))
// 添字がデータ O(1)
// 探すデータが電話番号 272925 のような 6 桁ならば
int a[ 1000000 ] ;
a[ 272925 ] = 272925 ;
// 処理速度はクソ速いけど、メモリは大量消費

良いプログラムを作るとは

プログラムを作る時には、メモリが大量に使えるのなら、速いものを使えばいい。だけど実際には、そのシステムには限られた予算があるだろう。

実際には、限られる予算から、メモリやCPUが決まり、その会社の人員やら経験やらで、プログラム開発に使える時間がきまる。プログラムをデザインするとは、限られた条件の中で、適切な速度のコンピュータ、適切な量のメモリでコンピュータを用意し、限られた納期の中でシステムを完成させることである。

入学式のネット配信も中止

入学式のネット配信の中止

新型コロナ対策で、入学式も大人数を集めての実施もできず、クラス毎に教室に別れ、保護者の方もクラス毎に分かれて実施の予定でした。来ていただいた保護者の方にも少しでも入学式を楽しんでもらおうと、校長の訓示、学生の呼名を各部屋間をネット中継すべく、有志の先生に協力してもらい準備してました。

しかし、福井県も患者数も増え、週末の外出自粛、公立校も再開延期で、本校も入学式・ホームルームなども延期となりました。

ネットの準備はひとまず無駄になったけど、TeamsやStreamの使い方の勉強になりました。
{CAPTION}

ネット配信の案

入学式のネット配信は、新入学生の撮影などの問題もあることから、各教室、保護者控室に限定した配信で、以下のような予定でした。

しかし、入学式を短時間で終わらせたい事情も考慮しました。

最終的には、配信は以下のような構成となりました。

寮の桜

{CAPTION}

制御構文の理解

コロナ対策で、4年向けの情報構造論も始められないので、自習用資料。

ただし作りかけのファイルおいただけ。

制御構文の理解

基本として、C言語の制御構文の意味をフローチャートで表すと以下のようになる。

条件分岐if

繰り返しwhile, for, do-while

繰り返し命令の中では、break文でループを抜ける、continue文で次の繰り返し先頭に飛ぶ。フローチャートで表すと、上記の図中の赤、青の部分。

条件分岐switch

条件分岐のswitch文は、以下のようなフローチャートで示すことができる。
ただしcase の後には定数式しか書けない。 一般的には、分岐処理のAAA;BBB;CCC;の後ろには、break を書くのが一般的。繰り返し処理の中にswitch文があった場合、break命令では、switch文を抜けるだけで、ループを抜け出す訳ではない。

もし、breakを書き忘れると、以下のようなフローチャートになるので要注意。

このフローチャートを見てわかるように、breakが無いと、X=Bの時、処理BBB,CCCが実行することになる。

文の定義

C言語では、とは(大雑把に言うと)以下の定義である。複文の所が要注意。

for()の後には1つの文が書ける。単純な計算式であれば、式;で1つの文なので、{,} は本来不要。forの中で複数の処理を書きたい時は、{ 文 文 … } のように複文で1つの文の塊をつくる。

((( C言語の文 )))

// 式 : 計算式が ; で終わっているもの
式 ;

// if文
if ( 式 ) 文
else      文   // else以下略あり

// while文   
while( 式 ) 文
// for文
for( 式 ; 式 ; 式 ) 文
// do-while文
do 文 while( 式 ) ;   // セミコロンまででdo-while文

// 複文
{ 文 文... }   // 複数の文を1つの文として扱う
// 空文
;             // for(;;); これも文法としては正しい

例題

上記の制御構文の意味を踏まえた上で、過去のテスト問題より具体例で説明。

以下のプログラムの動作順序を(A)〜(M)の記号で答えよ。
答えは20ステップ目までで良い。

前述の文の定義を踏まえ、前述の問題の中では、以下の様な命令の塊(ブロック)が存在する。

ここで、水色部分(c)の if 文の break は{,} は不要なのか?という質問をする人が多いけど、if(式) { 文 } と書いても、if(式) 文 でも、文の部分に複文を使うか使わないかの違いにすぎない。

これを踏まえて、フローチャートを書くと以下の通り。

よって、この問題の回答は、以下のようになる。

A(i=0)→ B(i==0)D(j=0) E(j==0)G→H→   F→
E(j==1)G→H→I(break)
J(j=0) K(j==0)M→L
K(j==1) C(i=1)
B(i==1)D(j=0) E(j==0)G→H→   F→
E(j==1)G→H→I(break)
J(j=0) K(j==0)M→L
K(j==1)M→L
K(j==2) C(i=2)
B(i==2)

レポート課題

rep-1-1

rep-1-2

rep-1-3

rep-1-4

変数のスコープの理解

払い下げPCへのddを使ったディスクイメージコピー

総合情報処理センターのパソコンの入れ替えにより、払い下げとなったパソコンのセットアップ中。

1台をWindows10などの環境を整えて、あとは、USBブートのUbuntuを使って、HDDを全コピー。

最初、SATA のケーブルを、コピー元=SATA0 と、コピー先=SATA1 につないでコピーをしたら、同一バスを使うからかな!?やたらと時間がかかり、1台あたり 290分かかった。

$ time sudo dd if=/dev/sda of=/dev/sdb
289min...

2度目からは、コピー元=SATA0で、コピー先=SATA1を、コピー先=SATA3に変更して、ついでにコピー単位を256kB に変更して行う。

$ time sudo dd if=/dev/sda of=/dev/sdb bs=256k
78min...

バッファーサイズが効果的だったのか、SATA3 にしたのが良かったのか…はよく判らないけど、コピー時間を1/3に短縮できた。

でも、残りあと10台以上セットアップは続く。卒業式が始まる前に、1ローテーション回してから、式に向かう。まだまだあるし、もう1つUbuntuのUSBを準備し、2台並行作業を開始。

サーヴェイとは(FD研修会)

発想法の指導に関するFD研修会

サーヴェイ

はじめに

  • 論理立てて思考する起点を見出すのがサーヴェイ
  • デザインの作ろうとする物事の仕組みや考えを論理立てて説明出来るための要
  • 自身が納得できて、説得するためではなく説明の基礎

アイデア・イメージメモ

  • 考えの写真・図・イラスト
  • コメント1(思いつき、気付き、疑問、不、好感、利点など)
  • コメント2(提案、発展、課題など)
  • その他

Surveyとは、

  • SurveyとResearchの違い
    • Research…研究・調査
      • 研究する、調査する
    • Survey …調査、探査、測量、実地踏査
      • 見渡す、概観する
    • field work …実地研究、野外調査、実地調査、現地調査、巡見
  • 探検・発見

ResearchとSurveyの相違

  • リサーチ
    • 準備して調べること
      • 縛りが強い、決め事がある
      • 客観的
      • 設定
      • 定数的
      • やや論理的
      • ロジカル、裏付け的
  • サーヴェイ
    • 特に準備なく体感すること
      • 縛りがゆるやか、決め事はない
      • 主観的
      • 想定
      • 定性的
      • 感覚的
      • エモーショナル、曖昧さがあっていい

Surveyでの留意点

  • サーヴェイは、情報・データを得る方法の1つ
  • 問題を発見する方法
  • ポイント
    • 先入観を持たずに概観(常識や固定観念をはずす)
      • 自分の経験や知識を一度仕舞い込む
      • 常識や規則、良識に囚われていないかと自分に問う
    • 自分の五感+αに素直(感じや思いを表出する)
      • 感じるがまま、思うがままを表現
      • 幼少時の感覚を思い起こす
        • 純真な子供に成り代わって素直に対象と接する
    • 気付き、思いつきをメモ
      • 記号化 – 話し言葉、書き言葉、絵、写真、図など「うつし」
        • 取捨選択をしない
        • あまり深く考えない
        • 結論や解を求めない
        • 評価しない
  • 気になることがない…という場合には
    • アイデアイメージを書けない理由
      • こんなことはできない、不可能だから言わない、提案しても採用されない…
    • 曼荼羅法→根拠理由を考えて再度行う
      • なぜ書けないを曼荼羅法で気づかせる
    • なぜ、どうしてと問わない。関わり、関係を考えない

Surveyからメモ作成での姿勢と方向

  • 対象の概観(観察)
  • 時間を区切る
    • (5) / 15 / (30) / 45 / 90 分
    • 5分でまとめる(連想法を5分で…)
    • 30分以上同じことをさせない
  • 自他の評価を考えない・行わない
  • 対象の良い点も悪い点も見つける
    • 曼荼羅法、
      • 3×3の表
      • 真ん中にテーマと気付き
      • その周り8コマにアイデア(上下左右にプラスマイナス)
    • プラスマイナスカード法、
    • Brain Writing法、
    • Brain Storming法(希望点列挙法,欠点列挙法)
  • 素直に問う
    • 気になることを「何だろう」「どうしてかな」と自問する
  • 話す・見せる
  • ▶︎サーヴェイによるデータ・資料作成のプロセスとなる

サーヴェイの位置付け・必要性・実施の意味

  • サーヴェイ
    • 問題の発見 … 問う「なぜ?」「どうして?」と疑問に思うこと
    • 問題の探索 … さぐる、さがす
    • 問題の把握 … 全貌と細部(ディテール、詳細) → 現状把握・確認
  • 「発想のネタ」、「創造のいとぐち」を見出すためのプロセスの最初の行為であり思考
  • サーヴェイと問題
    • 発見、把握、探索

サーヴェイの発散・収束の思考

  • イメージからアイデアに
    • 探索→発見→把握→探索…のスパイラルアップ
  • 感覚的から論理的に
  • 関係や関わりも探り考える(空間・場・時間・機会・遊・休・知・美・感・交・操・演)

発想を出す時のテクニック

  • Surveyする時の写真は、モノクロの方がいい
    • 余計な情報が先入観になってしまう
  • 写真にマーカーを入れる
    • マーク付けした所をもとに議論

 

ネットワークセキュリティのためのTips

ファイル操作演習 回答編

Linux の操作演習をやったけど、興味を持った人はそれなりに楽しんでくれたみたい。ひっかけのネタになっていた部分を抜粋して簡単に説明。

基本は、以下のようにディレクトリに入って、ファイルだったら表示…の繰り返し。

$ cd /home0/Challenge/1-CTF.d/Task1
$ ls -al
0ReadMe brain concussion persons
$ cat 0ReadMe
...
$ cd brain
$ ls
company  concussion  of-brains
$ cat *
...
$ cd ../concussion
$ ls
...

Task4では、特殊なファイル名が入れてあるので、注意が必要。

$ cd /home0/Challenge/1-CTF.d/Task4
$ cd dir1
$ cat 'file name.txt'   空白を含むファイル名は''で囲む
:
$ cat ./--file.txt      -で始まるファイル名はコマンドオプションと
                        勘違いされないように ./ をつける。

dir3 の中には、シンボリックリンク(Windowsでいうところのショートカット)があるので要注意。

$ cd ../dir3
$ ls -al
lrwxrwxrwx 1 t-saitoh t-saitoh    2 Dec 20 10:45 Task4 -> ..
-rw-rw-r-- 1 t-saitoh t-saitoh   39 Dec 20 10:47 ZFile4

# cd Task4 をすると、1つ上のディレクトリへのシンボリックリンクがあるので
# 無限の繰り返しになる。

Task5 には、unix の基礎的なセキュリティトラップを体感してもらう。

$ cd /home0/Challenge/1-CTF.d/Task5
$ ls 
0ReadMe  Bomb
$ cd Bomb
$ ls                   接続が切れてしまう。

実は、今回 Login すると、環境変数PATH の設定に不備が仕掛けてある。また Bomb のディレクトリ内には、ls , cat といった名前で、強制的に接続をするコマンドを置いてある。この仕掛けにより、Bomb ディレクトリで ls を実行すると、接続が切れてしまう。

対策1

Bomb ディレクトリに入らずにファイルを探る

$ cd /home0/Challenge/1-CTF.d/Task5
$ ls Bomb
0ReadMe  Bomb
$ cat Bomb/cat
$ cat Bomb/flag

対策2

実は、環境変数 PATH (利用者がよく使うコマンドが保存されているディレクトリ一覧)が “.:/usr/bin:/bin” となっている。先頭に . が入っているため、カレントディレクトリの中に ls といったコマンドがあると実行してしまう。

環境変数 PATH にカレントディレクトリ(.)が入っていると、悪意のあるプログラムを実行させたい人が、危険な実行プログラムを置き逃げしてあると、実行してしまう可能性が高い。このため、(.)無しにすべき。

$ export PATH=/usr/bin:/bin
$ cd /home0/Challenge/1-CTF.d/Task5/Bomb
$ ls
cat  flag  less  ls  lv  more  nkf
$ cat flag
FLAG{DoNotTouchBomb}

Linux演習用リンク

演習の中では、クイズ形式などの回答を聞いたり、講義後の質問などのために、以下の Twitter ハッシュタグを用いることとする。#2020nitfcei3os って書いたけど、学内WiFi SNS系全カットじゃん。

なお、教室で BYOD パソコンで同時接続を行うため、この授業中だけ増設の WiFi アクセスポイントを設置します。

  • SSID = fnct-class , password = fnct-class にて接続してください。

Windowsでsshが使えない場合

データベース2019-講義録