【ネットワーク】お勉強1
【第3回】
- プロトコル ネットワークの約束事
- TCP/IP プロトコルの一種で最も有名
- 帯域幅 毛0ブルの性能規格を説明するときに使う言葉で本来の意味は使用できる周波数,最近はデータ転送速度を指す
- bps 一秒間に何ビット送れるかの単位
【第4回】
| 第7層 | Application Layer |
| 第6層 | Presentation Layer |
| 第5層 | Sessiion Layer |
| 第4層 | Transport Layer |
| 第3層 | Network Layer |
| 第2層 | Data-Link Layer |
| 第1層 | Physical Layer |
【第5回】
各レイヤでは機能が違い,独立している.
特定の機能を理解するためにはそのレイヤだけを考えればよい.
機能変更があってもそのレイヤ以外に影響が及ばない.
- Application Layer
ネットワークサービスを提供
ネットワークが可能かどうか判断する.
- Presentation Layer
データの形式を決定する.
- Session Layer
セッションを管理する.
会話(通信)の行き違いがないように会話の流れを管理する.
- Transport Layer
信頼性の高い通信サービスを保証する.
信頼性の高いとは相手に確実に届けるなど.
- Network Layer
離れた場所とのデータの伝送,運ぶルートの決定,宛先の決定などを行う.
- Datalink Layer
近くの機器とのデータの伝送制御を行う.
- Physical Layer
電気,機械的なルールを決める.
電気信号をやり取りする.
【環境設定】Ctrl + Spaceで日本語入力
「定義済みのキーマップからインポートで好きなものをインポート(任意)」と書いてあったがMS-IMEでないとうまくいかなかった.
また設定後新しいアプリケーションから設定が有効になるので注意.
d.hatena.ne.jp
【GIMP】画像サイズ変更
拡大縮小ツールを使う
画像をクリックして,したい画像のサイズを入力
synclogue-navi.com
【GIMP】トリミング
切り抜きツールを用いて画像から切り取りたい範囲を選択
Enterでトリミングされる
www.gimp2.net
【GIMP】背景透過
1.ファジー選択ツールで選びたい範囲を選択
2.Ctrl+Delで選択範囲を切り取る
synclogue-navi.com
【Python】ループ中の要素の削除
for element in LIST: if ---: LIST.remove(element) for i,enumerate in LIST: if ---: del LIST[i]
上でValueErrorが出たが下で書きなおしたら出なくなった.
全体の処理的には同じ位置を削除するようにしたつもりだけど何故だろう.
k-means法 準備
k-means法で理想的な結果が出せるようにデータを予めプロットしておく方法
# -*- coding: utf-8 -*- impo from sklearn.datasets import make_blobs import matplotlib.pyplot as plt X,y = make_blobs(n_samples=150, #サンプル点の総数 n_features=2, #特徴量の個数 centers=5, #クラスタの個数 cluster_std=0.5,#クラスタの標準偏差 shuffle=True, #サンプルをシャッフル random_state=0) #乱数生成器の状態を指定 plt.scatter(X[:,0],X[:,1],c='blue',marker='o',s=30) plt.grid() plt.show()
plt.scatter()の色指定はcolorはcでもイイらしい.
横軸にX[:,0],縦軸にX[:,1]をセット
X[:,0]はXの全ての要素の1つ目の要素という意味
plt.scatter(X[:,0],X[:,1],c='blue',marker='o',s=30)
Irisのデータプロット
# -*- coding: utf-8 -*- impo import pandas as pd import matplotlib.pyplot as plt import numpy as np #データの取得 df = pd.read_csv("https://archive.ics.uci.edu/ml/machine-learning-databases/iris/iris.data",header=None) df.tail() #1-100行目の目的変数の抽出 y = df.iloc[0:100,4].values #Iris-setosaを-1,Iris-virginicaを1に変換 y = np.where(y=="Iris-setosa",-1,1) #1-100行目の1,3列目の抽出 X = df.iloc[0:100,[0,2]].values #品種setosaのプロット(赤の○) plt.scatter(X[:50,0],X[:50,1],color='red',marker='o',label='setosa') #品種versicolorのプロット(青のx) plt.scatter(X[50:100,0],X[50:100,1],color='blue',marker='x',label='varsicolor') #軸のラベルの設定 plt.xlabel('sepal length [cm]') plt.ylabel('pepal length [cm]') #判例の設定 plt.legend(loc='upper left') #図の表示 plt.show()
ラベルの変換方法
名前(文字列)を数値に変換
y = np.where(y == 'Iris-setosa',-1,1)
1-100行目の1,3列目の抽出をする.
X = df.iloc[0:100,[0,2]].values
1-50行目の1つ目の要素をX軸に2つ目の要素をY軸とし青ｘをプロット
plt.scatter(X[:50,0],X[:50,1],color='blue',marker='x',label='varsicolor')
Tweepy
#!/usr/bin/env python # -*- coding:utf-8 -*- import tweepy CONSUMER_KEY = '-----------------------' # Consumer Key CONSUMER_SECRET = '-----------------------' # Consumer Secret auth = tweepy.OAuthHandler(CONSUMER_KEY, CONSUMER_SECRET) ACCESS_TOKEN = '-----------------------' # Access Token ACCESS_SECRET = '-----------------------' # Accesss Token Secert auth.set_access_token(ACCESS_TOKEN, ACCESS_SECRET) #APIインスタンスを作成 api = tweepy.API(auth) # これだけで、Twitter APIをPythonから操作するための準備は完了。 print('Done!') #タイムライン上の最新ツイートを参照する print api.home_timeline()[0].text #自分のアカウントでつぶやく api.update_status(status='test from Tweepy') #ツイート検索 #エラー出た search_result = api.search(q='もふもふ') for result in search_result: print result.text
k-means法
k-means法はプロトタイプベース(prototype-based)クラスタリングというカテゴリに属している.
アルゴリズムは以下の通りである.
1.クラスタの中心の初期値として,サンプル点からk個のセントロイドをランダムに選びだす.
2.各サンプルを最も近いセントロイドに割り当てる.
3.セントロイドに割り当てられたサンプルの中心にセントロイドを移動する.
4.サンプル点へのクラスタの割当が変化しなくなるか,ユーザー定義の許容値またはイテレーションの最大回数に達するまでステップ2-3を繰り返す.
ステップ4について,オブジェクトの類似度を測定するにはm次元空間にある2つの点
xベクトルとyベクトルのユークリッド距離の2乗は
【Calc】セル内改行
LibreOfficeCalcのセル内改行をするショートカット
Ctrl + Enter
ABC022_C
頂点1を含まないグラフを考えてその最短経路を作れば良いと思ったが
頂点1を含まないグラフの作り方 == 頂点1に隣接している頂点の選び方O(N^2)
dijkstra法O(N^2)
よって全体でO(N^4)掛かってしまい案の定TLEだった.
#include <bits/stdc++.h> using namespace std; static const int WHITE = 0; static const int GRAY = 1; static const int BLACK = 2; static const int INF = 1<<21; static const int MAX_N = 300; static const int MAX_M = 45000; int n,m; int res = INF; int u[MAX_M],v[MAX_M],l[MAX_M]; int M[MAX_N][MAX_N]; int color[MAX_N],d[MAX_N]; void dijkstra(int s){//最短経路を求める int mincost; //初期化：全ての頂点uに対してcolor[u]をWHITE,d[u]をINF,d[s]=0,p[s]=-1; for(int u=0;u<n;u++){ color[u] = WHITE; d[u] = INF; } d[s] = 0; color[s] = GRAY; while(1){ mincost = INF; int u = -1; for(int i=0;i<n;i++){ if(color[i]!=BLACK && d[i]<mincost){ mincost = d[i]; u = i; } } if(u==-1){ break; } color[u] = BLACK; for(int v=0;v<n;v++){ if(color[v]!=BLACK && M[u][v]!=INF){ if(d[v]>d[u]+M[u][v]){ d[v] = d[u]+M[u][v]; color[v] = GRAY; } } } } } int main() { cin>>n>>m; for(int i=0;i<m;i++){ cin>>u[i]>>v[i]>>l[i];//家u[i]から家v[i]までの距離がl[i] } //隣接グラフにする for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ M[i][j] = INF; } } for(int i=0;i<m;i++){ M[u[i]-1][v[i]-1] = l[i]; M[v[i]-1][u[i]-1] = l[i]; } //始点1に隣接する接点を2つ選ぶ for(int i=0;i<n-1;i++){ for(int j=i+1;j<n;j++){ if(M[0][i]!=INF && M[0][j]!=INF){//始点に2つ隣接する頂点があったら int tmp1 = M[0][i]; int tmp2 = M[0][j]; M[0][i] = INF; M[0][j] = INF; dijkstra(i); res = min(res,tmp1 + tmp2 + d[j]); M[0][i] = tmp1; M[0][j] = tmp2; } } } if(res==INF)res = -1; cout<<res<<endl; return 0; }
そこでwarshall_froyd法を用いた.
warshall_floyd法はグラフの全ての頂点の間の最短路を見つけるアルゴリズム.
#include <iostream> #include <vector> #include <algorithm> using namespace std; typedef vector<vector<int> > Matrix; const int INF = 1<<21; Matrix d;//隣接行列 void warshall_floyd(int n){//n：頂点数 for(int i=0;i<n;i++){//経由する頂点 for(int j=0;j<n;j++){//開始頂点 for(int k=0;k<n;k++){//終端 d[j][k] = min(d[j][k],d[j][i] + d[i][k]);//j->kの経路がiを経由して短縮できたら更新する } } } } int main(){ int n,m; cin>>n; d = Matrix(n,vector<int>(n,INF));//n*n行列,要素はINF for(int i=0;i<n;i++){ d[i][i] = 0; } cin>>m; for(int i=0;i<m;i++){ int from,to,cost; cin>>from>>to>>cost; d[from][to] = cost; d[to][from] = cost; } warshall_floyd(n); for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(i!=j && d[i][j]!=INF){ cout<<i<<"から"<<j<<"へのコスト："<<d[i][j]<<endl; } } } return 0; }
最短経路問題（ベルマンフォード法・ワーシャルフロイド法） - アルゴリズム講習会
abc022.contest.atcoder.jp
解答
#include <iostream> #include <vector> #include <algorithm> using namespace std; static const int MAX_N = 300; typedef vector<vector<int> > Matrix; const int INF = 1<<29; Matrix d;//隣接行列 void warshall_floyd(int n){//n：頂点数 for(int i=1;i<n;i++){//経由する頂点 for(int j=1;j<n;j++){//開始頂点 for(int k=1;k<n;k++){//終端 d[j][k] = min(d[j][k],d[j][i] + d[i][k]);//j->kの経路がiを経由して短縮できたら更新する } } } } int main(){ int n,m; cin>>n; d = Matrix(n,vector<int>(n,INF));//n*n行列,要素はINF for(int i=0;i<n;i++){ d[i][i] = 0; } cin>>m; for(int i=0;i<m;i++){ int from,to,cost; cin>>from>>to>>cost; d[from-1][to-1] = cost; d[to-1][from-1] = cost; } //WFで頂点1以外の最短経路を更新 warshall_floyd(n); //頂点1から隣接した2点に int res = INF; for(int i=1;i<n-1;i++){ for(int j=i+1;j<n;j++){ res = min(res,d[0][i]+d[0][j]+d[i][j]); } } cout<<(res!=INF?res:-1)<<endl; return 0; }
ABC007_C
幅優先探索の問題
queueにいれて順番に計算していく.
座標を扱う際にtypedefが便利
typedef pair<int,int> P; que.push(P(x,y));
#include <bits/stdc++.h> using namespace std; int r,c,sx,sy,gx,gy; int dx[4] = {1,0,-1,0},dy[4] = {0,1,0,-1}; static const int MAX_R =50; static const int INF = 1<<21; char M[MAX_R][MAX_R+1]; int D[MAX_R][MAX_R]; typedef pair<int,int> P; int main() { queue<P> que; cin>>r>>c>>sy>>sx>>gy>>gx; sy--;sx--;gy--;gx--; string tmp; for(int y=0;y<r;y++){ cin>>tmp; for(int x=0;x<c;x++){ M[y][x] = tmp[x]; D[y][x] = INF; } } D[sy][sx] = 0; que.push(P(sx,sy)); while(!que.empty()){ P p = que.front();que.pop(); int x = p.first; int y = p.second; if(x==gx && y==gy)break; for(int i=0;i<4;i++){ int nx = x + dx[i]; int ny = y + dy[i]; if(0<=nx && nx<c && 0<=ny && ny<r && M[ny][nx]=='.' && D[ny][nx]==INF){ que.push(P(nx,ny)); D[ny][nx] = D[y][x] + 1; } } } cout<<D[gy][gx]<<endl; return 0; }
