文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > Asymptotic Notation. Part I Theory 1
侵权投诉

Asymptotic Notation. Part I Theory 1

Summary. The widely used textbook by Brassard and Bratley [3] includes a chapter devoted to asymptotic notation (Chapter 3, pp. 79–97). We have attempted to test how suitable the current version of Mizar is for recording this type of material in its entir

JOURNALOFFORMALIZEDMATHEMATICS

Volume11,Released1999,Published2003

Inst.ofComputerScience,Univ.ofBia ystok

AsymptoticNotation.PartI:Theory1

RichardKrueger

UniversityofAlberta

EdmontonPiotrRudnickiUniversityofAlbertaEdmontonPaulShelleyUniversityofAlbertaEdmonton

Summary.ThewidelyusedtextbookbyBrassardandBratley[3]includesachap-

terdevotedtoasymptoticnotation(Chapter3,pp.79–97).Wehaveattemptedtotesthow

suitablethecurrentversionofMizarisforrecordingthistypeofmaterialinitsentirety.A

moredetailedreportonthisexperimentwillbeavailableseparately.Thisarticlepresentsthe

developmentofnotionsandafollow-uparticle[11]includesexamplesandsolutionstoprob-

lems.Thepreliminariesintroduceanumberofpropertiesofrealsequences,someoperations

onrealsequences,andacharacterizationofconvergence.Theremainingsectionsinthisar-

ticlecorrespondtosectionsofChapter3of[3].Section2de nestheOnotationandproves

thethreshold,maximum,andlimitrules.Section3introducesthe andΘnotationsand

theiranalogousrules.Conditionalasymptoticnotationisde nedinSection4wheresmooth

functionsarealsodiscussed.Section5de nessomeoperationsonasymptoticnotation(we

havedecidednottointroducetheasymptoticnotationforfunctionsofseveralvariablesasitis

astraightforwardgeneralizationofnotionsforunaryfunctions).

MMLIdenti er:ASYMPT_0.

WWW:doc.guandang.net

Thearticles[14],[18],[2],[16],[7],[4],[5],[15],[1],[9],[8],[12],[13],[6],[17],and[10]providethenotationandterminologyforthispaper.

1.PRELIMINARIES

Inthispaperc,ddenoterealnumbersandn,Ndenotenaturalnumbers.

Inthisarticlewepresentseverallogicalschemes.TheschemeFinSegRng1dealswithnaturalnumbersA,B,anonemptysetC,andaunaryfunctorFyieldinganelementofC,andstatesthat:

{F(i);irangesovernaturalnumbers:A≤i∧i≤B}isa nitenonemptysubset

ofC

providedthefollowingrequirementismet:

A≤B.

TheschemeFinImInit1dealswithanaturalnumberA,anonemptysetB,andaunaryfunctorFyieldinganelementofB,andstatesthat:

{F(n);nrangesovernaturalnumbers:n≤A}isa nitenonemptysubsetofB

forallvaluesoftheparameters.

TheschemeFinImInit2dealswithanaturalnumberA,anonemptysetB,andaunaryfunctorFyieldinganelementofB,andstatesthat:

{F(n);nrangesovernaturalnumbers:n<A}isa nitenonemptysubsetofB

providedtheparametershavethefollowingproperty:

A>0.

第1页

你可能喜欢

热门文档

相关文档

  • Asymptotic Notation,

    Asymptotic Notation,Asymptotic Notation,隐藏>> Asymptotic Notation, Review of Functions & Summations Jan. 2011 Asymptotic Complexity Running time of an ...

  • asymptotic notation

    CSc 345 — Analysis of Discrete Structures (McCann) Asymptotic Notation: O(... Asymptotic analysis 34页 免费 Asymptotic Theory of S... 745页 免费 ...

  • Analysis of Algorithms Asymptotic Notation Asymptot...

    Analysis of Algorithms Asymptotic Notation Asymptotic Analysis_专业资料。Analysis of Algorithms Asymptotic Notation Asymptotic Analysis...

  • Asymptotic Theory of Locally Conic Models and its A...

    Asymptotic Notation. Par... 暂无评价 7页 免费 ASYMPTOTIC PROPERTIES... 6页 免费 Asymptotic Hodge theory ... 暂无评价 21页 免费 Asymptotic conservation ...

  • Statistics 552 Asymptotic Theory

    Asymptotic Theory of Sta... 745页 免费 Asymptotic Properties of... 10页 1财富值 Asymptotic Notation. Par... 暂无评价 7页 免费 ASYMPTOTIC RAY THEORY...

  • 01Analysis_...

    book Overview Page 5 Algorithm Design I Part I...Number Theory and Cryptography Rolf Haenni & ...notation To perform the asymptotic analysis ¨ ...

  • Theory of Algorithm_handout_1

    I. Theory of Computation is to understand the ...So we are measuring the asymptotic running time ...The O-Notation The O-notation provides an upper...

  • Information Theory

    universal coding theorems and algorithms are also asymptotic in nature i.e.... . " Notation: Let ` X1 = X1 ; X2 ; : : : ; X` ; Xi 2 ...

  • 2014演化计算_1...

    Asymptotic notation Exercise 1: Asymptotic Notation How to Analyse Time Complexity of EAs Basic Probability Theory Binomial Random Variables ? We run an ...

  • PART 1 Preliminaries

    1. 2. Empirical comparison (run programs) Asymptotic Algorithm Analysis (...Engineering Big-oh Notation (cont) BigBig-oh notation indicates an upper ...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email