アルゴリズムの世界地図 - Qiita
0. アルゴリズムとは？ まず、アルゴリズムとは何かを説明します。（0 節の説明はスライド「50 分で学ぶアルゴリズム」 の説明を参考にして書きました） さて、次の問題を考えてみましょう。 問題： 1 + 2 + 3 + … + 100 の値を計算してください。 単純な方法として、式の通りに 1 つずつ足していく方法が考えられます。すると、以下の図のように答えが計算されることになります。 これで答え 5050 が正しく求まりました。これはれっきとした アルゴリズム であり、この問題を 99 回の足し算 で解いています。しかし、計算回数が多く、計算に時間がかかるのではないかと思った方もいると思います。 ここで、方法を変えて、「1 + 100」「2 + 99」「3 + 98」…「50 + 51」の合計を求めることで、1 + 2 + 3 + … + 100 の値を計算してみましょう。 50 個の
レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】 - Qiita
※ ダイクストラ法・ワーシャルフロイド法は最短経路問題を解くアルゴリズムです。 ※ クラスカル法は最小全域木問題を解くアルゴリズムです。 それらのアルゴリズムが学習できる記事たちなどを紹介します。 全探索 全探索には、「全列挙」「ビット全探索」「順列全探索」「再帰関数を用いた全探索」など多くの種類に分かれます。しかし、基本的に以下の記事を読めば全部理解できます。 全列挙 たのしい探索アルゴリズムの世界【前編：全探索、bit全探索から半分全列挙まで】 の 2 章 その他の全探索 たのしい探索アルゴリズムの世界【前編：全探索、bit全探索から半分全列挙まで】 の 3 章 二分探索 アルゴリズムの代表例ともいわれる二分探索は、以下の 2 記事で解説されています。 二分探索とは：アルゴリズムを勉強するなら二分探索から始めよう！ 『なっとく！アルゴリズム』より 競プロで使える二分探索：二分探索アルゴ
計算量オーダーの求め方を総整理！ 〜 どこから log が出て来るか 〜 - Qiita
NTT データ数理システムでリサーチャーをしている大槻 (通称、けんちょん) です。今回は計算量オーダーの求め方について書きます。 0. はじめに 世の中の様々なシステムやソフトウェアはアルゴリズムによって支えられています。Qiita Contribution ランキング作成のために用いるソートアルゴリズムのような単純なものから、カーナビに使われている Dijkstra 法、流行中のディープラーニングに用いられている確率的勾配降下法など、様々な場面でアルゴリズムが活躍しています。アルゴリズムとはどんなものかについて具体的に知りたい方には以下の記事が参考になると思います: アルゴリズムとは何か ～ 文系理系問わず楽しめる精選 6 問 ～ アルゴリズムを学ぶと $O(n^2)$ や $O(n\log{n})$ や $O(2^n)$ といった計算量オーダーの概念が登場します。こうした記法を見ると
マクドナルドで一日分の栄養を取れる組み合わせを計算したら衝撃の結果に - Qiita
コレステロールは最低摂取基準量はないので0としています（実はこれが伏線になっている）。 そして目的は、一日必要な栄養素を満たす最もカロリーの低い商品の組み合わせとします。金に糸目はつけません。健康第一！ 解く 商品の数が96個、栄養素の数が16個なので、とても人間の手では解けません。そこでコンピューターの力を借ります。幸いPuLPというPythonで無料で利用できるソルバーがあるので、これで計算します。ちなみにExcelにもソルバーが搭載されていますが、この程度の数の決定変数でもエラーになって計算できませんでした。 # Import PuLP modeler functions from pulp import * # A new LP problem prob = LpProblem(name="mac", sense=LpMinimize) # Variables AA = LpVar
完全栄養マクドナルド食の線型計画による実装～もしマクドナルドだけで生活すると栄養バランスはどうなるのか？～ - Qiita
完全栄養マクドナルド食の線型計画による実装～もしマクドナルドだけで生活すると栄養バランスはどうなるのか？～PythonMacデータ分析データサイエンスマクドナルド 背景と概要 マクドナルドが大好きである。 しかし、ジャンクフード、健康に悪い、 などという話は以前よりよく見かける。 では本当にマクドナルドを食べ続けると、 健康に悪いのだろうか？ マクドナルドだけで生活する場合本当に、 栄養の偏りやカロリー過剰などが発生するのだろうか？ 本稿は、マクドナルドだけで 一日に必要なすべての栄養素を摂取する食事 をする場合に、どのようなメニューを選ぶべきで、 その結果どのような栄養問題が生じるのか、 PuLPというPythonの線型計画ライブラリを用いて 研究した結果をまとめたものである。 すなわち、マクドナルドだけで 完全栄養食としてのメニューを組み立てるには 何をどれだけ食べればいいの？ そして
遺伝的アルゴリズムでナーススケジューリング問題（シフト最適化）を解く - Qiita
この記事は ナーススケジューリング問題という最適化の問題を遺伝的アルゴリズムで解いてみたらまあまあの精度が出たので記録です pythonのdeapというライブラリを使っています 前提 ナーススケジューリング問題というものがあります 病院等の医療施設に勤める看護師の勤務スケジュールを決定する問題のことであり，シフトスケジューリング問題の代表例である．日勤・夕勤・夜勤等の複雑なシフト勤務や多岐に渡る制約の考慮のため，実際にスケジュールを求めるのは人手では手間のかかる困難な作業であり・・・ 要するにシフト勤務のスケジュールを自動的に最適に組むというものです 制約が色々あって、必要人数を満たすような基本的なものから、公平性、必須な資格/役割、この２人は（仲が悪いから？）一緒に入れないなど、いくらでも複雑になりうる問題て感じで、完璧な解答を作るのは困難なので、近似解を求めるような分野みたいです *
しゃくとり法 (尺取り法) の解説と、それを用いる問題のまとめ - Qiita
0. はじめに 気軽な気持ちでプログラムを書いたら計算量オーダーが $O(n^2)$ になってしまって処理がメチャクチャ遅い、というのは大変あるあるです (この記事など)。そういった状況を打破するために、古来から $O(n^2)$ なアルゴリズムを $O(n)$ や $O(n\log{n})$ に改良するテクニックは無数に考案されて来ました。逆に本来なら $O(n)$ で終わるはずの処理を雑に実装したために $O(n^2)$ になってしまうトラップも無数に知られています。その辺りの話は以下に特集してみました: 特集！知らないと損をする計算量の話 今回は $O(n^2)$ を $O(n)$ にするテクニックの 1 つであるしゃくとり法について、個人的に思うことを書いて行きます。またしゃくとり法を用いる以下の問題たちを紹介します: AOJ Course The Number of Window
最短経路問題総特集！！！～BFSから拡張ダイクストラまで～ - Qiita
基本的アルゴリズム（幅優先探索など）から応用（経路復元、拡張ダイクストラなど）まで、最短経路問題に関するアルゴリズムを総特集しました。 基本的なグラフ理論の用語については、次を参考にしてください。 グラフ理論 用語集 queueなどのデータ構造の用語については、次のスライドの後半を参考にしてください。 C++ STL講習会 by @e869120 最短経路問題とは 一般的に、次のような問題とされます。 $V$ 頂点と $E$ 辺からなるグラフが与えられる。頂点 $u$ と 頂点 $v$ を結ぶパスのうち、重みの総和が最も小さいものはどれか。 始点を固定して他のすべての頂点との対について最短経路問題を解く場合や、任意の2頂点の対について解く場合などが実際には多いです。 実社会とも強く密着した問題のため、古くからたくさん効率的な解法が考えられてきました。 今回はそれらを紹介しつつ、細かいテクニ
スーパーマリオのジャンプのアルゴリズム - Qiita
先日、気持ちのいいジャンプを目指してというQiitaの記事を見かけました。記事中では、マリオのジャンプについても触れられています。マリオというと、マリオブラザースやスーパーマリオブラザース等々、色々あるのですが、これはおそらくスーパーマリオブラザースの事だと思われます。ジャンプアクションゲームといったらスーマリですね。 そのマリオのジャンプの仕組みは「マリオの速度ベクトルを保存しておいて座標を計算するんじゃなくて～」と書かれていて、別サイトのブログへのリンクが張られています。 マリオのジャンプ実装法とVerlet積分 ただ、この記述については不正確であるという別のブログもあったりします。 マリオの完コピvol.28 ジャンプの解析と修正 ホントのところはどうなんでしょうか？世界で最も有名なゲームのジャンプがどのように処理されているのか気になったので調べてみることにしました。 原典にあたる
AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～ - Qiita
本記事を終えた次は？ AtCoder Beginners Selection を終えたら、AtCoder 上の過去問が AtCoder Problems に集大成されていますので、片っ端から埋めるような気持ちで精進していきましょう。本記事の続編として AtCoder 版！蟻本 (初級編) AtCoder 版！蟻本 (中級編) AtCoder 版！蟻本 (上級編) AtCoder 版！蟻本 (発展的トピック編) も執筆しましたので参考にしていただけたらと思います。また、アルゴリズムとデータ構造に関するトピックを集大成した書籍として、 問題解決力を鍛える！アルゴリズムとデータ構造 (通称、けんちょん本) を上梓しました。ぜひ読んでみてください。 1. AtCoder とは AtCoder は以下のコンテストサイトを運営しています。今後常に訪れることになるサイトです: AtCoder コンテスト
#2 Google OR-toolsを使って線形計画問題に制約条件を付ける - Qiita
モチベーション 「あたらしい数理最適化 python言語とGurobiで解く」 を教科書として、数理最適化の基本となるところを、肌感覚で理解したい。そのために、 基礎的な内容 その例題演習 を書くことで、自身の理解と、新たな仕事の確保を目指します。私の大本のモチベーションはここを参照してください。 この記事を読むとできること Google OR-Toolで制約条件付きの簡単な問題を解けるようにする を目指します。 ステップ1: 写経 例の如く、Python用のStart Guideから、写経をしていきます。以下、引用。 from __future__ import print_function from ortools.linear_solver import pywraplp def main(): solver = pywraplp.Solver( 'SolveSimpleSystem
データの種類の理解と線形回帰ことはじめ - Qiita
昨日は統計のウソを見破る 5 つの視点として統計的誤りに関する注意点を説明しました。 本日はここであらためて、分析しようとしているデータそのものにスポットを当ててみたいと思います。 KPI (key performance indicator) とは目標を達成するために何が必要かを定量的に表す数値です。整形して美人になりたいというのは KPI ではありませんが、体重を 3 ヶ月後までに 10 キロ減らすとか鼻を 1.5 センチ高くするといったものは KPI です。 データにはどのような種類があり KPI として利用しようとしている指標はどんなデータなのか正しく理解していないとしばしば誤った KPI を導き、無意味なデータ分析へとつながる危険を孕みます。 変数とは 社会調査や医療統計など様々な分野で被調査対象者の状態を多方面から特定していきます。たとえばアンケートやカルテを想定してみましょう
線形回帰と相関係数、そして東京の平均気温を実際に分析してみる - Qiita
線形回帰における仮定 前々回、前回 と線形回帰について説明してきました。 線形回帰における最小二乗法では Y 軸の点と点の全体的な長さの差異 (= これを、それぞれの差の二乗を取ってから加算するので二乗誤差といいます) が最小になるように、まっすぐな線 (= 1 次式の直線となる関数) を求めました。すなわち、データの集合から直線に回帰する推定をおこなったわけです。 相関係数を求める どんな 2 次元データでも線形回帰で関数を導くことはできますが、それが妥当かどうか気になります。そこで両者の相関係数を求めます。相関係数はベクトル v1, v2 からそれぞれの要素 x, y の平均を求め、次に v1, v2 の分散と共分散を求めます。コードで表現してみましょう。 def correlation(data): n = len(data) # 二次元データの長さを n に求める xm = 0.0
[Review] Wide&Deep Learning - Qiita
Main Question can we teach computers to learn like humans do, by combining the power of memorization and generalization? Study Resources Tensorflow Tutorial Nice Qiita Post in Japanese Research Blog Visual Concept Case Study Let's say one day you wake up with an idea for a new app called FoodIO*. A user of the app just needs to say out loud what kind of food he/she is craving for (the query). The
![[Review] Wide&Deep Learning - Qiita](https://cdn-ak-scissors.b.st-hatena.com/image/square/64986902f6134033c8a8a43fdb6ff7dd4f701b1e/height=288;version=1;width=512/https%3A%2F%2Fqiita-user-contents.imgix.net%2Fhttps%253A%252F%252Fcdn.qiita.com%252Fassets%252Fpublic%252Farticle-ogp-background-9f5428127621718a910c8b63951390ad.png%3Fixlib%3Drb-4.0.0%26w%3D1200%26mark64%3DaHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZ3PTkxNiZoPTMzNiZ0eHQ9JTVCUmV2aWV3JTVEJTIwV2lkZSUyNkRlZXAlMjBMZWFybmluZyZ0eHQtY29sb3I9JTIzMjEyMTIxJnR4dC1mb250PUhpcmFnaW5vJTIwU2FucyUyMFc2JnR4dC1zaXplPTU2JnR4dC1jbGlwPWVsbGlwc2lzJnR4dC1hbGlnbj1sZWZ0JTJDdG9wJnM9M2MwODk1MjUyNjBjOGFlNzUzZTBlNjM5ODJjYWU5ZmE%26mark-x%3D142%26mark-y%3D112%26blend64%3DaHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZ3PTYxNiZ0eHQ9JTQwUm93aW5nMDkxNCZ0eHQtY29sb3I9JTIzMjEyMTIxJnR4dC1mb250PUhpcmFnaW5vJTIwU2FucyUyMFc2JnR4dC1zaXplPTM2JnR4dC1hbGlnbj1sZWZ0JTJDdG9wJnM9ZmZlYzg2MWVmZTZlYjgzNWRiYWViMGE2N2NkMzI0Mzc%26blend-x%3D142%26blend-y%3D491%26blend-mode%3Dnormal%26s%3D601220007381e2ed179c693441784adc)
LinearRegression クラスについてメモ - Qiita
sklearn の LinearRegression クラスについての個人メモ。 LinearRegression とは 線形回帰モデルの一つ。説明変数の値から目的変数の値を予測する。 導入 import sklearn.linear_model.LinearRegression アトリビュート coef_ 回帰変数。 intercept_ 切片。 メソッド fit(x, y) 線形回帰モデルの当てはめを実行。訓練の開始。 xが対象データで、yが正解データ ※教師あり学習が前提 get_params() 推定に用いたパラメータを取得。 predict(x) モデルを使用して、xに対して予測を実行し予測値を算出する。 score(x, y) 決定係数を出力。予測値xと正解値yの相関を測る。 実践 import pandas as pd from sklearn.linear_model im
【機械学習】最小二乗法について メモ - Qiita
機械学習で使用することを前提として、最小二乗法についてまとめます。 ど文系のメモなので、誤りなどあったら指摘していただければ嬉しいです。 最小二乗法とは 最小二乗法(さいしょうにじょうほう、さいしょうじじょうほう；最小自乗法とも書く、英: least squares method)は、測定で得られた数値の組を、適当なモデルから想定される1次関数、対数曲線など特定の関数を用いて近似するときに、想定する関数が測定値に対してよい近似となるように、残差の二乗和を最小とするような係数を決定する方法、あるいはそのような方法によって近似を行うことである。(Wikipedia) あるデータの分散について回帰を行いたいときなどに用いる考え方。 回帰直線をはじめとし、ロッソ回帰やリッジ回帰などの根底となる概念。 数式について 数式 モデル関数を f(x) とするとき
[Review] Wide&Deep Learning for Recommender System - Qiita
Preface Basic Concept is well explained in this post. [Review] Wide&Deep Learning Research Paper Abstract Contents Introduction Recommender System Overview Wide & Deep Learning The Wide Component The Deep Component Joint Training of Wide & Deep Model System Implementation Data Generation Model Training Model Serving Experiment Results App Acquisitions Serving Performance Related Work Conclusion Re
![[Review] Wide&Deep Learning for Recommender System - Qiita](https://cdn-ak-scissors.b.st-hatena.com/image/square/be906d4e70328ec5bee311270a7f5a8d64eafd11/height=288;version=1;width=512/https%3A%2F%2Fqiita-user-contents.imgix.net%2Fhttps%253A%252F%252Fcdn.qiita.com%252Fassets%252Fpublic%252Farticle-ogp-background-9f5428127621718a910c8b63951390ad.png%3Fixlib%3Drb-4.0.0%26w%3D1200%26mark64%3DaHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZ3PTkxNiZoPTMzNiZ0eHQ9JTVCUmV2aWV3JTVEJTIwV2lkZSUyNkRlZXAlMjBMZWFybmluZyUyMGZvciUyMFJlY29tbWVuZGVyJTIwU3lzdGVtJnR4dC1jb2xvcj0lMjMyMTIxMjEmdHh0LWZvbnQ9SGlyYWdpbm8lMjBTYW5zJTIwVzYmdHh0LXNpemU9NTYmdHh0LWNsaXA9ZWxsaXBzaXMmdHh0LWFsaWduPWxlZnQlMkN0b3Amcz1iMjUzMDhlNTgwYTMxZjc5ZGU5ZjU2OWVlZTRlMmRjZQ%26mark-x%3D142%26mark-y%3D112%26blend64%3DaHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZ3PTYxNiZ0eHQ9JTQwUm93aW5nMDkxNCZ0eHQtY29sb3I9JTIzMjEyMTIxJnR4dC1mb250PUhpcmFnaW5vJTIwU2FucyUyMFc2JnR4dC1zaXplPTM2JnR4dC1hbGlnbj1sZWZ0JTJDdG9wJnM9ZmZlYzg2MWVmZTZlYjgzNWRiYWViMGE2N2NkMzI0Mzc%26blend-x%3D142%26blend-y%3D491%26blend-mode%3Dnormal%26s%3Df1d64cdf203416c0a80540b3c47624a6)
プログラムは音楽だ (A program is a music.)
この資料の背景 この資料は、子供にプログラミングを教えるのに、音がなる題材だとデバッグが容易であることと、音楽活動をされているプログラマの方々との意見交換に基づいています。 何人かは、プログラマに転身される過程におつきあいしています。 そんな方の紹介からまず。 公開算譜(open source)は楽しいの (just want to have fun.) から参照しました。 # ある日の午後 音楽活動をされているプログラマの方と話をした。 音楽のこと。 オープンソースのこと。 心理学のこと。 音楽 音楽を専門家としてお金をもらって活動するか、 音楽以外の職業を持ち音楽を自分の楽しみとして活動するか、 それ以外にも色々な状況がある。 音楽から少し視点を変えて美術ならどうだろう。 美術であれば、専門家で、美術活動だけでは食えずに、 学校の先生をしたり、別に職業を持って絵を描いている人たちは大勢
ElixirでIoT#1.2：いろいろ分かるベンチマークを整備してみる - Qiita
この記事は「Elixir or Phoenix Advent Calendar 2017」の12日目です． 昨日は@zacky1972さんの「ZEAM開発ログv0.1.1 AI/MLを爆速にしたい！ Flow / GenStage でGPUを駆動できないの？」でした． はじめに こんにちは． カーネルや低レイヤを触ることが多いので，並行と並列の違いにはうるさいほうです． 先日の勉強会「fukuoka.ex#8(福岡Elixir会)：2018年 春のElixir入学式」にて発表した内容を加筆編集しながら，ElixirをIoTボードで動かしたらどうなんの？という異色ネタをお届けしています． これまでの記事では，IoTボード上でElixirが実行できる環境を構築してきました． ElixirでIoT#1.0：IoTボードへのLinux環境の準備 ElixirでIoT#1.1：IoTボードへのEli
コピペから脱却して自由に Deep Learning するための TensorFlow 再入門 - Qiita
はじめに TensorFlow はなかなかとっつきにくい部分があるかと思います。書き方が独特なので、慣れるまでに時間がかかるかと思います。公式の MNIST は一通りやったけど、自分で考えたディープニューラルネットワーク (DNN) をどう書いたらいいかわからない……なんてこともあるのではないでしょうか。 この記事では、シンプルな問題を題材にして、 TensorFlow をコピペに頼らず、自分の書きたい DNN を 低レベル API を使ってどのように書くかを最小構成で説明していきます（今さら感はありますが。。）。ベースは公式ドキュメントの Low Level APIs のあたり です。 内容としては： TensorFlow の最小構成要素 TensorFlow で線形関数のフィッティング TensorFlow で DNN を実装 のようになっています。また、以下のような方を対象としており
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
