94695

COMPUTER RESEARCH

Конспект урока

Иностранные языки, филология и лингвистика

The IBM Computer Science team explores foundational issues that confront the computing industry today. Because theory cuts across every aspect of computer science, they tend to interact with a large number of other research teams. The IBM research center has ongoing projects in the following areas...

Английский

2015-09-15

85.5 KB

0 чел.

116

UNIT IX

COMPUTER RESEARCH

INTRODUCTORY

INTRODUCTORY TEXT

    The IBM Computer Science team explores

                                           foundational issues that confront the computing industry today. Because theory cuts across every aspect of computer science, they tend to interact with a large number of other research teams. The IBM research center has ongoing projects in the following areas:

-Algorithms: How can you get computers to solve problems efficiently?

-Complexity: What computational resources (time, storage, etc) do problems inherently require?

-Database: What models and algorithms are useful in helping computers store and retrieve information efficiently?

-Web: What is the overall structure of the World-wide Web, and how can algorithms take advantage of this?

IBM’s focus on algorithms falls under the following broad categories: (1) Massive data set algorithms: The design of algorithms that work on massive data sets is inevitable from a practical point of view. These algorithms have to work with very limited main memory. Three computational models have been proposed in this setting: the data stream model where the algorithm can make one or few passes over the data; the sampling model, where the algorithm is allowed random access; and the sublinear model, where the running time of the algorithm has to be sublinear in its input size. (2) Approximation algorithms: To overcome the curse of NP-hardness, developing approximation algorithms becomes important. The primal-dual and the semi-definite programming methods have been of immense help in this regard. These tools have yielded remarkably powerful algorithms to to solve many important combinatorial optimization problems. (3) Aggregation algorithms: Developing algorithms for improving the performance of large-scale databases and information retrieval system is a challenging task. Recent interests include aggregation algorithms with performance guarantees and static pruning methods for reducing the index size in IR systems. (4) Other algorithms: Other interests of the IBM research team include lattice algorithms, online algorithms, and property testing algorithms.

Complexity theory is a field that concerns itself with the intrinsic computational difficulty of problems. It focuses on the effect of limiting natural computational resources, e.g. time and space, on the class of problems that need to be solved. The emphasis is on generality, and this is usually achieved by defining appropriate models of computation. The classical Turing machine captures the notion of general computation. In dealing with specific classes of problems, it has been fruitful to also consider other models such as circuits, probabilistic Turing machines, random access machines, interactive proof systems, sampling/data stream models etc. The group at IBM Almaden has focused on a variety of problems in this area. Recent work has addressed the complexity of lattice problems, zero-knowledge protocols, fault-tolerant computing, property testing, derandomization, communication complexity, sampling, an data stream algorithms.     

There is a long history of research at IBM on the theory of databases, going back to the early days of the relational model, which was invented, developed, and studied extensively here. Their main database focus now, both in theory and in more practical projects, is on less traditional ways of storing data, such as in multimedia databases and in emerging databases and data service technologies for the Internet. In the area of multimedia databases, IBM investigated aggregation algorithms for combining fuzzy information from multiple sources

Algorithmic tools for searching and mining the web are becoming increasingly sophisticated and vital. In this context, algorithms that use and exploit structural information about the web perform better than generic methods in both efficiency and reliability. The IBM research center provides a characterization of the web that shows that the web emerges as the outcome of a number of essentially independent stochastic processes that evolve at various scales. A striking consequence of this scale invariance is that the structure of the web is “fractal”- cohesive sub-regions displays the same characteristics as the web at large. An understanding of this underlying fractal nature is therefore applicable to designing data services across multiple domains and scales. We describe potential applications of this line of research to optimized algorithm design for web-scale data analyses.

The IBM focuses on two kinds of Web-related research. The first is understanding and modeling the seemingly chaotic Web and the second is developing algorithms that exploit this understanding. Several macro-level micro-level connectivity properties of the Web were studied and the bow-tie model was proposed to abstract the connectivity properties. A simple stochastic model was constructed to explain experimentally observed phenomena; such models can be used to predict the evolution of the Web.

TOPICAL VOCABULARY

  1.  massive data set algorithms          алгоритмы большого

                                                                      объёма данных

  1.  data stream model                         модель потока данных
  2.  sampling model                            модель выборочного типа
  3.  random access                              прямой (произвольный)

                                                                      доступ

  1.  sublinear model                            сублинейная модель
  2.  approximation algorithms            алгоритмы

                                                                      аппроксимирующего

                                                                      типа

  1.  primal-dual method                      основной двухвариантный

                                                                      метод

  1.  semi-definite method                    метод нечёткого типа
  2.  diverse                                           разнообразный
  3.  aggregation algorithms                 алгоритмы совокупного

                                                                      типа 

  1.  information retrieval system         система возвращения

                                                                       информации

  1.  performance guarantees                гарантии эффективности

                                                                       эксплуатации

  1.  static pruning method                   статический метод

                                                                      отсечения решений

  1.  lattice algorithm                           алгоритм решётчатого

                                                                      типа

  1.  online algorithm                           интерактивный алгоритм
  2.  property testing algorithm           алгоритм проверки

                                                                      свойств

  1.  intrinsic                                        свойственный,

                                                                      внутренний

  1.  Turing machine                            машина Тьюринга

                                                                      (гипотетический

                                                                       вычислитель)

  1.  interactive proof systems             системы интерактивных

                                                                       испытаний

  1.  fault-tolerant                                отказоустойчивый
  2.  relational model                           модель отношения,

                                                                      сравнения

  1.  fuzzy information                        нечёткая информация
  2.  generic method                            базовый (общий) метод
  3.  fractal structure/nature                фрактальная

                                                                     структура/природа

  1.  cohesive                                      способный к сцеплению,

                                                                      связующий

  1.  bow-tie model                             модель в виде завязанного банта

 EXERCISES

1. Read the introductory text again and answer these questions.

  •  What ongoing projects does IBM develop?
  •  What categories does their focus on algorithms fall under?
  •  What is the IBM’s complexity theory concerned with?
  •  Can you name the ways of storing data employed in the IBM?
  •  What characterization of the Web do IBM researchers give?
  •  What for was the bow-tie model proposed?     

2. Find in the text equivalents for the following words and word-combinations:

разрабатываемые проекты; круг интересов в ч-л.; с практической точки зрения; неизбежный; сотрудничать с; исследовать проблемы; делиться на категории; время работы; вычислительная модель; преодолеть проблему; улучшить работу; сложная задача; крупномасштабные базы данных; заниматься/интересоваться ч-л.; хранение данных; надёжность; потенциальное применение; исследование всемирной сети; экспериментально выявленное явление.

3. Read the text. Do the tasks given below.

CAN COMPUTERS OUTSMART US?

If the world’s population continues to grow at its present rate- doubling every 40 years- there isn’t going to be enough room for us all on Earth by the year 2600. The only sounds in the room are the clicking of the pressure pads and the whirring of the computer. We need to become more complex if biological systems are to keep ahead of electronic ones. At the moment computers have an advantage of speed but they show no sign of intelligence. This is not surprising as our present computers are less complex than the brain of an earthworm, a species not known for its intellectual powers. But computer’s speed and complexity double every eighteen months and this will probably continue until computers have a similar complexity to the human brain.

But will computers ever show true intelligence, whatever it might be? It seems to me that if very complicated chemical molecules can operate in humans to make them intelligent, then equally complicated electronic circuits can also make computers act in an intelligent way. And if they are intelligent, they can presumably design computers that have even greater intelligence and complexity.

  •  Choose the words given below to complete the text:

Twenty years ago we relied mainly on TVs, radios and stereo equipment to provide entertainment in our homes, (1)___ their place is quickly being taken over by computers. (2)___ do we use computers to lighten or load at work, increasingly we are using computers for fun. (3)___. More and more home computers have access to the Internet. (4)___ we can now access a huge range of leisure facilities in our homes, such as reading newspapers on screen, shopping from home, (5)___ downloading music and films. Developments in optical fibre cables and DVD videos CDs mean that we can now download entire albums or feature films onto our computers and soon video players and hi-fis could become totally obsolete

But now; but then; also; it’s true that; as well; not only; so, in this sense; but more importantly; this means that; as well as; after all.

  •   Make sentences out of the two parts:

1. Computers’ speed and complexity

A. will have a similar complexity to the human brain.

2. To keep ahead of electronic systems

B. may become the only sounds in the room in the future.

3. Is it possible that computer

C. double every ten years.

4. The clicking of the pressure pads and computer whirring

D. no sign of intelligence.

5. At the moment computers show

E. people need to become more complex.

DISCUSSION

Working in pairs discuss the following problems:

  1.  What role does the computer play in your everyday life?
  2.  Do you think it will be the same in ten years’ time?
  3.  Do you use e-mail or the Internet? If you do, what do you use them for?

SUPPLEMENTARY READING

    VIDEO GAMES  

                                               

Video games these days are extremely popular. One in four households in Britain has a Playstation and in 1999 the video game industry made nearly a billion pounds, which was 60 percent more than cinema box office takings.

So, why are video games so popular? Well, they combine very fast moving, well-designed graphical images with very interesting sound design and music. But crucially they’re interactive, so they can change according to what you do from moment to moment, so the computer system concentrates on what you are saying to it, and poses you very interesting challenges and difficulties at very high speed.

The first commercial video game came along in 1971. IT was called Computer Space. Unfortunately it wasn’t very successful because it was a very complicated game involving spaceships and torpedoes and black holes and so forth. The same man who had invented that invented a game called Pong in 1972 and that’s when the video game explosion really took off. It was a very simple tennis game.

The very early video games like Pong just took place on one screen and the boundaries of the screen were the boundaries of the playing area. But then the space in video games started to get larger. The games started to scroll from side to side or up and down, so that the playing area became larger than the total size o one screen. The graphics in games slowly became more colourful and more detailed and then the big innovation took place in the 90’s, which was the invention of full 3D. This meant that you started to control characters who explored fully realized, solid 3D environments. You could wander round landscapes and buildings and look at them from any angle.

I think video games are close to becoming an art form in itself. Certainly, when cinema was only around 30 years old, as video games are today, a lot of people thought films were mindless entertainment and rotted peoples’ brains and were no good. But now we know that cinema is an art form and we have film critics who can analyse films and enhance our enjoyment of them, so in the future it will be true of video games as well. The current research in video games is concentrating on artificial intelligence. People want to play video games that give a greater illusion of interacting with real characters.       

 

FINAL TEST

  •  Put the following sentences in the same sequence as the information is arranged in the introductory text (Расположите следующие предложения в той же последовательности как информация представлена в вводном тексте)

1.  A. Complexity theory developed by the IBM research center is concerned with the intrinsic computational difficulty of problems.

     B. The bow-tie model was proposed to abstract the connectivity properties of the Web.

     C. The IBM investigated aggregation algorithms for combining fuzzy information from multiple sources.

     D. Other algorithms developed by the IBM include lattice algorithms, online algorithms, and property testing algorithms.

  •  Choose the right English equivalent to the following Russian sentence (Выберите верный английский эквивалент следующему русскому предложению)

 Алгоритмические инструменты для исследования сети постоянно усложняются.

2. A. Algorithmic tools for searching the web are becoming increasingly vital.

        B.  Algorithmic tools for searching the web are becoming more reliable.

       C. Algorithmic tools for searching the web are becoming increasingly sophisticated.

  •  Choose the right Russian equivalent to the following English sentence (Выберите верный русский эквивалент следующему английскому предложению)

Because theory cuts across every aspect of computer science, the IBM tends to interact with a large number of other research teams.

3.  A. Так как теория полностью соответствует компьютерной науке, IBM взаимодействует с большим количеством исследовательских групп.

     B. Так как теория затрагивает все аспекты компьютерной науки,

IBM взаимодействует с большим количеством исследовательских групп.

     C. Так как теория идёт в разрез с компьютерной наукой, IBM не склонна сотрудничать с большим количеством исследовательских групп.

  •  Find the equivalents in two languages (Найдите эквиваленты в двух языках)

4. fault-tolerant                         A. модель выборочного типа

5. sampling model                    B. произвольный доступ

6. random access                      C. базовый метод

7. fuzzy information                 D. нечёткая информация

8. generic method                     E. отказоустойчивый

                                                 F. метод отсечения

  •  Complete the sentences with the proper word (Закончите предложения подходящим по смыслу словом)

9. To overcome NP-hardness the IBM developed good … … .

10. The algorithms are allowed random access to data in the … … .

11. The IBM focuses now on less traditional ways of storing … .

12. It was discovered that the structure of the Web is … .

13. Stochastic models can be used to predict the evolution of the …

14. Algorithms for improving the performance of  large scale databases

are … .

15. Massive data set algorithms have to work with very limited main … .

16. To abstract the connectivity properties of the Web there was proposed the … … .

17. The intrinsic computational difficulty is a field of concern of … … .

  •  Choose the right variant (выберите правильный вариант)

18. The running time of the algorithm is of great importance in

A. sampling model    B. data stream model      C. sublinear model

19. Random access to data is allowed to the algorithm in the

A. sampling model    B. data stream model      C. sublinear model

20.The algorithm can make one or few passes over the data in the

A. sampling model    B. data stream model      C. sublinear model

21. At the moment computers have an advantage of speed but they show no sign of

  1.  Complexity                       C. vitality
  2.  Intelligence                        D. reliability

22. In the future computers may have a similar complexity to the human

A. thoughts                 B. ideas                  C. Brain

23. The problem of computational resources is touched upon in the IBM’s project

A.”algorithms”                      C. “complexity”

B.”web”                                 D. “database principles”

24. The aspect of efficient problem solving is discussed in the IBM’s project

A.”algorithms”                      C. “complexity”

B.”web”                                 D. “database principles

25.To overcome the curse of NP-hardness … algorithms become important.

A. massive data set        B. approximation         C. aggregation


 

А также другие работы, которые могут Вас заинтересовать

29577. Коммерческая и социальная реклама в СМК 15.24 KB
  Функции выполняемые социальной и коммерческой рекламы посредством СМК: 1. Коммерческая реклама: В соответствие с современным подходом к изучению рекламы коммерческая реклама входит в комплекс маркетинговых коммуникаций в который помимо рекламы входят такие инструменты как стимулирование сбыта PR пропаганда и личные продажи. Социальная реклама вид некоммерческой рекламы направленной на изменение моделей общественного поведения и привлечения внимания к проблемам социума. В 1993 году был образован негосударственный Рекламный Совет в...
29578. Состояние медиарынка в кризисный и поскризисный период, тенденции дальнейшего развития 24.52 KB
  Те компании которые выжили в это время оказались в очень неплохой ситуации. Как отмечают специалисты основным принципом коммуникаций в кризисной ситуации – не замалчивать события говорить все и как можно скорее. Однако на ранних стадиях кризисной ситуации не следует говорить вещей которых вы не знаете или в которых вы не уверены не следует включаться в догадки поскольку вы можете оказаться не правы. Американские специалисты предлагают учитывать следующие позиции в подобной ситуации [10 с.
29579. Телевидение XXI века: соотношение социальных, политических и коммерческих функций 13.23 KB
  Степень этой вовлеченности и мера воздействия ТВ на аудиторию в плоскости выполнения этой функции зависят от той системы в которой действует данное телевизионное СМИ. Особенно сильно подобное отношение к СМИ вообще и к ТВ в частности у населения постсоветских государств. Люди ждут реакции властей на критические выступления касающиеся тех или иных явлений жизни по инерции доставшейся от советской системы в то время как СМИ – лишь способ донести информацию об этих явлениях до своей аудитории. Дальнейшее зависит уже не от СМИ выпадающего из...
29580. Интернет: история, возможности и прогнозы 16.93 KB
  Интернет: история возможности и прогнозы. Исторически интернет произошел от американской сети RPNET которая разрабатывалась как децентрализованное средство обмена информацией в случае ядерного удара. Прототип интернета RPNET в 1969 соединил сеть американских научно исследовательских университетов. Следующим значительным скачком в развитии интернета стал концепт всемирной паутины выдвинутый в 1989 Тимом БернсЛи идея создания универсального языка HTML Аштэмэйли протокола связи HTTPАштэтэпэ что позволило сделать интернет таким каким он...
29581. Информационное общество: основные характеристики, тенденции развития. Дискуссии в отношении позитивных изменений и негативных последствий всеобщей информатизации и глобализации мирового пространства 16.15 KB
  Информационное общество – ступень в развитии современной цивилизации характеризующаяся увеличением роли информации и знаний в жизни общества; возрастанием доли инфокоммуникаций информационных продуктов и информационных услуг в валовом внутреннем продукте ВВП; созданием глобального информационного пространства обеспечивающего эффективное информационное взаимодействие людей их доступ к мировым информационным ресурсам и удовлетворение их социальных и личностных потребностей в информационных продуктах и услугах. Основные характеристики:...
29582. Массовое сознание 12.93 KB
  На общественное мнение влияют мнения людей признаваемых обществом авторитетными и компетентными личный опыт людей В формировании общественного мнения выделяются: субъект воздействия – элитные группы стремящиеся к достижению или удержанию власти заказчики и исполнители государство аналитики журналисты и т.; объект воздействия – массовое сознание изменение которого является целью субъекта; инструмент воздействия – СМИ как массмедиа так и институты социализации культура и т. Формы и способы влияния общественного мнения на личность...
29583. Массовое сознание: Субъективистский и объективистский подходы 14.37 KB
  Массовое сознание включает в себя понятие массы: МассаОртега и Гаса это суждение некомпетентных низкое качество современной цивилизации; Масса Юнгер механизное общество в котором человек является придатком машины; Масса Зиммель Вебер Манхейм – это бюрократическое общество которое отличается широко расчленненой организацией в которой принятие решений допускается на высших этапах иерархии; МассаЛенин – совокупность трудящихся наименее организованных и просвещенных. МассаШарков это шаблонное Например когда в деревнях все...
29584. Стратегия и тактика планирования рекламной кампании 16.33 KB
  Стратегия и тактика планирования рекламной кампании. Планирование рекламной кампании это процесс в котором принимают участие все структурные подразделения рекламного агентства и маркетинговый отдел рекламодателя. Результат этого процесса составление плана рекламной кампании на определенный период. Главная задача планирования рекламной кампании определить как будет доноситься рекламное послание до потребителя: в какой форме с помощью каких средств массовой информации и в рамках какого бюджета.
29585. Основные понятия в медиапланировании (рейтинг, доля, HUT, PUT, PUR). Их расчет и соотношение в планировании рекламных кампаний 33.55 KB
  Home Using TV одним из базовых показателей в медиапланировании является число людей или домохозяйств в которых смотрят телевизор. Этот показатель описывает количество людей или домохозяйств использующих ТВ на определенный момент времени Иными словами это процент индивидуумов или домохозяйств использующих телевизор в данное время дня. Показатель HUT не включает людей смотрящих телевизор вне дома например в магазинах аэропортах отелях и т. То есть рекламное сообщение смогут увидеть те люди которые по крайней мере в данный момент...