Explore
For Enterprise
Join for Free
Log In

예술 & 인문학
비즈니스
컴퓨터 공학
데이터 과학
정보 기술
건강
수학 및 논리
자기개발
물리 과학 및 공학
사회 과학
언어 학습
학위
수료증

Explore all of Coursera

검색
포 엔터프라이즈 (For Enterprise)
로그인
무료 회원 가입

Problem Overview and Naive Algorithm

Loading...

Algorithmic Toolbox

캘리포니아 샌디에고 대학교

4.7(4,771개의 평가) | 150K명의 학생이 등록함

데이터 구조 및 알고리즘 전문 분야에서 6의 강좌 1

The course covers basic algorithmic techniques and ideas for computational problems arising frequently in practical applications: sorting and searching, divide and conquer, greedy algorithms, dynamic programming. We will learn a lot of theory: how to sort data and how it helps for searching; how to break a large problem into pieces and solve them recursively; when it makes sense to proceed greedily; how dynamic programming is used in genomic studies. You will practice solving computational problems, designing new algorithms, and implementing solutions efficiently (so that they run in less than a second).

강의 계획서 보기

배우게 될 기술

Dynamic Programming, Debugging, Software Testing, Algorithms, Computer Programming

검토

4.7(4,771개의 평가)

5 stars
3,567 ratings
4 stars
958 ratings
3 stars
169 ratings
2 stars
35 ratings
1 star
42 ratings

MB

Mar 06, 2018

Cool course. Thank you! One suggestion about your book (Learning Algorithms Through Programming and Puzzle Solving): could you add some theory which would serve as a brief reminder before problems?

PR

Feb 10, 2019

The course is perfectly designed. The perfect start for those who start with data structures and algorithms. The Dynamic programming was a little bit tough but overall course is perfectly designed

수업에서

Algorithmic Warm-up

In this module you will learn that programs based on efficient algorithms can solve the same problem billions of times faster than programs based on naïve algorithms. You will learn how to estimate the running time and memory of an algorithm without even implementing it. Armed with this knowledge, you will be able to compare various algorithms, select the most efficient ones, and finally implement them as our programming challenges!

Problem Overview and Naive Algorithm4:03

Efficient Algorithm5:50

강사:

Alexander S. Kulikov
Visiting Professor
Michael Levin
Lecturer
Neil Rhodes
Adjunct Faculty
Pavel Pevzner
Professor
Daniel M Kane
Assistant Professor

스크립트

Hello everybody.

Welcome back.

Today, we're going to be talking about computing greatest common divisors.

So, in particular, what we'd like to do this lecture,

is we're going to define the greatest common divisor problem.

And, we're going to talk about an inefficient way to compute them.

And, next lecture we'll talk about how to do better.

So, okay.

What are GCDs?

So, suppose that you have a fraction, a over b.

And, you want to put it in simplest form.

Now, the standard way of doing this, is we want to divide the numerator and

denominator both by some d, to get some equivalent fraction, a/d / b/d.

Fair enough.

Now, what d do we want to use for this?

Well, it needs to satisfy two properties.

Firstly, d had better divide both a and b, since the new numerator and

denominator are both integers.

But, subject to that, we would like this d to be as large as possible.

So, that we can reduce the fraction as much as we possibly can.

So, turning this into a definition, we say that for two integers, a and

b, their greatest common divisor, or GCD,

is the largest integer d that divides both a and b.

Okay, so this is a thing that you use to reduce fractions.

However, it turns out that GCDs are a critically important

concept in the field of number theory.

The study of prime numbers, and factorization, and things like that.

And, because it's so important to number theory, it turns out that being able to

compute GCDs is actually very important in cryptography.

And, the fact that you can perform secure online banking is, in part,

due to the fact that we can efficiently compute GCDs of numbers in order for

our cryptographic algorithms to work.

So, because of this importance, we're going to want to be able to compute GCDs.

So, we'd like an algorithm that, given two integers, a and b, at say, at least 0,

we can compute the GCD of a and b.

And, just to be clear as to what kinds of inputs we care about,

we'd actually like to be able to run this on very large numbers.

We don't just want something that works for GCD of 5 and 12, or 11 and 73.

We'd like to be able to do things like the GCD of

3,918,848 with 1,653,264.

In fact, we'd also like to be able to compute much bigger numbers,

20, 50, 100, 1000 digits.

We'd still like to be able to get GCDs of numbers of those sizes pretty quickly.

Well, let's get started.

Let's start by just finding an algorithm that works.

What we'd like is the largest number that divides both a and b.

So, one thing we can do,

is we can just check all of the numbers that are candidates for

this, figure out which ones divide a and b, and return the largest one.

So, there's an easy implementation for this.

We create a variable called best, and set it to 0.

This just remembers the biggest thing we've seen so far.

We then let d run from 1 to a + b,

since this is the range of numbers that are valid.

Now, if d divides a, and d divides b, well, since d is increasing,

this has to be the new best that we've seen.

So, we set best equal to d, and then, at the end the of the day,

we return back the best thing we've seen.

So, that's a perfectly good algorithm.

It works.

Unfortunately, it's a little bit slow,

because we need to run through this for loop a + b many times.

And, this means that, even once a and b are, say, 20 digit numbers, it's already

going to be taking us at least thousands of years in order to run this computation.

And, so that's not sufficient for the sorts of applications that we care about.

We're going to need a better algorithm.

So, come back next lecture, and we'll talk about how to find a better algorithm for

this problem, and what goes into that.

Coursera 카탈로그 살펴보기

무료로 참여해 맞춤화된 추천, 업데이트 및 제안을 받아보세요.

Coursera는 세계 최고의 교육에 대한 보편적인 접근 기회를 제공하며, 최고의 대학 및 기관들과 제휴하여 온라인 강좌를 제공합니다.

© 2019 Coursera Inc. All rights reserved.

앱스토어에서 다운로드하기

구글 플레이에서 받기

Coursera
소개
리더십
직업
카탈로그
수료증
MasterTrack™ 수료증
학위
포 엔터프라이즈 (For Enterprise)
정부용

커뮤니티
Learners
Partners
Developers
Beta Testers
Translators

연결
블로그
Facebook
Linkedin
Twitter
Instagram
YouTube
기술 블로그

이상
조건
개인정보 보호
도움말
접근성
보도 자료
문의하기
디렉토리
계열사