2011年3月8日 星期二

[Introduction To Algorithms] 第二堂: Growth of Functions(3)

asymptotic notation 的運算也就是集合的運算。


老師補充了 

  • Rule of Sum
  • Rule of Product
當作範例說明。注意這兩個 theorem 在程式中的應用。(時間和 vs 巢狀迴圈)






























這裡要注意一下,為什麼第一個式子成立,但第二個式子卻不成立。答:係數的問題。第一個式子 c 可以從 θ 拿過來。但第二個式子因為是加法,最高項的係數固定是 1 。 所以會有問題。














接下來老師花了一些時間證明 Rule of sum
這裡用三個單向來證明,舉例來說要證明 A=B=C ,用三個單向就是

  • A ≦ B
  • B ≦ C
  • C ≦ A
這樣就證明出 A=B=C 了。 三個單向證明都很簡單參考 p.26~p.28。
值得注意的是, for sufficient large n 這裡有三個 n0 要 n 要大於他們。但為了方便起見,用足夠大寫比較簡潔。
下面是一個 Rule of Sum 亂用的例子。
記住: 要用 asymptotically nonnegative function,而 max 的第二個 function 不管你 n 多大都無法是正數。














這張投影片才是正確的示範,不要亂用證明。




















這個證明很有用,也很常用到,但注意不要亂用(等下會有投影片說明),Cormen 教科書上直接用,老師補充 Rule of Sum (什麼是θ相加)對於這個定理的證明推倒之理解比較有幫助。
















這張也是講亂用的例子,這裡錯的原因是因為,這錯誤的式子用到多個 n0 個與 c0 ,記住要合併的話必須要找出共用的 n0 與 c。
p.32~p33 有舉例說明這個問題,可以參考。














接下來兩張投影片的 Theorem 比較少用,但是還是要注意一下,這張講的是 -1 在次方向時 ο與 Ω 要互換。這跟分數的比較大小很像。
















這裡要注意,式子左邊代表的不是集合的集合。
而是要再 Union 起來。跟一般的不太依樣,要注意。

















  • 3.2 Standard notations and common functions
p.38 ~ p.43 介紹了常用的 function 指數、對數、階層等等。微積分的基礎就很重要 (我忘得差不多了 = =) 概念性的像是 polynomials 代表的是上限為 poly 而不一定是指多項式函式。 Logarithms 再怎麼強都沒有poly 快。Logarithms的底沒有這麼重要 (用換底公式弄完後只是一個係數)。


     階層的話要注意 Stirling's formula,講義舉了三種方式證明,Summation 的證明方式很重要!!
     Harmonic number 也蠻常用的。


有用到再複習吧!! 我的微積分阿~~

2011年3月4日 星期五

Paparazzi-Part 3

這作業原本預計一個禮拜完成,結果多花了一個禮拜。我想主要原因是 Core Data 的部份我不熟,在 Part 2 時草草帶過,使得 Part 3 時不得不好好研究一下。


 
Part 2 時對於 relationship 的用法不是很瞭解,這次重新設計了 Core Data 就好很多。


這裡值得注意的是經度緯度我在 Data Model 用的Type是 double 但產生出來的 Code 卻是 NSNumber 






@class Person;
@interface Photo : NSManagedObject
{
}
@property (nonatomic, retain) NSNumber * longitude;
@property (nonatomic, retain) NSData * data;
@property (nonatomic, retain) NSNumber * watched;
@property (nonatomic, retain) NSNumber * latitude;
@property (nonatomic, retain) NSString * name;
@property (nonatomic, retain) id url;
@property (nonatomic, retain) Person * author;
@end


而要取值時: theCoordinate.longitude = [self.longitude doubleValue];
注意: MKAnnotation 並不是程式自己產生的,而是為了要讓 photo 直接有 location 的功能而加入的 delegate




另外,參考 More iPhone SDK 增加了 NSArray 的 Categories Set
@interface NSArray(Set)
+ (id)arrayByOrderingSet:(NSSet *)set byKey:(NSString *)key ascending:(BOOL)ascending;
@end 

值這樣就可以順利取出 photo set 了  (NSSet 轉 NSArray)

NSArray* array = [NSArray arrayByOrderingSet:thePerson.photos byKey:@"name" ascending:YES];


Flickr 從網路抓取圖片用作業提供的 JSON 和 FlickFetcher 來達成,此次作業用同步的方式來下載,所以會有點停頓。



之前我遇到的  Hierarchy NavigationBar 問題 其實很蠢 ==
UIViewController 本身就有 navigationController 所以.... 不用這麼麻煩,下面的 code 很簡單就達成:

[self.navigationController pushViewController:photoDetailViewController animated:YES];






#pragma mark -
#pragma mark MKMapViewDelegate
// note: you can assign a specific call out accessory view, or as MKMapViewDelegate you can implement:
- (void)mapView:(MKMapView *)mapView annotationView:(MKAnnotationView *)view calloutAccessoryControlTapped:(UIControl *)control{
//NSLog(@"%@",view.annotation);
Photo* thePhoto = (Photo*) view.annotation;
PhotoDetailViewController* photoDetailViewController = [[PhotoDetailViewController alloc] initWithNibName:@"PhotoDetailViewController" bundle:nil];
//photoDetailViewController.url = thePhoto.url;
photoDetailViewController.title = thePhoto.name;
photoDetailViewController.photo = thePhoto;
[self.navigationController setNavigationBarHidden:NO animated:NO];
[self.navigationController pushViewController:photoDetailViewController animated:YES];
[photoDetailViewController release];
}
- (MKAnnotationView *)mapView:(MKMapView *)theMapView viewForAnnotation:(id <MKAnnotation>)annotation
{
    // if it's the user location, just return nil.
    if ([annotation isKindOfClass:[MKUserLocation class]])
        return nil;
    
static NSString* AnnotationIdentifier = @"AnnotationIdentifier";
MKPinAnnotationView* pinView = (MKPinAnnotationView *)
    [self.map dequeueReusableAnnotationViewWithIdentifier:AnnotationIdentifier];
if (!pinView)
{
// if an existing pin view was not available, create one
MKPinAnnotationView* customPinView = [[[MKPinAnnotationView alloc]
  initWithAnnotation:annotation reuseIdentifier:AnnotationIdentifier] autorelease];
customPinView.pinColor = MKPinAnnotationColorPurple;
customPinView.animatesDrop = YES;
customPinView.canShowCallout = YES;
// add a detail disclosure button to the callout which will open a new view controller page
//
// note: you can assign a specific call out accessory view, or as MKMapViewDelegate you can implement:
//  - (void)mapView:(MKMapView *)mapView annotationView:(MKAnnotationView *)view calloutAccessoryControlTapped:(UIControl *)control;
//
UIButton* rightButton = [UIButton buttonWithType:UIButtonTypeDetailDisclosure];
//[rightButton addTarget:self
// action:@selector(showDetails:)
//   forControlEvents:UIControlEventTouchUpInside];
customPinView.rightCalloutAccessoryView = rightButton;
return customPinView;
}
else
{
pinView.annotation = annotation;
}
return pinView;
}



Map 顯示也是比較不熟,主要是參考 Apple 範例程式修改 MapCallouts
有些照片沒有地理位置資訊,我就不知道他是怎麼判斷的了。
看起來很多圖片都是在同一個位置上。


主要是實作上面的兩個 delegates








































要有 Scroll 功能記得要設 delegate

















剩下最後一個部份了  gogogogo!!

2011年3月3日 星期四

Oracle Technology Network (OTN) Developer Day

早上把大園的問題解決,下午趕場去聽 Java 的研討會,下面是 Agenda



Agenda
13:30-14:00報到
14:00-14:45Keynote Session
Java - The Language of the Future
14:45-15:25Technical Session 1
Java Development Kit 7 and Java SE 7
15:25-15:40Tea Break
15:40-16:20Technical Session 2
What's new in Java EE 6.0
16:20-17:00Technical Session 3
A Java-Enabled Platform for Ubiquitous Computing
17:00-17:10Q&A

  • Java - The Language of the Future

          第一個議程介紹了一下 Java 目前的網頁,與 RoadMap (GlassFish、Weblogic、JavaFX),跟技術比較無關,就不介紹了。

  • Java Development Kit 7 and Java SE 7

              第一個議程是段老師講的,講得很不錯,簡單易懂。 Java 7 增加了幾個特性。
      Nimbus、Project Da Vinic 、 Project Coin 等等。代號是海豚 (dolphin),



Name bus 讓外觀看起來比較漂亮。
投影片有兩個範例,展示各種 control 在各種 Look 看起來的狀況。









達文西計畫讓多種動態語言能在 JVM 上面執行,不過在 Java 6 上面執行效率不好,Java 7 多了兩個 bytecodes 增進效能。
  • invokedynamic
  • MethodHandle









Coin Project 算是 syntax sugar,在語法上提供了方便性。
老師有稍微講 switch 如何比對字串,基本上反組譯都可以看到過程。
也有說明到 rethrow 的問題,若 rethrow 拋出的例外大於 method 所保證的例外時如何處理。而自動資源管理目前只有對 IO 類別有用...



最後介紹 Objects 增加的一些功能,例如有助於陣列的比較之類的... 











  • What's new in Java EE 6.0
J2EE 我就聽得很模糊,Java 6 多了一些 annotation 的技術讓 deployment 能夠方便一些,不用設定 config.xml ...

Java Persistence API 是一種 ORM 技術,跟 iPhone 的 core data 不知道是不是差不多....

J2EE 阿~~







  • A Java-Enabled Platform for Ubiquitous Computing
SunSpot 是一個開放式的平台,有很多應用,聽講者介紹起來很有趣,像是遠端監控狗狗的應用、空中騎腳踏車等....






[Introduction To Algorithms] 第二堂: Growth of Functions(2)

這堂課先複習了利用微積分找極限的觀念來定上下界。 (p.14)
注意 Asymptotic Notation 與 微積分、集合的關西。
講到了集合,接下來就利用集合的理論對 Asymptotic Notation 做了一些推導:


結論就是: θ是 equivalence relation,而 Ο 是 partial order 的關西(同理類推其他的 notation)。










partial order 也就是可以比大小。




















當我們說 2n2 = θ(n2) 時,這裡的 = 是屬於的意思,所以不可以對調。但每個教科書或論文的定義多多少少都有些差異,所以要注意上下文的關西。


老師花了蠻多時間在講這張投影片,等號左邊是 "對每一個"、等號右邊是 "存在",把握集合的概念就可以了。


















這張投影片老師用了一個例子說明,當最高次項都一樣時可以比較其係數這時候就可以用:
2n2 + cn = 2n2 + θ(n) 的方式來讓最高次項的係數表示出來。


這張投影片也解釋了第二章 p.21 頁 cn 表示的問題,因為 θ是 equivalence relation 所以用 cn 來表示 θ(n) 是 OK 的。 但是 Ο 就不行這樣用。




  • T(n) = 2T(n/2) + θ(n)
  • T(n) ≦ 2T(n/2) + Ο(n)
    掰!




2011年2月28日 星期一

[Introduction To Algorithms] 第二堂: Growth of Functions

   老師講了一個觀念我覺得很不錯,Asympotic 也就是漸進線的意思,當 n 夠大時,會趨近某值。而 Big-O 也就是當 input size 夠大時,係數的差異就可以忽略過去。


這五種 asymptotic notation 之前就學過了,所以上課就比較沒有認真聽,不過再聽一次 Big-O 的定義時,覺得這種定義就很自然。
因為教科書上的定義問題,老師有解釋了一下,因為 computer 是離散的,但用連續函數表示比較方便,為了方便表示或是分析,有時候 n 會允許負數,雖然現實上是不可能。就方便方便~










關於定義的部分就參考講義,這裡要注意的是 Big-O 的定義和 Little-o 定義的差別,Big-O 是存在一個 c 而 Little-o 則是對每一個 c。


跟微積分一樣,證明極限值若用定義方式證明很不容易,像是扯到對數的話,這裡提供一個定理,接下來證明的話,可以用上下微分的方式來求出值...
懂概念就好,這證明也很簡單,兩邊的定義寫一下,就可以看出來相等。主要還是 O o 大於小於的觀念。