プログラミング Tips

ITエンジニアの雑記ブログ。
IT関連ニュースの考察や、プログラミングに関するTipsの備忘録として…
育児や日常の雑記帳としても、記事を投稿していきます。

プログラミングと日常生活に関する情報を発信しています。

2017年11月

2018/10/5更新:CES2019関連情報

更新:CES 関連情報

これまでに、CESに関連する記事を色々投稿してきた。読んでいただいた方々からの感謝・励ましの声もいただけたり、PVに表れたりしているので感謝感謝です!!

ここで、これまでに投稿したCES関連記事を集約してみる。情報集約によって、有効かつ簡単な情報ができ、より便利に活用でてもらえたら幸いである。

まとめ情報に関して、要望や質問があったらぜひ一報してほしい。



スタートアップ企業の出展数は800社超え!

CESのスタートアップ企業は「Eureka Park」に出展している。
今回CES2018における出店数は、800社を超えて過去最高を記録する模様。

CES is the global stage for startups. Investors come to Eureka Park to find their next unicorn. Global media come to look for their next story. Corporations come to look for partnerships and acquisitions. With more than 800 startups from every corner of the globe, you need to be here, too.

日本語訳:
CESは、スタートアップのグローバルなステージである。そして、投資家は"Eureka Park"に来て次のユニコーンを探す。グローバルメディアは次の物語を探すようになる。企業はパートナーシップと買収を探す。世界中の800以上のスタートアップ企業とともに、あなたもここにいなければなりません。

"Eureka Park"はどこにある?

肝心のEureka Parkの場所だが、CESオフィシャルマップによると、
「Sands EXPO Level1」にあると記載されているが、その場所がわかりにくい…

そもそも、「Sands EXPO」ってどこ?「Level1」の意味がわからない…
と思ったので、色々調べた結果を備忘のために残しておく。

Sands EXPO :"Tech EAST" のベネチアンホテル
Level1 :1階フロア

上記の場所にいけば、スタートアップ企業に出会える!!
が…

"Eureka Park"にどんな企業が出てるの!?

が、またわかりにくい…
一覧で入手したかったのだが、そのリストの入手方法がわからなかった…

マップ形式であれば、出展スタートアップ企業情報があったので、
それを代わりに載せておく。

Eureka Park出展企業情報

このマップを見るとわかるが、ベネチアンホテルのGホール全てが"Eureka Park"エリアになっている。つまり、このホール内全てがスタートアップ企業である。

まだ増減の可能性はあるが、現状概算で数えても800社の出展は間違いなさそう。


手元にある過去のマップと比較すると、昨年もこのホールが"Eureka Park"会場となっていたが…
ホール全体ではなく、一部にスタートアップ企業以外の出展も混在していた。

それが今回からはホールG内が、全てEureka Parkされている。

この点からも、過去最多のスタートアップ企業出店数というのは裏付けられていると判断できる。


展示会まで2ヶ月程度。
気になったスタートアップ企業を今後紹介していきたいと思う。

最短経路を求める方法を勉強してみた!

出発点から目的地までの最短経路を求めるアルゴリズムを勉強してみた!

ダイクストラほうは、出発点ごろから目的地までの最短経路を求めるアルゴリズムとして有名である。


最短隣接地点を繰り返し求めていく

ダイクストラ方のアイデアは、出発点に隣接する地点までの経路を確定していき、最終的に目的にたどり着く手法である。

確定した地点を太い線で囲み、確定した経路を実践で示すことにする。

出発点である東京は確定しているため、太い線で囲んでおく。出発点であるため確定距離は0キロメートルとする。
東京に隣接しているのは高崎、長野、名古屋である。東京からの距離は、高崎510キロ、長野230キロ、名古屋350キロ。よって最短距離は高崎までの110キロで確定する。なぜなら他の地点を経由して高崎に行くと、長野または名古屋を経由することになるため、高崎に直接行く方法より長くなるからである。

このように現場確定している経路に隣接する地点が複数ある場合、その中にある最短の時点までの経路が確定する。これがダイクストラ方のその中にある最短の時点までの経路が確定する。これがダイクストラ方のアイディアである。

パリティビットとハミング符号について勉強してみた!!

データのエラーチェックで使用される「パリティビット」と「ハミング符号」について、今までよく知らずに使ってきたので、ここでまとめて勉強してみようと思った。

パリティビットはエラーを検出できるがエラーの訂正はできない。 一方、ハミング符号は エラーの検出と訂正ができるという差がある。

これらはどのような仕組みで実現されているのかいくつかのバリエーションが存在するがその一部を備忘録としてここに残す。


パリティビットの仕組み

パリティビットもハミング符号も、データ本体にエラーチェック情報を付加して表現する。 今後はデータ本体のことを「情報ビット」、エラー情報のことを「冗長ビット」とする。

はじめにパリティビットの仕組みを解説。

パリティビットは、情報ビットに1桁の冗長ビットを付加して、データ全体の中にある「1」の数を偶数もしくは奇数に揃えるものである 。それぞれを「偶数パリティ」「奇数パリティ」と呼ぶ。
例えば7桁の

0101010

という情報ビットの先頭に、 偶数パリティで1桁を付加することとする。情報ビットの中には1が3個(奇数) ある。 よって1の個数を偶数にするために先頭に付加する冗長ビットの値は1である。この結果、データ全体が8桁の

10101010

となり、その中にある1の数は4個(偶数)になる。

偶数パリティを使ってデータ通信を行う場合を考える。
送信者側のプログラムでは、7桁の情報ビットの中にある1の数が偶数か奇数かによって冗長ビットの値を0か1に決定する。
受信者側のプログラムでは、冗長ビットと情報ビットを合わせた8桁のデータの中にある1の数が、偶数なら正常だと判定し、奇数ならエラーだと判定する。

データの中にある1の数が偶数か奇数かはXOR(排他的論理和演算)で簡単に判定できる。データを構成するすべての桁でXOR 演算を行った結果が0なら、1は偶数個あったことになる。結果が1なら、1は奇数個あったことになる。 なぜなら、1が偶数の場合1同志をペアにしてXOR演算を行うことができ、その結果が0になるからである(1XOR1=0)。

残った0同士でXOR演算を行った最終的な結果も0になる。それに対して、1が奇数個の場合はペアになれない1が一つ残る。XOR演算をすることになるので、最終的な結果は1になる。

パリティビットは全ての桁をXOR演算する仕組みなので、エラーを検出できてもどの桁がエラーなのかを特定できない。 よってエラー訂正もできない。 さらに、偶数個の桁にエラーがあった場合、それをエラーではなく正常と判断してしまう。 パリティビットは冗長ビットが少なくて済むが、エラーの検出に関しては不十分である。

次に説明するハミング符号は、冗長ビットが多い分だけエラー検出に優れる。

ハミング符号の仕組み

ここでは、情報ビットが4ビット、冗長ビットが3ビットのハミング符号を説明する。情報ビットを構成する各桁を X1, X2, X3, X4で表し、冗長ビットを構成する各桁を P1, P2, P3で表す。また情報ビットの後に冗長ビットを、X1,X2,X3,X4,P1,P2,P3の順に並べる。

冗長ビットP1, P2, P3の値は、以下のように情報ビットから3桁を選んでXOR演算して求める。

P1 = X1 XOR X3 XOR X4
P2 = X1 XOR X2 XOR X4
P3 = X1 XOR X2 XOR X3

例えば情報ビットが0101なら、冗長ビットは101になるので、全体は0101101となる。ハミング符号でエラーチェックを行うときは、以下の式1から式3を使う。

X1 XOR X3 XOR X4 XOR P1 = 0 //式1
X1 XOR X2 XOR X4 XOR P2 = 0 //式2
X1 XOR X2 XOR X3 XOR P3 = 0 //式3

これらは先ほど示したP1,P2,P3を求める式を、取り扱いやすいように変形したものである。三つの式の演算結果が全て0なら、正常と判定できる。三つの式の中に演算結果が1になるものが一つ以上あれば、エラーだと判定できる。この時どの式が1になったかで、情報ビットの何桁目がエラーなのかを特定できる。エラーとは、データの反転のため、何桁目がエラーなのか特定できればエラー訂正も可能となる。

エラーチェックの式で注目すべきは、4桁ある情報ビットから3桁だけを取り出していることである。これが、何桁目がエラーなのかを特定できる仕組みになっている。すべての式に含まれている X1がエラーなら全ての式の演算結果が1になる。X2がエラーならX2を含まない式1の演算結果が0になり、X2を含む式2と3の演算結果が1になる。エラーの桁と式1〜3の演算結果の対応をまとめる。なお、これ以外のパターンで式1〜3のいずれかの演算結果が0でない場合は、複数桁がエラーになっている。この場合は桁を特定できない。

RSA暗号(秘密鍵と公開鍵)の仕組みを勉強してみた!

暗号化と複合化で異なる鍵を使う「公開鍵暗号方式」は、SSL通信などで用いられる重要かつ有名な技術である。

この公開鍵暗号方式で有名なものに「RSA暗号」があり、これは内緒で選んだ2つの素数から公開鍵と秘密鍵を作り、2つの素数の積を公開する。従って、もしも2つの素数の積を素因数分解できれば、暗号を解読が可能。

ただし大きな素数の積の場合、最新のコンピューターを用いても素因数分解は実用的な時間では終わらない。
素因数分解を効率的に行うアルゴリズムがまだ見つかっていないためである。


素因数分解の関数を作る

引数に指定された整数nを素因数分解し、その結果を表示するprimeFactorization関数を作成する。

この関数は、引数にnに100を指定すると、

100 = 2 * 2 * 5 * 5

と表示する。素因数分解のアルゴリズムには、高度な数学を使った技法も考案されているが、ここは単純な技法に工夫を加える手法とする。

下記の例は、まだ工夫を加える前のprimeFactorization関数とテスト用main関数。

main関数では、キーボードから1以上の整数入力を受け、それを引数nとしてprimeFactorization関数を呼び出す。

#include <stdio.h>

void primeFactorization(unsigned int n) {
    unsigned int, a, counter;

    printf("%u = ", n);
    counter = 0;
    a = 2;
    while (n >= a * a) {
        if (n % a == 0) {
            printf("%u * ", a);
            n /= a;
        }
        else
        {
            a++;
        }
        counter++;
    }
    printf("%u\n", n);
    printf("counter = %u\n", counter);
}

int main(int argc, char* argv[]) {
    unsigned int n;

    printf("1以上の整数を入力してください:")
    scanf("%u", &n);
    primeFactorization(n);
    return 0;
}

primeFactorization関数では、aで繰り返しnを割って(割切れることを確認後)、nの値を更新。aの初期値は、最小の素数2である。nが、aで割切れる可能性があるのは、n ≧ aの2乗の時だけであるため、それをwhile分の繰り返し条件にする。

例えば、100を素因数分解する時、nの値が100, 50, 25, 5と更新された時点で、n ≧ 2の2乗という条件がfalseになり、繰り返しが終了となる。

while文を抜けてから、最後に残った5を付け足して表示する。

後で加える"工夫"の効果を確認できるように、while文の繰り返し回数をcounterという変数でカウントし、100および429467295(unsigned int型の最大値)を素因数分解結果は以下になる。

| 1以上の整数を入力してください:100
| 100 = 2 * 2 * 5 * 5
| counter = 6

| 1以上の整数を入力してください:429467295
| 429467295 = 3 * 5 * 17 * 257 * 65537
| counter = 259

繰り返し回数が減るように工夫する

100の素因数分解であれば実行時間は一瞬で、実行上問題ない。

しかし、数字が大きくなるほど時間がかかる。よって、primeFactorization関数の処理を工夫してみる。

気づいている方はいるかもしれないが、ポイントはwhile文の中で、aの値が2, 3, 4...と1ずつ増えていく部分である。例えば、100の場合、2と5で割切れるかを2回ずつチェックしただけでなく、3, 4でも割切れる事の確認をした。

素数である3はチェックする必要があるが、素数でない4をチェックすることは無駄になる。

するとaが素数であるか?否か?の確認を実施した上で、素数であることを確認してから割り算を実施すべきである。しかし、これでは「aの素数確認」に時間がかかってしまうことになる。

よって、ここでは処理に時間のかからない簡易的な素数確認方法を採ることとする。

具体的には、5以降の数では、2の倍数、3の倍数は素数でないとして繰り返しかた除外する。

aのインクリメント法を工夫して回数を減らせる。
5以上の整数を並べてみると、

| 5, 6, 7, 8, 9, 10...

となる。この並びは、「奇数⑸、偶数かつ3の倍数⑹、奇数⑺、偶数⑻、奇数かつ3の倍数⑼、偶数⑽」であり、11以降も同じパターンで繰り返される。よって、2の倍数と3の倍数をスキップするには5以降の1の増加分を+2, +4, +2, +4…とすればよい。

以下に改良したprimeFactorization関数を載せる。

まず、aを2および3の倍数でない数で割る。次にaの初期値を5として、2および3の倍数でない数で割る。
次にaに2と4を交互に加える

a += (inc ^ 6);

少し変わった書き方なので、解説すると以下の通りである。
"inc"は増分、"^"は排他的論理和(XOR)演算。2と4を2進数で表すと、"0010", "0100"になる。これらを交互に切り替えるには、"0110"つまり"6"とXOR演算を行えばよい。XOR演算は、1に対する桁を反転し、0に対する桁を変化させない。つまり、

0010 XOR 0110 = 0100
0100 XOR 0110 = 0010
0010 XOR 0110 = 0100

となり、1, 4の繰り返しを切り替えられる。

この方法を用いて、先ほどの4294967295を実行すると、繰り返し回数が259→130回に減っていることがわかる。
つまり120回は無駄な繰り返しだったことがわかる。

↑このページのトップヘ