[하루 한문제]20180508 정렬된(sorted) n개 원소를 이진 검색 알고리즘으로 찾는다고 할 때, 최악의 상황에 놓인다면 어느 정도의 시간이 걸리나요?

[하루 한문제]

이진 검색 알고리즘

(Binary Search Algorithm)

[문제]

정렬된(sorted) n개 원소를 이진 검색 알고

리즘으로 찾는다고 할 때, 최악의 상황에 놓인

다면 어느 정도의 시간이 걸리나요?

1.Θ(log⁡n  )             2. Θ(n)              3. Θ(n^2 )            4. Θ(1)

[정답]

1번

이 문제를 맞추신 분들이 있으신가요?

사실 저도 검색을 해봐야 알 수 있었답니다.

[문제풀이]

해당 문제를 푸시려면 두가지 개념을 아셔야 합니다.

하나는 "이진 검색 알고리즘이 무엇인가?" 이고

또다른 하나는 "점근표기법이 무엇인가" 입니다.

[이진 검색 알고리즘]

먼저 이진 검색 알고리즘에 대해서 알아봅시다.

이진 검색 알고리즘은 간단히 생각하면 up-down 게임입니다.

중앙의 숫자를 선택하면 up 혹은 down으로

원하는 값을 찾아가죠

(정렬되었다는 사실을 명심하세요!)

정렬된 원소집합에 사용할 수 있다는 단점이 있지만

한번 확인마다 목표값을 찾을 확률이

두배가 된다는 장점이 있습니다.

[점근표기법]

빅오는 점근표기법 (Asymptotic Notation) 중 하나입니다.

점근표기법 종류 

대문자 O 표기법

소문자 o 표기법

대문자 오메가(Ω) 표기법

소문자 오메가(ω) 표기법

대문자 세타(Θ) 표기법

Asymptotic Growth는 함수가 증가하는 정도를 나타냅니다.

이런 증가의 기준되는 함수 f(n)이 있다고 합시다.

그리고 우리가 관심있는 함수 g(n)이 있다고 합시다.

두개 함수의 관계는 아래와 같을 것입니다.

f(n)의 증가률이 g(n)의 증가률보다 같거나

f(n)의 증가률이 g(n)의 증가률보다 느리거나

f(n)의 증가률이 g(n)의 증가률보다 빠르거나

중 하나일 것입니다.

f(n)의 증가률이 g(n)의 증가률보다 같으면

f(n) = Θg(n)이라 표기하고

f(n)의 증가률이 g(n)의 증가률보다 느리면

f(n) = o(g(n))이라 표기하고

f(n)의 증가률이 g(n)의 증가률보다 빠르면

f(n) = w(g(n))으로 표기합니다.

f(n)의 증가률이 g(n)의 증가률보다 같거나 느리면

f(n)=0(g(n))으로 표시합니다.

[생각하기]

if f(n) = o(g(n)) then g(n) = w(f(n))

[산동일크무크]

여러분 이해 안되시면, 댓글을 남겨주세요!

일크무크는 전세계의 다양한 대학교에서

공부하는 대학원생들입니다.

여러분들의 댓글이 저희를 공부하게 만들고,

더 좋은 자료를 만들 수 있도록 도와줍니다.

"배워서 남주자"라는 가치를 우리 다 함께 실천해 보아요!

[양자컴퓨터][Quantum Computer]Log Day 1

QISKIT Dowload Instruction

ANACONDA & MINICONDA

Anaconda

A downloadable, free, open source, high-performance and optimized Python and R distribution. Anaconda includes conda, conda build, Python and 100+ automatically installed, open source scientific packages and their dependencies that have been tested to work well together, including SciPy, NumPy and many others.

ANACONDA DOWNLOAD

Miniconda

A free minimal installer for conda. Miniconda is a small, bootstrap version of Anaconda that includes only conda, Python, the packages they depend on and a small number of other useful packages, including pip, zlib and a few others.

MINICONDA DOWNLOAD

Reference Pages

ANACONDA DOCUMENTATION

[인상깊은 문구]스티븐 호킹: 쉽게 풀어 쓴 시간의 역사

<<스티븐 호킹: 쉽게 풀어 쓴 시간의 역사>>

지은이: 스티븐 호킹

옮긴이: 현정준

발행처: 청림출판

1판 1쇄 인쇄: 1995년 10월 15일

1판 10쇄 발행: 2002년 4월 30일

제 1장

P14 독일군은 옥스퍼드와 케임브리지를 폭격하지 않기로 합의했는데, 이것은 영국군이 하이델베르크와 괴팅겐을 폭격하지 않는다는데 대한 교환 조건

P24 스티븐은 세인트 앨반스 학교 1학년 때 성적은 바닥에서부터 세 번째였던 것으로 기억됩니다. 그래서 내가 “스티븐, 너는 정말 그렇게 밖에 못하니?”했더니 그는 “다른 애들이라고 훨씬 더 잘한 것도 없어요”라고 하면서 전혀 개의치도 않더군요. 그 아이의 학교성적은 썩 좋은 편이 아니었지만 웬일인지 그는 언제나 머리가 아주 좋은 것으로 인정받았습니다.

P25 호킹 아빠: 그의 관심은 분야를 불문하고 그저 연구하는 것에 있었지요. 우연히 그것이 의학이었고 또 그의 특정한 생활 환경이 그를 열대 지방 의학으로 이끌어 갔던 셈이지요.

P27 바실 킹: 내 기억에는 호킹의 집에 여러 번 갔었던 것 같아요. 그 집에서는 이를 테면 저녁 식사에 초대해 놓고 스티븐과 이야기를 하는 동안 다른 식구들은 식탁에서 책을 읽고 있는 식의 상황이 벌어지곤 했어요. 이런 일은 내가 아는 교제 범위에서는 용납되지 않는데, 호킹가에서는 있을 수 있는 일이었습니다.

P32 메리 호킹: 내 기억에는 스티븐이 어떤 책에 몰두하고 있는 광경이 아주 선명하게 남아 있어요. 그 책이 무엇이었는지는 모르지만 그의 옆에는 비스킷이 한 통 있었을 뿐 아무도 그의 관심을 끌 수 없었지요. 그는 이 책에 흠뻑 빠져 버렸고 비스킷은 감쪽같이 사라져 버렸어요. 그가 책에 나와 제 정신을 찾았을 때 비스킷이 온데간데 없는 것을 알고는 깜짝 놀랐습니다.

제 2장

P47 수학은 나에게 있어 물리학을 하는 수단에 지나지 않았어요.

P71 그러나 내가 퇴원한 직후 나는 마치 처형대에 놓여 있는 것처럼 느껴졌어요. 만약 내게 집행유예가 주어졌다면 내가 해볼 만한 일들이 많다는 사실을 갑자기 깨달았어요. 내 질병이 가져다 준 하나의 결과는 다음과 같은 것이지요. “때 이른 죽음의 가능성에 당면하게 되면 인간은 인생이 살 값어치가 있다는 것을 이해하게 된다.”

P72 나는 박사 학위를 끝낼 때까지 살아 있을 가망이 없었기 때문에 연구를 계속하는데 별 의미가 없을 것 같았습니다. 그러나 시간이 갈수록 병세는 지체하는 듯 했어요. 나는 일반 상대성 이론을 이해하기 시작했고 연구에도 진전을 봤습니다.

 그러나 실제로 변동이라고 생각되는 일은 내가 제인 와일드라는 여성과 약혼을 하게 된 사실입니다. 이것은 나에게 살아 갈 보람을 주는 동시에 우리가 결혼을 하려면 내가 일자리를 얻어야 한다는 사실을 의미하는 것이었습니다.

제 3장

P83 퀘이사, 혹은 준성은 1963년에 발견된 항성과 유사한 천체인데 이 천체는 엄청나게 많은 빛을 내고 있다. 퀘이사는 우주의 시초에 가까운 약 100억년 전쯤에 형성된 것으로 생각되고 있다.

펄서는 맥동 전파성의 약층이고 그 붕괴된 상태에 연유하는 전자파의 규칙적 맥파를 내고 있는 별인데 1976년에 발견되었다.

P103 우주의 밀도가 무한대였던 시기가 있었는가?

그것은 1965년에서 1970년 사이에 주로 로저 펜로즈와 내가 발전시켰습니다. 우리는 이 기술을 사용하여 만일 일반 상대성이 옳다면 과거에 밀도가 무한대로 되는 상태가 존재해야만 한다는 것을 증명했습니다. ‘대폭발 특이점’

P122 검은 구멍이 이 양자역학적 효과로 인하여 마치 고온의 물체처럼 복사를 내기 떄문에 검은 구멍이 검지 않다는 것을 내게 설명해 주었지요.

 이 일은 열역학과 상대론과 양자역학의 새로운 통일을 이룩하여 물리학에 대한 우리의 이해를 변화시키게 되었습니다.

제 4장

P148 ”나는 엄밀하기 보다는 오히려 올바르기만을 원한다”

P154 그러나 결국 우주가 팽창하고 있다는 사실이 밝혀지게 되자 아인슈타인은 그와 나의 위대한 친구 조지 가모프에게 말했어요 “그것은 내 일생 최대의 실수였네!”

P162 우주는 창조되지도 파괴되지도 않으며 그저 ‘존재’할 따름입니다.

P176 과거 수백년 동안에 보어와 아인슈타인 사이에 있었던 논쟁처럼 큰 논쟁은 없었다고 생각돼요. 그렇게 위대한 두 사람 사이에 28년 이라는 오랜 기간 동안 그들처럼 수준 높은 동료 의식을 갖고 진행된 논쟁은 말이죠.

P177 아인슈타인은 그가 쓴 논문 가운데 가장 많은 논의를 불러 일으켰던 논문에서 “양자론은 내가 이해하는 바로는 실재에 관한 합리적인 모든 생각과 모순된다.”고 말했어요

 보어는 이에 대해서 “실재에 관한 당신의 생각은 너무나 한정되어 있어요.”

제 5장

P206 이사벨 호킹: 호킹은 그 자신이 할 수 있다면 다른 사람도 모두 할 수 있다 생각했다.

[인상깊은 문구]뉴턴 – 사과는 왜 땅으로 떨어지는가

<<뉴턴 – 사과는 왜 땅으로 떨어지는가>>

시공 디스커버리 총서

장-피에르 모리 Jean-Pierre Maury

김윤 옮김

㈜ 시공사

초판 1쇄 발행 1996년 5월 20일

초판 7쇄 발행 2004년 12월 31일

제 1장 아이작 뉴턴의 휴가

P11 – 1665년 여름, 끔찍한 전염병이 창궐하자 케임브리지 대학은 문을 닫고 학생들과 교수들을 집으로 돌려보냈다. 이들 중에서 막 학사학위를 받은 청년 아이작 뉴턴이 있었다. 그는 평화롭고 조용한 곳을 찾아 고향인 영국의 시골로 떠났고, 그곳에서 1년을 보냈다. 이 시기에 풍성한 발견들이 이루어졌고, 따라서 후세 역사가들은 이때를 ‘기적의 해’라고 부른다.

P12 – 뉴턴이 독서, 실험, 단상 들을 공책에 기록하기 시작한 1664년부터, 그가 이미 갈릴레이의 <<두 개의 세계에 대한 대화>>, 르네 데카르트의 <<기하학>>, 그리고 요하네스 케플러의 저작 – 특히 빛에 관한 연구와 관련된 – 을 신중히 연구하고 이었음을 알 수 있다.

P17 – ‘백색’ 태양광선은 여러 빛깔을 띤 광선의 혼합물이고 이것들은 프리즘을 통과할 때 각각 서로 다른 정도로 굴절한다는 것이었다.

P18 – 태양광선이 단색광의 집합이라는 사실은 5년 동안이나 발표하지 않았지만, 그보다 더 결정적인 발견은 (만유인력) 그 후 20년 동안이나 공표되지 않았다.

제 2장 근대 천문학이 탄생

P29 – 1667년, 유럽의 많은 과학자들은 파리에서 활발한 활동을 벌였다. 파리 천문대가 건설되면서 파리는 가장 활발한 천문학 연구 중심지가 되었다.

프랑스 과학 아카데미 -> 지구 둘레, 태양과 지구 사이의 거리, 빛이 속도 측정

제 3장 반사망원경에서 중력으로

P57 - 라이프니츠는 독일의 탁월한 수학자였을 뿐만 아니라 철학자, 신학자, 역사가, 법률가였다. 그와 뉴턴은 각각 미분법을 개발했다. 하지만 일반적으로 라이프니츠의 방법이 채택되었다.

제 4장 마침내 만유인력!

P77 – 핼리는 오늘날 관점에서 보면 지구물리학자였다. 그는 지자기, 조수, 기류에 관련된 놀랄 만한 연구를 수행했고, 기상학적 현상 연구에서 중대한 발전을 이루었다. 태양열이 변화에 따라 공기 층의 수직운동이 일어나고 이로써 무역풍이 발생한다는 사실을 처음으로 설명한 사람도 그였다. 물의 순환-증발, 구름의 형성, 강우, 강, 대양, 증발 – 도 핼리의 발상이었다. 그래서 그는 열전도가 지구물리학에서 중심적인 역학을 하고 있다고 생각한 최초의 사람이 되었다.

P80 – 갈릴레이가 죽고 나서(1642) 물 펌프가 과학적 논쟁의 초점이 되었다. 물 펌프의 작동원리는 아리스토텔레스 적인 오래 된 개념인 진공을 싫어하는 자연으로 설명해야 할 것인가, 아니면, 갈릴레오의 조수인 에반젤리스다 토리첼리의 주장대로 기압으로 설명해야 할 것인가?

P81 – 그는 중력이 야기하고 전달하는 동인이 무엇인가에 관해서 <<프린키피아>>에서는 가능한 한 언급을 회피했다.

제 5장 승리에 승리를 거듭하다

P83 – 중력이론으로 과학자들은 지구의 양극이 평평하고, 핼리 혜성이 다시 나타나며, 새로운 행성이 존재한다는 예견을 할 수 있었다. 이 모든 것들이 150년안에 사실로 밝혀졌다.

P104 – 아마추어 천문학자 윌리엄 허셜 – 전문 음악인(낮), 천문학자(밤), 거울제작자(구름낀방)

천왕성 – 우라누스는 고대 그리스 신화에서 ‘하늘’이었다.

P123 – “그는 천성적으로 소박하고 온화했으며, 언제나 자신을 평범한 사람들의 수준에 놓았다. 다른 이들은 심지어 자신들보다 위에 있는 사람도 경멸하지만, 이 일등급 천재는 결코 자기 아래 사람들을 무시하지 않았다. 그는 자신의 업적이나 명성이 모든 평범한 일상생활의 의무들로부터 면제됨을 의미한다고는 생각하지 않았다. 그는 선천적이든 후천적이든 결코 특이하지 않았다. 그는 단지 평범한 한 사람이 어떻게 행동하는지를 알고 있었다.” - 1727년 뉴턴 사망 후 프랑스 과학 아카데미의 서기인 베르나르 르 보비에 드 퐁트넬의 조사 중

[영어강의]산동일크무크 X Learn English with Jennifer

산동일크무크 X Learn English with Jennifer

[완전기초반]

안녕하세요 산동일크무크 입니다.

저희 그룹에서 사회적 취약계층을 위한 영어강의 콘텐츠를 만들어서 기재하였습니다.

영어를 아에 못하시는분들도 들어며 따라가실 수 있을 난이도 입니다.

저희는 사회적 취약계층의 학생들에게 교육의 평등성을 제공하는것이 주 목표입니다.

"배워서 남주자"라는 가치를 함께 실천하고 싶으신 분들은 언제든지 환영합니다!

연락처: ilkmooc@ilkmooc.kr

홈페이지 주소: http://ilkmooc.kr/

[플라즈마 물리][Plasma Physics]CH1 Introduction - Plasma Frequency

"배워서 남주자"라는 가치를 가진 산동일크무크를 응원해주세요!

[Youtube Link]

Plasma Frequency

Consider a hypothetical slab of plasma, where we assume that the ions have infinite mass(immobile) and the electrons can move freely through the ions.

1. Suppose the electron slab is displaced a distance \(x\) to the right of the ion slab and then allowed to move freely.

2. An electric field will be set up, causing the electron slab to be pulled back toward the ions.

3. When the electrons exactly overlap the ions (when \(x=0\)), the net force is zero, but the electron slab overshoots.

4. The net result is harmonic oscillation. The frequency of the oscillation is called the electron plasma frequency.

Derivation for Plasma Frequency

From Gauss’s law,

\[\oint \vec{D} \cdot d\vec{a} = Q\]

we have

\[\epsilon_0 EA = neAx\]

or

\[E=\frac{nex}{\epsilon_0}\]

Since the force is given by

\[F=QE=(-neAx)(\frac{nex}{\epsilon_0})=nAxm_e \frac{d^2x}{dt^2}\]

we obtain the equation of motion

\[\begin{aligned} \frac{d^2x}{dt^2} = - \left( \frac{ne^2}{m_e \epsilon_0} \right) x\end{aligned}\]

or

\[\begin{aligned} \frac{d^2x}{dt^2} +\omega_{pe}^2x=0\end{aligned}\]

where

\[\begin{aligned} \boxed{\omega_{pe}=\sqrt{\frac{ne^2}{m_e \epsilon_0}}}\end{aligned}\]

This is electron plasma frequency.
\(\bullet\) If there are no collisions, the disturbance will oscillate indefinitely.
\(\bullet\) Debye length, thermal velocity, and plasma frequency are inter-related.

\[\frac{v_{th}}{\omega_{pe}}=\frac{\sqrt{\frac{K_BT}{m}}}{\sqrt{\frac{ne^2}{m\epsilon_0}}}=\sqrt{\frac{\epsilon_0 KT}{ne^2}}=\lambda_D\]

4차 산업혁명에 걸맞는 인터넷 기반 고등교육기관

이메일: ilkmooc@ilkmooc.kr

홈페이지주소: http://ilkmooc.kr

산동일크무크란? https://goo.gl/FnvqXd

[플라즈마 물리][Plasma Physics]CH1 Introduction - Plasma Parameter

"배워서 남주자"라는 가치를 가진 산동일크무크를 응원해주세요!

[Youtube Link]

Plasma Parameter

\(\bullet\) The plasma parameter is defined as

\[\begin{aligned} \boxed{ N_D =n\frac{4}{3}\pi \lambda_D^3 }=1.38 \times 10^6 \frac{T^{\frac{3}{2}}}{n^{\frac{1}{2}}} [T](in^{\circ}K)\end{aligned}\]

which is the number of plasma particles in a Debye sphere.

\(\bullet\) For Debye shielding to occur, and for the description of a plasma to be statistically meaningful, the number of particles in a Debye sphere must be large; that is \(N_D>>1\)

\(\bullet\) Plasma parameter is a measure of the ratio of the mean plasma kinetic energy to potential energy.

\[\frac{K.E.}{P.E.} \simeq \frac{\frac{3}{2}K_BT}{\frac{e^2}{4\pi\epsilon_0 \lambda_D}} \simeq \frac{9}{2}N_D >> 1\]

\(\bullet\) Thus \(N_D>>1\) means that the potential energy of a particle due to its nearest neighbor is much smaller than its kinetic energy. If this were not the case, there would be a strong tendency for electrons and ions to bind together into atoms, thus destroying the plasma.

\(\bullet\) An ideal gas corresponds to zero potential energy between the particles. Since the plasma parameter is large, the plasma may be treated as an ideal gas of charged particles, that is, a gas that can have a charge density and electric field but in which no two discrete particles interact.

\(\bullet\) In deriving the Debye potential, we assumed that the electrostatic energy was small compared to the thermal energy. The largeness of the plasma parameter guarantees the validity of the Debye potential.

4차 산업혁명에 걸맞는 인터넷 기반 고등교육기관

이메일: ilkmooc@ilkmooc.kr

홈페이지주소: http://ilkmooc.kr

산동일크무크란? https://goo.gl/FnvqXd

[플라즈마 물리][Plasma Physics]Introduction

Introduction to Plasma

\(\bullet\) We are surrounded by plasmas starting from the ionosphere a hundred kilometers above us, which is connected to the sun via the plasma of the solar wind.

\(\bullet\) The very tenuous interstellar space is a plasma and so are the largest objects that emit x-rays in the universe.

Plasma State

\(\bullet\) Plasma is a fundamental state of matter: by heating the mater changes from a solid \(\rightarrow\) liquid \(\rightarrow\) gas \(\rightarrow\) plasma.

\(\bullet\) When gas is heated above a certain temperature, or it is subject to strong electromagnetic fields, it gets ionized, and a transition towards the so-called fourth state of matter(coined by W.crookes in 1879), plasma state, is observed.

\(\bullet\) Compare

• Ancient: Universe - Earth, water, air, fire

• Modern: Universe - solid, liquid, gas, plasma

\(\bullet\) Plasma: Introduced by Tonks and Irving Langmuir(Nobel Prize winner) in 1928.

\(\bullet\) Plasma: Greek words - moldable substacne; jelly.

\(\bullet\) Plasma ionized gas with \(n_e = n_i\); macroscopically charged neutral. Much more complicated than many single charged particle becuase of collective effects.

Definition of Plasma

\(\bullet\) The ensemble of freely moving charged particles of both signs, i.e., ionized gas, can be considered as plasma if the Debye length is small compared with dimensions of the volume occupied by the gas. (Langmuir)

\(\bullet\) A plasma is a quasi-neutral gas of charged and neutral particles which exhibits collective behavior (F.F. Chen)

\(\bullet\) A plasma is a gas of charged particles, in which the potential energy of a typical particle due to its nearest neighbor is much smaller than its kinetic energy. (D. R. Nicholson)

\(\bullet\) A plasma may be roughly defined as a system containing mobile charges, in which the electric and magnetic interactions between particles play a dominant role in the dynamics of the systems. (J. M. Dawson)

\(\bullet\) A plasma is collection of charged particles, usually of opposite sign, that tends to be electrically neutral. We often describe a plasma as the fourth state of matter. Adding energy to a solid melts it and it becomes a liquid; adding energy to a liquid boils it and ib becomes a gas; adding energy to a gas ionizes it and it becomes a plasma. (J. L. Shohet)

\(\bullet\)The plasma state is a characteriza

4차 산업혁명에 걸맞는 인터넷 기반 고등교육기관

이메일: ilkmooc@ilkmooc.kr

홈페이지주소: http://ilkmooc.kr

산동일크무크란? https://goo.gl/FnvqXd